Power of Quantum Algorithms and Open Questions

by

Quantum algorithms – what we can do and what could we do

Mathematical Challenges in Quantum Algorithms (51 pages)

There are many things we can do with our quantum computers. For example:
Factorise large integers and hence break RSA;
Efficiently simulate quantum-mechanical systems;
Solve certain search and optimisation problems faster than possible classically;
. . .

See the Quantum Algorithm Zoo
(http://math.nist.gov/quantum/zoo/) for 214 219
papers on quantum algorithms

Nevertheless, many embarrassingly fundamental open problems remain in the study of quantum computing:
* What we can do;
* What we can’t do;
* Why we can do what we can.