Quantum supremacy
This article may be too technical for most readers to understand.(October 2019) |
In
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]
Background
Quantum advantage in the 20th century
In 1936, Alan Turing published his paper, “On Computable Numbers”,[17] in response to the 1900 Hilbert Problems. Turing's paper described what he called a “universal computing machine”, which later became known as a Turing machine. In 1980, Paul Benioff used Turing's paper to propose the theoretical feasibility of Quantum Computing. His paper, “The Computer as a Physical System: A Microscopic Quantum Mechanical Hamiltonian Model of Computers as Represented by Turing Machines“,[18] was the first to demonstrate that it is possible to show the reversible nature of quantum computing as long as the energy dissipated is arbitrarily small. In 1981, Richard Feynman showed that quantum mechanics could not be efficiently simulated on classical devices.[19] During a lecture, he delivered the famous quote, “Nature isn't classical, dammit, and if you want to make a simulation of nature, you'd better make it quantum mechanical, and by golly it's a wonderful problem, because it doesn't look so easy.”[19] Soon after this, David Deutsch produced a description for a quantum Turing machine and designed an algorithm created to run on a quantum computer.[20]
In 1994, further progress toward quantum supremacy was made when
Progress in the 21st century
Vast progress toward quantum supremacy was made in the 2000s from the first 5-qubit
On June 18, 2019,
In December 2020, a group based in the
In October 2021, teams from USTC again reported quantum primacy by building two supercomputers called Jiuzhang 2.0 and Zuchongzhi. The light-based Jiuzhang 2.0 implemented gaussian boson sampling to detect 113 photons from a 144-mode optical interferometer and a sampling rate speed up of 1024 – a difference of 37 photons and 10 orders of magnitude over the previous Jiuzhang.[51][52] Zuchongzhi is a programmable superconducting quantum computer that needs to be kept at extremely low temperatures to work efficiently and uses random circuit sampling to obtain 56 qubits from a tunable coupling architecture of 66 transmons — an improvement over Google's Sycamore 2019 achievement by 3 qubits, meaning a greater computational cost of classical simulation of 2 to 3 orders of magnitude.[53][54][55] A third study reported that Zuchongzhi 2.1 completed a sampling task that "is about 6 orders of magnitude more difficult than that of Sycamore" "in the classic simulation".[56]
In June 2022 Xanadu has reported on a boson sampling experiment summing to those of Google and USTC. Their setup used loops of optical fiber and multiplexing to replace the network of beam splitters by a single one which made it also more easily reconfigurable. They detected a mean of 125 up to 219 photon from 216 squeezed modes (squeezed light follows a photon number distribution so they can contain more than one photon per mode) and claim to have obtained a speedup 50 million times bigger than previous experiments.[57][58]
Computational complexity
The difficulty of proving what cannot be done with classical computing is a common problem in definitively demonstrating quantum supremacy. Contrary to decision problems that require yes or no answers, sampling problems ask for samples from probability distributions.[64] If there is a classical algorithm that can efficiently sample from the output of an arbitrary quantum circuit, the polynomial hierarchy would collapse to the third level, which is generally considered to be very unlikely.[10][11] Boson sampling is a more specific proposal, the classical hardness of which depends upon the intractability of calculating the permanent of a large matrix with complex entries, which is a #P-complete problem.[65] The arguments used to reach this conclusion have been extended to IQP Sampling,[66] where only the conjecture that the average- and worst-case complexities of the problem are the same is needed,[64] as well as to Random Circuit Sampling,[11] which is the task replicated by the Google[38] and USTC research groups.[48]
Proposed experiments
The following are proposals for demonstrating quantum computational supremacy using current technology, often called
Shor's algorithm for factoring integers
This algorithm finds the prime factorization of an n-bit integer in time[68] whereas the best known classical algorithm requires time and the best upper bound for the complexity of this problem is .
This algorithm is important both practically and historically for quantum computing. It was the first polynomial-time quantum algorithm proposed for a real-world problem that is believed to be hard for classical computers.[68] Namely, it gives a superpolynomial speedup under the reasonable assumption that RSA, a well-established cryptosystem, is secure.[71]
Factoring has some benefit over other supremacy proposals because factoring can be checked quickly with a classical computer just by multiplying integers, even for large instances where factoring algorithms are intractably slow. However, implementing Shor's algorithm for large numbers is infeasible with current technology,[72][73] so it is not being pursued as a strategy for demonstrating supremacy.
Boson sampling
This computing paradigm based upon sending identical photons through a linear-optical network can solve certain sampling and search problems that, assuming a few complexity-theoretical conjectures (that calculating the permanent of Gaussian matrices is #P-Hard and that the polynomial hierarchy does not collapse) are intractable for classical computers.[9] However, it has been shown that boson sampling in a system with large enough loss and noise can be simulated efficiently.[74]
The largest experimental implementation of boson sampling to date had 6 modes so could handle up to 6 photons at a time.[75] The best proposed classical algorithm for simulating boson sampling runs in time for a system with n photons and m output modes.[76][77] BosonSampling is an open-source implementation in the R programming language. The algorithm leads to an estimate of 50 photons required to demonstrate quantum supremacy with boson sampling.[76][77]
Sampling the output distribution of random quantum circuits
The best known algorithm for simulating an arbitrary random quantum circuit requires an amount of time that scales exponentially with the number of qubits, leading one group to estimate that around 50 qubits could be enough to demonstrate quantum supremacy.[33] Bouland, Fefferman, Nirkhe and Vazirani[11] gave, in 2018, theoretical evidence that efficiently simulating a random quantum circuit would require a collapse of the computational polynomial hierarchy. Google had announced its intention to demonstrate quantum supremacy by the end of 2017 by constructing and running a 49-qubit chip that would be able to sample distributions inaccessible to any current classical computers in a reasonable amount of time.[29] The largest universal quantum circuit simulator running on classical supercomputers at the time was able to simulate 48 qubits.[78] But for particular kinds of circuits, larger quantum circuit simulations with 56 qubits are possible.[79] This may require increasing the number of qubits to demonstrate quantum supremacy.[31] On October 23, 2019, Google published the results of this quantum supremacy experiment in the Nature article, “Quantum Supremacy Using a Programmable Superconducting Processor” in which they developed a new 53-qubit processor, named “Sycamore”, that is capable of fast, high-fidelity quantum logic gates, in order to perform the benchmark testing. Google claims that their machine performed the target computation in 200 seconds, and estimated that their classical algorithm would take 10,000 years in the world's fastest supercomputer to solve the same problem.[80] IBM disputed this claim, saying that an improved classical algorithm should be able to solve that problem in two and a half days on that same supercomputer.[81][82][83]
Criticisms
Susceptibility to error
Criticism of the name
Some researchers have suggested that the term "quantum supremacy" should not be used, arguing that the word "supremacy" evokes distasteful comparisons to the racist belief of white supremacy. A controversial[91][92] commentary article in the journal Nature signed by thirteen researchers asserts that the alternative phrase "quantum advantage" should be used instead.[93][94] John Preskill, the professor of theoretical physics at the California Institute of Technology who coined the term, has since clarified that the term was proposed to explicitly describe the moment that a quantum computer gains the ability to perform a task that a classical computer never could. He further explained that he specifically rejected the term "quantum advantage" as it did not fully encapsulate the meaning of his new term: the word "advantage" would imply that a computer with quantum supremacy would have a slight edge over a classical computer while the word "supremacy" better conveys complete ascendancy over any classical computer.
"Quantum primacy" was coined in February 2021, in a Scientific American opinion piece as a more suitable replacement.[4] Nature's Philip Ball wrote in December 2020 that the term "quantum advantage" has "largely replaced" the term "quantum supremacy".[95]
See also
References
- ^ ].
- ^ .
- ^ S2CID 227254333.
- ^ a b c "John Preskill Explains 'Quantum Supremacy'". Quanta Magazine. 2 October 2019. Retrieved 2020-04-21.
- ^ 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.
- S2CID 124545445.
- ^ S2CID 2514901.
- S2CID 41867048.
- ^ S2CID 681637.
- ^ arXiv:1612.05903 [quant-ph].
- ^ S2CID 125264133.
- S2CID 249538723.
- ISSN 0362-4331. Retrieved 2020-12-07.
- ISSN 0362-4331. Retrieved 2020-12-07.
- ^ a b "On "Quantum Supremacy"". IBM Research Blog. 2019-10-22. Retrieved 2019-10-24.
- ^ Crane, Leah. "IBM says Google may not have reached quantum supremacy after all". New Scientist. Retrieved 2020-12-07.
- ^ Turing, Alan (1936). On Computable Numbers, With An Application To The Entscheidungsproblem.
- S2CID 122949592.
- ^ S2CID 124545445.
- ^ "Quantum Computing". Stanford Encyclopedia of Philosophy. September 30, 2019.
- ^ Shor, Peter (1996). Polynomial-Time Algorithms for Prime Factorization and Discrete Logarithms on a Quantum Computer.
- PMID 10059979.
- arXiv:quant-ph/9605043.
- S2CID 19348964.
- ^ Balaganur, Sameer (2019-11-20). "Man's Race To Quantum Supremacy: The Complete Timeline". Analytics India Magazine. Retrieved 2020-11-16.
- S2CID 4425833.
- ^ Battersby, Stephen (13 April 2012). "Controversial quantum computer beats factoring record". New Scientist. Retrieved 2020-11-16.
- ^ Hardy, Quentin (2013-05-16). "Google Buys a Quantum Computer". Bits Blog. Retrieved 2020-11-16.
- ^ a b Courtland, Rachel (24 May 2017). "Google Plans to Demonstrate the Supremacy of Quantum Computing". IEEE Spectrum. Retrieved 2018-01-11.
- ^ Hsu, Jeremy (8 January 2018). "CES 2018: Intel's 49-Qubit Chip Shoots for Quantum Supremacy". IEEE Spectrum. Retrieved 2017-07-22.
- ^ a b Kim, Mark (October 20, 2017). "Google's quantum computing plans threatened by IBM curveball". New Scientist. Retrieved October 22, 2017.
- ^ Harris, Mark (November 5, 2018). "Google has enlisted NASA to help it prove quantum supremacy within months". MIT Technology Review. Retrieved 2018-11-30.
- ^ S2CID 4167494.
- ^ Hartnett, Kevin (June 18, 2019). "A New Law to Describe Quantum Computing's Rise?". Quanta Magazine.
- ^ [1], Quantum Computing Jobs: Unlocking the Future of Technology, January 2024
- ^ "why is quantum computing useful for optimization problems?". Nowizine. Associated Press.
- ^ "Demonstrating Quantum Supremacy" – via www.youtube.com.
- ^ a b "Quantum Supremacy Using a Programmable Superconducting Processor".
- PMID 31645734.
- ^ "What the Google vs. IBM debate over quantum supremacy means | ZDNet". www.zdnet.com.
- ^ Zialcita, Paolo (23 October 2019). "Google Claims To Achieve Quantum Supremacy — IBM Pushes Back". NPR. Retrieved 2019-10-24.
- S2CID 239036985.
- PMID 35080972.
- S2CID 246910085.
- S2CID 251755796.
- )
- ^ "Google's 'quantum supremacy' usurped by researchers using ordinary supercomputer". TechCrunch. Retrieved 2022-08-07.
- ^ PMID 33273711.
- ^ Garisto, Daniel (December 3, 2020). "Light-based Quantum Computer Exceeds Fastest Classical Supercomputers". Scientific American. Retrieved 2020-12-07.
- ^ Conover, Emily (2020-12-03). "The new light-based quantum computer Jiuzhang has achieved quantum supremacy". Science News. Retrieved 2020-12-07.
- S2CID 235669908.
- ^ Johnston, Hamish (26 October 2021). "Quantum advantage takes a giant leap in optical and superconducting systems". Physics World. Retrieved 2021-10-27.
- S2CID 235658633.
- S2CID 235669908.
- S2CID 244826882.
- S2CID 237442167.
- S2CID 249277681.
- PMID 35650354.
- Bibcode:2000qcqi.book..103C.
- ^ S2CID 1380135.
- ^ ].
- arXiv:cs/0409051.
- arXiv:cs/0409051.
- ^ S2CID 54628108.
- S2CID 55999387.
- S2CID 8590553.
- ^ Jordan, Stephen. "Quantum Algorithm Zoo". math.nist.gov. Archived from the original on 2018-04-29. Retrieved 2017-07-29.
- ^ ISSN 0036-1445.
- arXiv:math/0610612.
- S2CID 9052772.
- S2CID 2873616.
- S2CID 46546101.
- S2CID 119277773.
- S2CID 23490704.
- S2CID 19067232.
- ^ arXiv:1706.01260 [cs.DS].
- ^ S2CID 73635825.
- .
- arXiv:1710.05867 [quant-ph].
- ^ "Quantum Supremacy Using a Programmable Superconducting Processor". Google AI Blog. Retrieved 2019-11-02.
- ^ Metz, Cade (23 October 2019). "Google Claims a Quantum Breakthrough That Could Change Computing". The New York Times. Retrieved 14 January 2020.
- arXiv:1910.09534 [quant-ph].
- ^ "Google and IBM Clash Over Quantum Supremacy Claim". Quanta Magazine. 23 October 2019. Retrieved 2020-10-29.
- ^ ].
- PMID 9912632.
- PMID 10062908.
- arXiv:quant-ph/9906129.
- S2CID 4420858.
- arXiv:1605.00992 [quant-ph].
- Bibcode:2006quant.ph.10117D.
- ^ Board, The Editorial (17 December 2019). "Opinion | Achieving Quantum Wokeness". Wall Street Journal. Retrieved 2019-12-21.
- ISSN 0307-1235. Retrieved 2019-12-21.
- PMID 31822842.
- ^ "Open Letter – Responsibility in Quantum Science".
- S2CID 227282052. Retrieved 16 December 2020.