nLab quantum supremacy

Idea

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.

Related concepts

• quantum complexity theory

References

General

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:

• Rønnow et al. Defining and detecting quantum speedup, Science 345 6195 (2014) 420-424 [doi:10.1126/science.1252319]

• Wikipedia, Quantum supremacy

Review:

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

• Sankar Das Sarma, Quantum computing has a hype problem, MIT Technology Review (March 2022)

  The qubit systems we have today are a tremendous scientific achievement, but they take us no closer to having a quantum computer that can solve a problem that anybody cares about. $[\cdots]$ What is missing is the breakthrough $[\cdots]$ bypassing quantum error correction by using far-more-stable qubits, in an approach called topological quantum computing.

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:

• F. Arute et al. Quantum supremacy using a programmable superconducting processor, Nature 574 (2019) 505–510 (doi:10.1038/s41586-019-1666-5)

• Han-Sen Zhong et al., Quantum computational advantage using photons, Science 370 6523 (2020) 1460-1463 (doi:10.1126/science.abe8770)

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:

• Adrian Cho, Google claims quantum computing milestone, Science 365 6460 (2019) 1364 (doi:10.1126/science.365.6460.1364)

• Philip Ball, Physicists in China challenge Google’s “quantum advantage”, Nature 588 380 (2020) [doi:10.1038/d41586-020-03434-7]

• Barry C. Sanders, Quantum Leap for Quantum Primacy, Physics 14 147 (2021)

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:

• Peter W. Shor, Algorithms for quantum computation: discrete logarithms and factoring, Proceedings 35th Annual Symposium on Foundations of Computer Science, IEEE Comput. Soc. Press: 124-134 (1994) [doi:10.1109/SFCS.1994.365700]

• Daniel R. Simon, On the power of quantum computation, SIAM Journal on Computing 26 5 (1997) [doi:10.1137/S0097539796298637, pdf]

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

• Lov K. Grover, A fast quantum mechanical algorithm for database search, STOC ‘96: Proceedings of the twenty-eighth annual ACM symposium on Theory of Computing (1996) 212-219 [arXiv:quant-ph/9605043, doi:10.1145/237814.237866]

The case of the Deutsch-Jozsa algorithm:

• David Deutsch, Richard Jozsa, Rapid solution of problems by quantum computation. Proc. R. Soc. Lond. A 439 1907 (1992) 553-558 [pdf, doi:10.1098/rspa.1992.0167]

For integral transforms:

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

Survey:

• Andrew M. Childs, Wim van Dam, Quantum algorithms for algebraic problems, Rev. Mod. Phys. 82 1 (2010) [arXiv:0812.0380, doi:10.1103/RevModPhys.82.1]

Application of quantum computing to quantum chemistry:

• Seth Lloyd, Universal Quantum Simulators, Science New Series 273 5278 (1996) 1073-1078 [jstor:2899535, doi:10.1126/science.273.5278.1073]

• Quantum Chemistry in the Age of Quantum Computing, Chem. Rev. (2019) 119 19 (2019) 10856–10915 [doi:10.1021/acs.chemrev.8b00803]

Argument that quantum supremacy in quantum chemistry is elusive:

• Garnet Kin-Lic Chan et al., Is there evidence for exponential quantum advantage in quantum chemistry? [arXiv:2208.02199, talk video]

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:

• Scott Aaronson, Lijie Chen, Complexity-Theoretic Foundations of Quantum Supremacy Experiments, CCC ‘17: Proceedings of the 32nd Computational Complexity Conference (2017) 22 1–67 [arXiv:1612.05903, doi;10.5555/3135595.3135617]