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 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:
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 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:
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:
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:
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 October 15, 2024 at 09:35:01. See the history of this page for a list of all contributions to it.