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
12:30 PM

Dr. Andrew Childs
California Institute of Technology

From Optimal State Estimation to Efficient Quantum Algorithms

Abstract

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).