Which problems have a known quantum advantage?
Mainly factoring and discrete log (Shor), unstructured search (Grover, quadratic), simulation of quantum systems, and oracle problems.
The list known in theory is limited and specific:
- Factoring and discrete logarithms: Shor's algorithm is polynomial, while the best known classical algorithm is sub-exponential. There is no proof that no fast classical algorithm exists.
- Unstructured search and amplitude amplification: Grover, a quadratic speed-up proven to be optimal.
- Simulating quantum systems (chemistry and materials): expected to be among the most important applications, using phase estimation on fault-tolerant devices.
- Oracle problems (Deutsch–Jozsa, Bernstein–Vazirani, Simon): a proven separation in the query model, without a direct practical application.
Variational algorithms (VQE, QAOA, QML) are heuristic, and there is as yet no general proof of their advantage. All of the above generally assume large, fault-tolerant computers.
Related topics
References
- Michael A. Nielsen; Isaac L. Chuang (2010). Quantum Computation and Quantum Information (10th Anniversary Edition). Cambridge University Press doi:10.1017/CBO9780511976667The standard reference for quantum computing; the Crossref record gives 2012 for the Cambridge Core online edition.
- John Preskill (2018). Quantum Computing in the NISQ era and beyond. Quantum 2:79 doi:10.22331/q-2018-08-06-79
- John Watrous / IBM Quantum (2025). Fundamentals of Quantum Algorithms (course). IBM Quantum Learning quantum.cloud.ibm.com
