News Archives

[Colloquium] Quantum algorithms and quantum state identification

March 29, 2007

Watch Colloquium: 

AVI file (282 MB)
Quicktime (115 MB)


  • Date: Thursday, March 29th, 2007 
  • Time: 11 am— 12:15 pm 
  • Place: ECE 118

Andrew Childs
California Institute of Technology

Abstract: Quantum mechanical computers would be much faster than ordinary classical computers at solving certain problems, such as factoring integers. However, the full extent of the computational power of quantum mechanics is not well understood. In this talk, I will describe recently developed quantum algorithms that outperform classical computation. These algorithms are based on efficient procedures for identifying quantum states. A simple example of a problem that can be solved in this way is the abelian hidden subgroup problem (HSP), the core problem solved by the factoring algorithm. I will explain how entangled measurements can be used to extend this approach to certain nonabelian HSPs. I will also describe how a similar approach can be applied to a new generalization of the abelian HSP, namely a problem of finding hidden nonlinear structures.