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 quantum algorithms such as 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:

Review and outlook:

see also at quantum computation – References - Limits of NISQ

  • 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]

  • Torsten Hoefler, Thomas Haener, Matthias Troyer, Disentangling Hype from Practicality: On Realistically Achieving Quantum Advantage, Communications of the ACM 66 5 (May 2023) 82-87 [arXiv:2307.00523, acm pdf, doi:10.1145/3571725]

    “A large range of problem areas with quadratic quantum speedups, such as many current machine learning training approaches, accelerating drug design and protein folding with Grover’s algorithm, speeding up Monte Carlo simulations through quantum walks, as well as more traditional scientific computing simulations including the solution of many non-linear systems of equations, such as fluid dynamics in the turbulent regime, weather, and climate simulations will not achieve quantum advantage with current quantum algorithms in the foreseeable future.”

  • Ryan Babbush, Jarrod R. McClean, Michael Newman, Craig Gidney, Sergio Boixo, Hartmut Neven, Focus beyond Quadratic Speedups for Error-Corrected Quantum Advantage, PRX Quantum 2 010103 (2021) [doi:10.1103/PRXQuantum.2.010103]

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]

Classical computations competing with these claims:

  • Zhao et al.: Leapfrogging Sycamore: Harnessing 1432 GPUs for 7× Faster Quantum Random Circuit Sampling [arXiv:2406.18889]

    “Here we report an energy-efficient classical simulation algorithm, using 1432 GPUs [which is] 7 times faster than Sycamore 53 qubits experiment.”

    arXiv Comments: “This work was completed on August 2023. A further 50x improvement has been achieved and will be posted on arXiv shortly”

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 June 29, 2024 at 09:50:29. See the history of this page for a list of all contributions to it.