Quantum Lunch Location:
T-Division Conference Room, TA-3,
Building 123, Room 121
Quantum Institute: Visitor Schedule
The Quantum Lunch is regularly held on Thursdays in the Theoretical Division Conference Room, TA-3, Building 123, Room 121.
For more information, contact Diego Dalvit.
July 13, 2006
Dr. Andrew Childs
California Institute of Technology
From Optimal State Estimation to Efficient Quantum Algorithms
One of the major challenges facing quantum computation is to better understand what problems can be solved faster by quantum computers than by classical ones. In particular, we would like to develop new algorithmic tools for obtaining quantum speedup. In this talk, I will present an approach to quantum algorithms based on optimal measurements for distinguishing quantum states. This approach has led to new quantum algorithms with exponential speedup for certain instances of the hidden subgroup problem and other related problems. These algorithms implement joint measurements on several copies of the states to be distinguished, which is significant since independent measurements are provably insufficient in some cases. I will present such an algorithm in detail for the hidden subgroup problem over the Heisenberg group, and I will survey other recent developments.
This talk is based on joint work with Dave Bacon (University of Washington) and Wim van Dam (UC Santa Barbara).