Recent News
Computer Science Colloquium will discuss strategies for sustainable AI data centers
March 10, 2025
Dissertation defense: Alyshia Bustos
March 5, 2025
Computer Science undergraduate honored for cybersecurity research
February 20, 2025
Associate Professor Matt Lakin wins PECASE Award
January 31, 2025
News Archives
[Colloquium] Quantum algorithms and quantum state identification
March 29, 2007
- 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.