Global InformationQuantum supremacy information
 | This article may be too technical for most readers to understand. (October 2019) |
In quantum computing, quantum supremacy or quantum advantage is the goal of demonstrating that a programmable quantum computer can solve a problem that no classical computer can solve in any feasible amount of time, irrespective of the usefulness of the problem.[1][2][3] The term was coined by John Preskill in 2012,[1][4] but the concept dates to Yuri Manin's 1980[5] and Richard Feynman's 1981[6] proposals of quantum computing.
Conceptually, quantum supremacy involves both the engineering task of building a powerful quantum computer and the computational-complexity-theoretic task of finding a problem that can be solved by that quantum computer and has a superpolynomial speedup over the best known or possible classical algorithm for that task.[7][8]
Examples of proposals to demonstrate quantum supremacy include the boson sampling proposal of Aaronson and Arkhipov,[9] and sampling the output of random quantum circuits.[10][11] The output distributions that are obtained by making measurements in boson sampling or quantum random circuit sampling are flat, but structured in a way so that one cannot classically efficiently sample from a distribution that is close to the distribution generated by the quantum experiment. For this conclusion to be valid, only very mild assumptions in the theory of computational complexity have to be invoked. In this sense, quantum random sampling schemes can have the potential to show quantum supremacy.[12]
A notable property of quantum supremacy is that it can be feasibly achieved by near-term quantum computers,[4] since it does not require a quantum computer to perform any useful task[13] or use high-quality quantum error correction,[14] both of which are long-term goals.[2] Consequently, researchers view quantum supremacy as primarily a scientific goal, with relatively little immediate bearing on the future commercial viability of quantum computing.[2] Due to unpredictable possible improvements in classical computers and algorithms, quantum supremacy may be temporary or unstable, placing possible achievements under significant scrutiny.[15][16]
- ^ a b Preskill, John (2012-03-26). "Quantum computing and the entanglement frontier". arXiv:1203.5813 [quant-ph].
- ^ a b c Preskill, John (2018-08-06). "Quantum Computing in the NISQ era and beyond". Quantum. 2: 79. arXiv:1801.00862. Bibcode:2018Quant...2...79P. doi:10.22331/q-2018-08-06-79.
- ^ Cite error: The named reference
:6was invoked but never defined (see the help page). - ^ a b Cite error: The named reference
:14was invoked but never defined (see the help page). - ^ Manin, Yu. I. (1980). Vychislimoe i nevychislimoe [Computable and Noncomputable] (in Russian). Sov.Radio. pp. 13–15. Archived from the original on 2013-05-10. Retrieved 2013-03-04.
- ^ Feynman, Richard P. (1982-06-01). "Simulating Physics with Computers". International Journal of Theoretical Physics. 21 (6–7): 467–488. Bibcode:1982IJTP...21..467F. CiteSeerX 10.1.1.45.9310. doi:10.1007/BF02650179. ISSN 0020-7748. S2CID 124545445.
- ^ Harrow, Aram W.; Montanaro, Ashley (September 2017). "Quantum computational supremacy". Nature. 549 (7671): 203–209. arXiv:1809.07442. Bibcode:2017Natur.549..203H. doi:10.1038/nature23458. ISSN 1476-4687. PMID 28905912. S2CID 2514901.
- ^ Papageorgiou, Anargyros; Traub, Joseph F. (2013-08-12). "Measures of quantum computing speedup". Physical Review A. 88 (2): 022316. arXiv:1307.7488. Bibcode:2013PhRvA..88b2316P. doi:10.1103/PhysRevA.88.022316. ISSN 1050-2947. S2CID 41867048.
- ^ Aaronson, Scott; Arkhipov, Alex (2011). "The computational complexity of linear optics". Proceedings of the forty-third annual ACM symposium on Theory of computing. STOC '11. New York, New York, United States: Association for Computing Machinery. pp. 333–342. arXiv:1011.3245. doi:10.1145/1993636.1993682. ISBN 9781450306911. S2CID 681637.
- ^ Aaronson, Scott; Chen, Lijie (2016-12-18). "Complexity-Theoretic Foundations of Quantum Supremacy Experiments". arXiv:1612.05903 [quant-ph].
- ^ Bouland, Adam; Fefferman, Bill; Nirkhe, Chinmay; Vazirani, Umesh (2018-10-29). "On the complexity and verification of quantum random circuit sampling". Nature Physics. 15 (2): 159–163. arXiv:1803.04402. doi:10.1038/s41567-018-0318-2. ISSN 1745-2473. S2CID 125264133.
- ^ Hangleiter, Dominik; Eisert, Jens (2023-07-20). "Computational advantage of quantum random sampling". Reviews of Modern Physics. 95 (3): 035001. arXiv:2206.04079. Bibcode:2023RvMP...95c5001H. doi:10.1103/RevModPhys.95.035001. S2CID 249538723.
- ^ Metz, Cade (2019-10-23). "Google Claims a Quantum Breakthrough That Could Change Computing (Published 2019)". The New York Times. ISSN 0362-4331. Retrieved 2020-12-07.
- ^ Aaronson, Scott (2019-10-30). "Opinion | Why Google's Quantum Supremacy Milestone Matters (Published 2019)". The New York Times. ISSN 0362-4331. Retrieved 2020-12-07.
- ^ Cite error: The named reference
ibmsupremacywas invoked but never defined (see the help page). - ^ Crane, Leah. "IBM says Google may not have reached quantum supremacy after all". New Scientist. Retrieved 2020-12-07.