quantum algorithms:
constructive mathematics, realizability, computability
propositions as types, proofs as programs, computational trinitarianism
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:
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:
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. What is missing is the breakthrough bypassing quantum error correction by using far-more-stable qubits, in an approach called topological quantum computing.
See also:
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:
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:
See also:
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:
The case of the Deutsch-Jozsa algorithm:
For integral transforms:
Survey:
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:
Application to solid state physics:
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.