nLab quantum supremacy



Quantum systems

quantum logic

quantum physics

quantum probability theoryobservables and states

quantum information

quantum computation


quantum algorithms:

quantum sensing

quantum communication

Constructivism, Realizability, Computability



The notion that for certain tasks the power of quantum computation potentially drastically surpasses that of classical computation (e.g. via Shor's algorithm) has been called quantum supremacy (Preskill 2013, there related to the computational resource of quantum entanglement) or quantum advantage.



The term “quantum supremacy” is due to:

  • John Preskill: Quantum computing and the entanglement frontier: pp. 63-80 in: The Theory of the Quantum World – Proceedings of the 25th Solvay Conference on Physics, World Scientific (2013) [arXiv:1203.5813, doi:10.1142/8674, slides: pdf]

See also:


  • Scott Aaronson, How Much Structure Is Needed for Huge Quantum Speedups?, talk at: 28th Solvay Physics Conference in Brussels on May 21, 2022 [arXiv:2209.06930, slides: ppt]

Emphasis of the need of topological stabilization:

See also:

  • Takashi Yamakawa, Mark Zhandry, Verifiable Quantum Advantage without Structure [arXiv:2204.02063]

Experimental realizations

Claimed experimental demonstration of “quantum supremacy” (“quantum advantage”) in (very) special purpose applications:

Critical analysis:

  • Gil Kalai?, Yosef Rinott, Tomer Shoham, Google’s 2019 “Quantum Supremacy” Claims: Data, Documentation, and Discussion [arXiv:2210.12753]

Review and status reports:

Quantum advantage for Grover's algorithm:

  • Bibek Pokharel, Daniel Lidar, Better-than-classical Grover search via quantum error detection and suppression [arXiv:2211.04543]

See also:

  • Réouven Assouly, Rémy Dassonneville, Théau Peronnin, Audrey Bienfait, Benjamin Huard, Demonstration of Quantum Advantage in Microwave Quantum Radar [arXiv:2211.05684]

Potential applications

Discussion of algorithms for which quantum computers are expected to outperform classical computers:

The case of Shor's algorithm, relevant for quantum cryptography:

The case of Grover's algorithm, for database searches:

The case of the Deutsch-Jozsa algorithm:

For integral transforms:

  • Doğa Veske et al., Quantum Advantage for Integral Transforms [arXiv:2204.04159]


Application of quantum computing to quantum chemistry:

Argument that quantum supremacy in quantum chemistry is elusive:

Application to solid state physics:

  • Nobuyuki Yoshioka, Tsuyoshi Okubo, Yasunari Suzuki, Yuki Koizumi, Wataru Mizukami, Hunting for quantum-classical crossover in condensed matter problems [arXiv:2210.14109]

Quantum complexity theory

Discussion of complexity-theoretic aspects:

Last revised on December 12, 2022 at 09:54:35. See the history of this page for a list of all contributions to it.