quantum supremacy

In 1936, Alan Turing published his paper, “On Computable Numbers”,{{Cite book|last=Turing|first=Alan|title=On Computable Numbers, With An Application To The Entscheidungsproblem|year=1936}} 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“,{{Cite journal|last=Benioff|first=Paul|date=1980-05-01|title=The computer as a physical system: A microscopic quantum mechanical Hamiltonian model of computers as represented by Turing machines|url=https://doi.org/10.1007/BF01011339|journal=Journal of Statistical Physics|language=en|volume=22|issue=5|pages=563–591|doi=10.1007/BF01011339|bibcode=1980JSP....22..563B|s2cid=122949592|issn=1572-9613}} 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.{{Cite journal|last=Feynman|first=Richard P.|date=1982-06-01|title=Simulating physics with computers|url=https://doi.org/10.1007/BF02650179|journal=International Journal of Theoretical Physics|language=en|volume=21|issue=6|pages=467–488|doi=10.1007/BF02650179|bibcode=1982IJTP...21..467F|s2cid=124545445|issn=1572-9575}} 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.” Soon after this, David Deutsch produced a description for a quantum Turing machine and designed an algorithm created to run on a quantum computer.{{cite web|date=September 30, 2019|title=Quantum Computing|url=https://plato.stanford.edu/entries/qt-quantcomp/|website=Stanford Encyclopedia of Philosophy}}

In 1994, further progress toward quantum supremacy was made when Peter Shor formulated Shor's algorithm, streamlining a method for factoring integers in polynomial time.{{Cite book|last=Shor|first=Peter|title=Polynomial-Time Algorithms for Prime Factorization and Discrete Logarithms on a Quantum Computer|year=1996}} In 1995, Christopher Monroe and David Wineland published their paper, “Demonstration of a Fundamental Quantum Logic Gate”,{{Cite journal|last1=Monroe|first1=C.|last2=Meekhof|first2=D. M.|last3=King|first3=B. E.|last4=Itano|first4=W. M.|last5=Wineland|first5=D. J.|date=1995-12-18|title=Demonstration of a Fundamental Quantum Logic Gate|journal=Physical Review Letters|language=en|volume=75|issue=25|pages=4714–4717|doi=10.1103/PhysRevLett.75.4714|pmid=10059979|bibcode=1995PhRvL..75.4714M|issn=0031-9007|doi-access=free}} marking the first demonstration of a quantum logic gate, specifically the two-bit "controlled-NOT". In 1996, Lov Grover put into motion an interest in fabricating a quantum computer after publishing his algorithm, Grover's Algorithm, in his paper, “A fast quantum mechanical algorithm for database search”.{{cite arXiv|last=Grover|first=Lov K.|date=1996-11-19|title=A fast quantum mechanical algorithm for database search|eprint=quant-ph/9605043}} In 1998, Jonathan A. Jones and Michele Mosca published “Implementation of a Quantum Algorithm to Solve Deutsch's Problem on a Nuclear Magnetic Resonance Quantum Computer”,{{Cite journal|last1=Jones|first1=J. A.|last2=Mosca|first2=M.|date=August 1998|title=Implementation of a Quantum Algorithm to Solve Deutsch's Problem on a Nuclear Magnetic Resonance Quantum Computer|journal=The Journal of Chemical Physics|volume=109|issue=5|pages=1648–1653|doi=10.1063/1.476739|arxiv=quant-ph/9801027|s2cid=19348964|issn=0021-9606}} marking the first demonstration of a quantum algorithm.

{{See also|Quantum computing#Quantum supremacy}}

Vast progress toward quantum supremacy was made in the 2000s from the first 5-qubit nuclear magnetic resonance computer (2000), the demonstration of Shor's theorem (2001), and the implementation of Deutsch's algorithm in a clustered quantum computer (2007).{{Cite web|last=Balaganur|first=Sameer|date=2019-11-20|title=Man's Race To Quantum Supremacy: The Complete Timeline|url=https://analyticsindiamag.com/race-quantum-supremacy-complete-timeline/|access-date=2020-11-16|website=Analytics India Magazine|language=en-US}} In 2011, D-Wave Systems of Burnaby, British Columbia, Canada became the first company to sell a quantum computer commercially.{{Cite journal|last=Merali|first=Zeeya|date=June 2011|title=First sale for quantum computing|journal=Nature|language=en|volume=474|issue=7349|pages=18|doi=10.1038/474018a|pmid=21637232|bibcode=2011Natur.474...18M|s2cid=4425833|issn=0028-0836|doi-access=free}} In 2012, physicist Nanyang Xu landed a milestone accomplishment by using an improved adiabatic factoring algorithm to factor 143. However, the methods used by Xu were met with objections.{{Cite web|last=Battersby|first=Stephen|title=Controversial quantum computer beats factoring record|url=https://www.newscientist.com/article/dn21699-controversial-quantum-computer-beats-factoring-record/ |work=New Scientist |date=13 April 2012 |access-date=2020-11-16|language=en-US}} Not long after this accomplishment, Google purchased its first quantum computer.{{Cite web|last=Hardy|first=Quentin|date=2013-05-16|title=Google Buys a Quantum Computer|url=https://bits.blogs.nytimes.com/2013/05/16/google-buys-a-quantum-computer/|access-date=2020-11-16|website=Bits Blog|language=en-US}}

Google had announced plans to demonstrate quantum supremacy before the end of 2017 with an array of 49 superconducting qubits.{{Cite news |url=https://spectrum.ieee.org/google-plans-to-demonstrate-the-supremacy-of-quantum-computing |title=Google Plans to Demonstrate the Supremacy of Quantum Computing |work=IEEE Spectrum |first=Rachel |last=Courtland |date=24 May 2017 |access-date=2018-01-11}} In early January 2018, Intel announced a similar hardware program.{{Cite news |url=https://spectrum.ieee.org/intels-49qubit-chip-aims-for-quantum-supremacy |title=CES 2018: Intel's 49-Qubit Chip Shoots for Quantum Supremacy |work=IEEE Spectrum |first=Jeremy |last=Hsu |date=8 January 2018|access-date=2017-07-22 }} In October 2017, IBM demonstrated the simulation of 56 qubits on a classical supercomputer, thereby increasing the computational power needed to establish quantum supremacy.{{cite web |url=https://www.newscientist.com/article/2151032-googles-quantum-computing-plans-threatened-by-ibm-curveball/ |title=Google's quantum computing plans threatened by IBM curveball |date=October 20, 2017 |work=New Scientist |first=Mark |last=Kim |access-date=October 22, 2017}} In November 2018, Google announced a partnership with NASA that would "analyze results from quantum circuits run on Google quantum processors, and ... provide comparisons with classical simulation to both support Google in validating its hardware and establish a baseline for quantum supremacy."{{Cite news|url=https://www.technologyreview.com/s/612381/google-has-enlisted-nasa-to-help-it-prove-quantum-supremacy-within-months/|title=Google has enlisted NASA to help it prove quantum supremacy within months|last=Harris|first=Mark|work=MIT Technology Review |date=November 5, 2018 |access-date=2018-11-30}} Theoretical work published in 2018 suggested that quantum supremacy should be possible with a "two-dimensional lattice of 7×7 qubits and around 40 clock cycles" if error rates can be pushed low enough.{{cite journal |last1=Boixo |first1=Sergio |last2=Isakov |first2=Sergei V. |last3=Smelyanskiy |first3=Vadim N. |last4=Babbush |first4=Ryan |last5=Ding |first5=Nan |last6=Jiang |first6=Zhang |last7=Bremner |first7=Michael J. |last8=Martinis |first8=John M. |last9=Neven |first9=Hartmut |title=Characterizing quantum supremacy in near-term devices |journal=Nature Physics |date=23 April 2018 |volume=14 |issue=6 |pages=595–600 |doi=10.1038/s41567-018-0124-x|arxiv=1608.00263 |bibcode=2018NatPh..14..595B |s2cid=4167494 }} The scheme discussed was a variant of a quantum random sampling scheme in which qubits undergo random quantum circuits featuring quantum gates drawn from a universal gate set, followed by measurements in the computational basis.

On June 18, 2019, Quanta Magazine suggested that quantum supremacy could happen in 2019, according to Neven's law.{{cite web|url=https://www.quantamagazine.org/does-nevens-law-describe-quantum-computings-rise-20190618/ |title=A New Law to Describe Quantum Computing's Rise?|website=Quanta Magazine|date=June 18, 2019 |last=Hartnett |first=Kevin}} On September 20, 2019, the Financial Times reported that "Google claims to have reached quantum supremacy with an array of 54 qubits out of which 53 were functional, which were used to perform a series of operations in 200 seconds that would take a supercomputer about 10,000 years to complete".[https://www.ft.com/content/b9bb4e54-dbc1-11e9-8f9b-77216ebe1f17], Financial Times, September 2019 {{subscription required}}{{Cite web|url=https://www.marketwatch.com/story/google-touts-quantum-computing-milestone-2019-10-23|title=Google touts quantum computing milestone|agency=Associated Press|website=MarketWatch}} On October 23, Google officially confirmed the claims.{{Cite web|url=https://www.youtube.com/watch?v=-ZNEzzDcllU|title=Demonstrating Quantum Supremacy|via=www.youtube.com}}{{Cite web|url=http://ai.googleblog.com/2019/10/quantum-supremacy-using-programmable.html|title=Quantum Supremacy Using a Programmable Superconducting Processor}}{{cite journal |author=Arute, Frank |display-authors=et al. |title=Quantum supremacy using a programmable superconducting processor |date=23 October 2019 |journal=Nature |volume=574 |issue=7779 |pages=505–510 |doi=10.1038/s41586-019-1666-5 |pmid=31645734 |arxiv=1910.11333 |doi-access=free |bibcode=2019Natur.574..505A }} IBM responded by suggesting some of the claims were excessive and suggested that it could take 2.5 days instead of 10,000 years, listing techniques that a classical supercomputer may use to maximize computing speed. IBM's response is relevant as the most powerful supercomputer at the time, Summit, was made by IBM.{{Cite web|url=https://www.zdnet.com/article/what-the-google-v-ibm-debate-over-quantum-means/|title=What the Google vs. IBM debate over quantum supremacy means|website=ZDNet}}{{Cite web|url=https://www.ibm.com/blogs/research/2019/10/on-quantum-supremacy/|title=On "Quantum Supremacy"|date=2019-10-22|website=IBM Research Blog|access-date=2019-10-24}}{{Cite news|url=https://www.npr.org/2019/10/23/772710977/google-claims-to-achieve-quantum-supremacy-ibm-pushes-back|title=Google Claims To Achieve Quantum Supremacy — IBM Pushes Back|newspaper=NPR|date=23 October 2019|access-date=2019-10-24|last1=Zialcita|first1=Paolo}} Researchers have since developed better algorithms for the sampling problem used to claim quantum supremacy, giving substantial reductions to the gap between Google's Sycamore processor and classical supercomputers{{Cite book |last1=Liu |first1=Yong (Alexander) |title=Proceedings of the International Conference for High Performance Computing, Networking, Storage and Analysis |last2=Liu |first2=Xin (Lucy) |last3=Li |first3=Fang (Nancy) |last4=Fu |first4=Haohuan |last5=Yang |first5=Yuling |last6=Song |first6=Jiawei |last7=Zhao |first7=Pengpeng |last8=Wang |first8=Zhen |last9=Peng |first9=Dajia |date=2021-11-14 |publisher=Association for Computing Machinery |isbn=978-1-4503-8442-1 |series=SC '21 |location=New York, New York, United States |pages=1–12 |language=en-us |chapter=Closing the "quantum supremacy" gap |doi=10.1145/3458817.3487399 |chapter-url=https://doi.org/10.1145/3458817.3487399 |last10=Chen |first10=Huarong |last11=Guo |first11=Chu |arxiv=2110.14502 |s2cid=239036985}}{{Cite journal |last1=Bulmer |first1=Jacob F. F. |last2=Bell |first2=Bryn A. |last3=Chadwick |first3=Rachel S. |last4=Jones |first4=Alex E. |last5=Moise |first5=Diana |last6=Rigazzi |first6=Alessandro |last7=Thorbecke |first7=Jan |last8=Haus |first8=Utz-Uwe |last9=Van Vaerenbergh |first9=Thomas |last10=Patel |first10=Raj B. |last11=Walmsley |first11=Ian A. |date=2022-01-28 |title=The boundary for quantum advantage in Gaussian boson sampling |journal=Science Advances |language=en |volume=8 |issue=4 |pages=eabl9236 |doi=10.1126/sciadv.abl9236 |issn=2375-2548 |pmc=8791606 |pmid=35080972|arxiv=2108.01622 |bibcode=2022SciA....8.9236B }}{{Cite journal |last=McCormick |first=Katie |date=2022-02-10 |title=Race Not Over Between Classical and Quantum Computers |url=https://physics.aps.org/articles/v15/19 |journal=Physics |language=en |volume=15|page=19 |doi=10.1103/Physics.15.19 |bibcode=2022PhyOJ..15...19M |s2cid=246910085 |doi-access=free }} and even beating it.{{Cite journal |title=Solving the Sampling Problem of the Sycamore Quantum Circuits |url=https://journals.aps.org/prl/accepted/f9079Kc7Yd613a0ec6447153516a99a03ca737793 |access-date= |journal=Physical Review Letters |year=2022 |doi=10.1103/PhysRevLett.129.090502 |arxiv=2111.03011|last1=Pan |first1=Feng |last2=Chen |first2=Keyang |last3=Zhang |first3=Pan |volume=129 |issue=9 |page=090502 |pmid=36083655 |bibcode=2022PhRvL.129i0502P |s2cid=251755796 }}{{Cite journal |date=2022-08-02 |title=Ordinary computers can beat Google's quantum computer after all |url=https://www.science.org/content/article/ordinary-computers-can-beat-google-s-quantum-computer-after-all |language=en |doi=10.1126/science.ade2364}}{{Cite web |title=Google's 'quantum supremacy' usurped by researchers using ordinary supercomputer |url=https://techcrunch.com/2022/08/05/googles-quantum-supremacy-usurped-by-researchers-using-ordinary-supercomputer/ |access-date=2022-08-07 |website=TechCrunch |language=en-US}}

In December 2020, a group based in the University of Science and Technology of China (USTC) led by Pan Jianwei reached quantum supremacy by implementing gaussian boson sampling on 76 photons with their photonic quantum computer Jiuzhang.{{Cite journal|last=Ball|first=Philip|date=2020-12-03|title=Physicists in China challenge Google's 'quantum advantage'|journal=Nature|volume=588|issue=7838|page=380|language=en|doi=10.1038/d41586-020-03434-7|pmid=33273711|bibcode=2020Natur.588..380B|doi-access=}}{{Cite web|last=Garisto|first=Daniel |date=December 3, 2020 |title=Light-based Quantum Computer Exceeds Fastest Classical Supercomputers|url=https://www.scientificamerican.com/article/light-based-quantum-computer-exceeds-fastest-classical-supercomputers/|access-date=2020-12-07|website=Scientific American|language=en}}{{Cite web|last=Conover|first=Emily|date=2020-12-03|title=The new light-based quantum computer Jiuzhang has achieved quantum supremacy|url=https://www.sciencenews.org/article/new-light-based-quantum-computer-jiuzhang-supremacy|access-date=2020-12-07|website=Science News|language=en-US}} The paper states that to generate the number of samples the quantum computer generates in 200 seconds, a classical supercomputer would require 2.5 billion years of computation.{{Cite journal|last1=Zhong|first1=Han-Sen|last2=Wang|first2=Hui|last3=Deng|first3=Yu-Hao|last4=Chen|first4=Ming-Cheng|last5=Peng|first5=Li-Chao|last6=Luo|first6=Yi-Han|last7=Qin|first7=Jian|last8=Wu|first8=Dian|last9=Ding|first9=Xing|last10=Hu|first10=Yi|last11=Hu|first11=Peng|date=2020-12-03|title=Quantum computational advantage using photons|url=https://www.science.org/doi/10.1126/science.abe8770|journal=Science|volume=370|issue=6523|pages=1460–1463|language=en|doi=10.1126/science.abe8770|issn=0036-8075|pmid=33273064|arxiv=2012.01625|bibcode=2020Sci...370.1460Z|s2cid=227254333}}

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 {{val|e=24}} – a difference of 37 photons and 10 orders of magnitude over the previous Jiuzhang.{{Cite journal|last1=Zhong|first1=Han-Sen|last2=Deng|first2=Yu-Hao|last3=Qin|first3=Jian|last4=Wang|first4=Hui|last5=Chen|first5=Ming-Cheng|last6=Peng|first6=Li-Chao|last7=Luo|first7=Yi-Han|last8=Wu|first8=Dian|last9=Gong|first9=Si-Qiu|last10=Su|first10=Hao|last11=Hu|first11=Yi|date=2021-10-25|title=Phase-Programmable Gaussian Boson Sampling Using Stimulated Squeezed Light|url=https://link.aps.org/doi/10.1103/PhysRevLett.127.180502|journal=Physical Review Letters|volume=127|issue=18|pages=180502|doi=10.1103/PhysRevLett.127.180502|pmid=34767431|arxiv=2106.15534|bibcode=2021PhRvL.127r0502Z|s2cid=235669908}}{{Cite web|date=26 October 2021 |first=Hamish |last=Johnston|title=Quantum advantage takes a giant leap in optical and superconducting systems|url=https://physicsworld.com/quantum-advantage-takes-a-giant-leap-in-optical-and-superconducting-systems/|access-date=2021-10-27|work=Physics World|language=en-GB}} 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.{{Cite journal|last1=Wu|first1=Yulin|last2=Bao|first2=Wan-Su|last3=Cao|first3=Sirui|last4=Chen|first4=Fusheng|last5=Chen|first5=Ming-Cheng|last6=Chen|first6=Xiawei|last7=Chung|first7=Tung-Hsun|last8=Deng|first8=Hui|last9=Du|first9=Yajie|last10=Fan|first10=Daojin|last11=Gong|first11=Ming|date=2021-10-25|title=Strong Quantum Computational Advantage Using a Superconducting Quantum Processor|url=https://link.aps.org/doi/10.1103/PhysRevLett.127.180501|journal=Physical Review Letters|volume=127|issue=18|pages=180501|doi=10.1103/PhysRevLett.127.180501|pmid=34767433|arxiv=2106.14734|bibcode=2021PhRvL.127r0501W|s2cid=235658633}}{{cite journal |last1=Zhong |first1=Han-Sen |last2=Deng |first2=Yu-Hao |last3=Qin |first3=Jian |last4=Wang |first4=Hui |last5=Chen |first5=Ming-Cheng |last6=Peng |first6=Li-Chao |last7=Luo |first7=Yi-Han |last8=Wu |first8=Dian |last9=Gong |first9=Si-Qiu |last10=Su |first10=Hao |last11=Hu |first11=Yi |last12=Hu |first12=Peng |last13=Yang |first13=Xiao-Yan |last14=Zhang |first14=Wei-Jun |last15=Li |first15=Hao |last16=Li |first16=Yuxuan |last17=Jiang |first17=Xiao |last18=Gan |first18=Lin |last19=Yang |first19=Guangwen |last20=You |first20=Lixing |last21=Wang |first21=Zhen |last22=Li |first22=Li |last23=Liu |first23=Nai-Le |last24=Renema |first24=Jelmer J. |last25=Lu |first25=Chao-Yang |last26=Pan |first26=Jian-Wei |title=Phase-Programmable Gaussian Boson Sampling Using Stimulated Squeezed Light |journal=Physical Review Letters |date=25 October 2021 |volume=127 |issue=18 |pages=180502 |doi=10.1103/PhysRevLett.127.180502|pmid=34767431 |arxiv=2106.15534 |bibcode=2021PhRvL.127r0502Z |s2cid=235669908 }}{{Cite journal|last=Sanders|first=Barry C.|date=2021-10-25|title=Quantum Leap for Quantum Primacy|url=https://physics.aps.org/articles/v14/147|journal=Physics|language=en|volume=14|page=147|doi=10.1103/Physics.14.147|bibcode=2021PhyOJ..14..147S|s2cid=244826882|doi-access=free}} 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".{{cite journal |author=Qingling Zhu, Sirui Cao |display-authors=et al. |title=Quantum computational advantage via 60-qubit 24-cycle random circuit sampling |journal=Science Bulletin |date=25 October 2021 |volume=67 |issue=3 |pages=240–245 |doi=10.1016/j.scib.2021.10.017 |pmid=36546072 |arxiv=2109.03494 |s2cid=237442167 |language=en |issn=2095-9273}}

In June 2022, Xanadu reported 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 photons 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 more than previous experiments.{{Cite journal |last=Brod |first=Daniel Jost |date=1 June 2022 |title=Loops simplify a set-up to boost quantum computational advantage |url=https://www.nature.com/articles/d41586-022-01402-x |journal=Nature |language=en |volume=606 |issue=7912 |pages=31–32 |doi=10.1038/d41586-022-01402-x|pmid=35650360 |bibcode=2022Natur.606...31B |s2cid=249277681 }}{{Cite journal |last1=Madsen |first1=Lars S. |last2=Laudenbach |first2=Fabian |last3=Askarani |first3=Mohsen Falamarzi |last4=Rortais |first4=Fabien |last5=Vincent |first5=Trevor |last6=Bulmer |first6=Jacob F. F. |last7=Miatto |first7=Filippo M. |last8=Neuhaus |first8=Leonhard |last9=Helt |first9=Lukas G. |last10=Collins |first10=Matthew J. |last11=Lita |first11=Adriana E. |date=1 June 2022 |title=Quantum computational advantage with a programmable photonic processor |journal=Nature |language=en |volume=606 |issue=7912 |pages=75–81 |doi=10.1038/s41586-022-04725-x |pmid=35650354 |pmc=9159949 |bibcode=2022Natur.606...75M |issn=1476-4687}}

In March of 2024, D-Wave Systems reported on an experiment using a quantum annealing based processor that out-performed classical methods including tensor networks and neural networks. They argued that no known classical approach could yield the same results as the quantum simulation within a reasonable time-frame and claimed quantum supremacy. The task performed was the simulation of the non-equilibrium dynamics of a magnetic spin system quenched through a quantum phase transition.{{Cite arXiv |first1=Andrew |last1=King |first2=Alberto |last2=Nocera |first3=Marek |last3=Rams |first4=Jacek |last4=Dziarmaga |first5=Roeland |last5=Wiersema |first6=William |last6=Bernoudy |first7=Jack |last7=Raymond |first8=Nitin |last8=Kaushal |first9=Niclas |last9=Heinsdorf |first10=Richard |last10=Harris |first11=Kelly |last11=Boothby |first12=Fabio |last12=Altomare |first13=Andrew |last13=Berkley |first14=Martin |last14=Boschnak |first15=Kevin |last15=Chern |first16=Holly |last16=Christiani |first17=Samantha |last17=Cibere |first18=Jake |last18=Connor |first19=Martin |last19=Dehn |first20=Rahul |last20=Deshpande |first21=Sara |last21=Ejtemaee |first22=Pau |last22=Farré |first23=Kelsey |last23=Hamer |first24=Emile |last24=Hoskinson |first25=Shuiyuan |last25=Huang |first26=Mark |last26=Johnson |first27=Samuel |last27=Kortas |first28=Eric |last28=Ladizinsky |first29=Tony |last29=Lai |first30=Trevor |last30=Lanting |first31=Ryan |last31=Li |first32=Allison |last32=MacDonald |first33=Gaelen |last33=Marsden |first34=Catherine |last34=McGeoch |first35=Reza |last35=Molavi |first36=Richard |last36=Neufeld |first37=Mana |last37=Norouzpour |first38=Travis |last38=Oh |first39=Joel |last39=Pasvolsky |first40=Patrick |last40=Poitras |first41=Gabriel |last41=Poulin-Lamarre |first42=Thomas |last42=Prescott |first43=Mauricio |last43=Reis |first44=Chris |last44=Rich |first45=Mohammad |last45=Samani |first46=Benjamin |last46=Sheldan |first47=Anatoly |last47=Smirnov |first48=Edward |last48=Sterpka |first49=Berta |last49=Trullas Clavera |first50=Nicholas |last50=Tsai |first51=Mark |last51=Volkmann |first52=Alexander |last52=Whiticar |first53=Jed |last53=Whittaker |first54=Warren |last54=Wilkinson |first55=Jason |last55=Yao |first56=T.J. |last56=Yi |first57=Anders |last57=Sandvik |first58=Gonzalo |last58=Alvarez |first59=Roger |last59=Melko |first60=Juan |last60=Carrasquilla |first61=Marcel |last61=Franz |first62=Mohammad |last62=Amin |date=1 March 2024 |title=Computational supremacy in quantum simulation |eprint=2403.00910v1 |language=en}}

{{Main|Quantum complexity theory}}

Complexity arguments concern how the amount of some resource needed to solve a problem (generally time or memory) scales with the size of the input. In this setting, a problem consists of an inputted problem instance (a binary string) and returned solution (corresponding output string), while resources refers to designated elementary operations, memory usage, or communication. A collection of local operations allows for the computer to generate the output string. A circuit model and its corresponding operations are useful in describing both classical and quantum problems; the classical circuit model consists of basic operations such as AND gates, OR gates, and NOT gates while the quantum model consists of classical circuits and the application of unitary operations. Unlike the finite set of classical gates, there are an infinite amount of quantum gates due to the continuous nature of unitary operations. In both classical and quantum cases, complexity swells with increasing problem size.{{Cite journal|last=Cleve|first=Richard|title=An Introduction to Quantum Complexity Theory|url=https://cds.cern.ch/record/392006/files/9906111.pdf|journal=CERN|year=2000|bibcode=2000qcqi.book..103C}} As an extension of classical computational complexity theory, quantum complexity theory considers what a theoretical universal quantum computer could accomplish without accounting for the difficulty of building a physical quantum computer or dealing with decoherence and noise.{{Cite book |title=Encyclopedia of Complexity and Systems Science |url=https://archive.org/details/encyclopediacomp00meye |url-access=limited |last=Watrous |first=John |date=2009 |publisher=Springer New York |isbn=9780387758886 |editor-last=Meyers |editor-first=Robert A. |pages=[https://archive.org/details/encyclopediacomp00meye/page/n3382 7174]–7201 |doi=10.1007/978-0-387-30440-3_428|chapter = Quantum Computational Complexity|s2cid=1380135 }} Since quantum information is a generalization of classical information, quantum computers can simulate any classical algorithm.

Quantum complexity classes are sets of problems that share a common quantum computational model, with each model containing specified resource constraints. Circuit models are useful in describing quantum complexity classes.{{cite arXiv|last=Watrous|first=John|date=April 21, 2018|title=Quantum Computational Complexity|class=quant-ph|eprint=0804.3401}} The most useful quantum complexity class is BQP (bounded-error quantum polynomial time), the class of decision problems that can be solved in polynomial time by a universal quantum computer. Questions about BQP still remain, such as the connection between BQP and the polynomial-time hierarchy, whether or not BQP contains NP-complete problems, and the exact lower and upper bounds of the BQP class. Not only would answers to these questions reveal the nature of BQP, but they would also answer difficult classical complexity theory questions. One strategy for better understanding BQP is by defining related classes, ordering them into a conventional class hierarchy, and then looking for properties that are revealed by their relation to BQP.{{cite arXiv|last=Tušarová|first=Tereza|title=Quantum complexity classes|year=2004|eprint=cs/0409051}} There are several other quantum complexity classes, such as QMA (quantum Merlin Arthur) and QIP (quantum interactive polynomial time).

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.{{Cite journal |last1=Lund |first1=A. P. |last2=Bremner |first2=Michael J. |last3=Ralph |first3=T. C. |date=2017-04-13 |title=Quantum sampling problems, BosonSampling and quantum supremacy |journal=npj Quantum Information |volume=3 |issue=1 |page=15 |doi=10.1038/s41534-017-0018-2 |issn=2056-6387 |bibcode=2017npjQI...3...15L |arxiv=1702.03061|s2cid=54628108 }} 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. 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.{{Cite book |last1=Gard |first1=Bryan T. |last2=Motes |first2=Keith R. |last3=Olson |first3=Jonathan P. |last4=Rohde |first4=Peter P. |last5=Dowling |first5=Jonathan P. |date=August 2015 |chapter=An introduction to boson-sampling |title=From Atomic to Mesoscale: the Role of Quantum Coherence in Systems of Various Complexities |publisher=World Scientific |isbn=978-981-4678-70-4 |arxiv=1406.6767 |pages=167–192 |doi=10.1142/9789814678704_0008|s2cid=55999387 }} The arguments used to reach this conclusion have been extended to IQP Sampling,{{Cite journal |last1=Bremner |first1=Michael J. |last2=Montanaro |first2=Ashley |last3=Shepherd |first3=Dan J. |date=2016-08-18 |title=Average-case complexity versus approximate simulation of commuting quantum computations |journal=Physical Review Letters |volume=117 |issue=8 |page=080501 |doi=10.1103/PhysRevLett.117.080501 |pmid=27588839 |issn=0031-9007 |arxiv=1504.07999 |bibcode=2016PhRvL.117h0501B|s2cid=8590553 }} where only the conjecture that the average- and worst-case complexities of the problem are the same is needed, as well as to Random Circuit Sampling, which is the task replicated by the Google and USTC research groups.

The following are proposals for demonstrating quantum computational supremacy using current technology, often called NISQ devices. Such proposals include (1) a well-defined computational problem, (2) a quantum algorithm to solve this problem, (3) a comparison best-case classical algorithm to solve the problem, and (4) a complexity-theoretic argument that, under a reasonable assumption, no classical algorithm can perform significantly better than current algorithms (so the quantum algorithm still provides a superpolynomial speedup).{{Cite web |url=http://math.nist.gov/quantum/zoo/ |title=Quantum Algorithm Zoo |last=Jordan |first=Stephen |website=math.nist.gov |access-date=2017-07-29 |archive-url=https://web.archive.org/web/20180429014516/https://math.nist.gov/quantum/zoo/ |archive-date=2018-04-29 |url-status=dead }}

{{Main|Shor's algorithm}}

This algorithm finds the prime factorization of an n-bit integer in $\backslash tilde\{O\}\; (n^3)$ time{{Cite journal|last=Shor|first=P.|date=1999-01-01|title=Polynomial-Time Algorithms for Prime Factorization and Discrete Logarithms on a Quantum Computer|journal=SIAM Review|volume=41|issue=2|pages=303–332|arxiv=quant-ph/9508027|bibcode=1999SIAMR..41..303S|doi=10.1137/S0036144598347011|issn=0036-1445}} whereas the best known classical algorithm requires $2^\{O(n^\{1/3\})\}$time and the best upper bound for the complexity of this problem is $O(2^\{n/3+o(1)\})$.{{cite arXiv |last=Rubinstein |first=Michael |date=2006-10-19 |title=The distribution of solutions to xy = N mod a with an application to factoring integers|eprint=math/0610612}} It can also provide a speedup for any problem that reduces to integer factoring, including the membership problem for matrix groups over fields of odd order.{{Cite book |last1=Babai |first1=László |title=Proceedings of the forty-first annual ACM symposium on Theory of computing |last2=Beals |first2=Robert |last3=Seress |first3=Ákos |date=2009 |publisher=Association for Computing Machinery |isbn=9781605585062 |series=STOC '09 |location=New York, New York, United States |pages=55–64 |language=en-us |chapter=Polynomial-time theory of matrix groups |citeseerx=10.1.1.674.9429 |doi=10.1145/1536414.1536425 |s2cid=9052772}}

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. Namely, it gives a superpolynomial speedup under the reasonable assumption that RSA, a well-established cryptosystem, is secure.{{Cite journal|last1=Rivest|first1=R. L.|last2=Shamir|first2=A.|last3=Adleman|first3=L.|date=February 1978|title=A Method for Obtaining Digital Signatures and Public-key Cryptosystems|journal=Commun. ACM|volume=21|issue=2|pages=120–126|doi=10.1145/359340.359342|issn=0001-0782|citeseerx=10.1.1.607.2677|s2cid=2873616}}

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,{{Cite journal|last1=Martín-López|first1=Enrique|last2=Laing|first2=Anthony|last3=Lawson|first3=Thomas|last4=Alvarez|first4=Roberto|last5=Zhou|first5=Xiao-Qi|last6=O'Brien|first6=Jeremy L.|date=November 2012|title=Experimental realization of Shor's quantum factoring algorithm using qubit recycling|journal=Nature Photonics|volume=6|issue=11|pages=773–776|doi=10.1038/nphoton.2012.259|issn=1749-4893|arxiv=1111.4147|bibcode=2012NaPho...6..773M|s2cid=46546101}}{{Cite journal|last1=Fowler|first1=Austin G.|last2=Mariantoni|first2=Matteo|last3=Martinis|first3=John M.|last4=Cleland|first4=Andrew N.|date=2012-09-18|title=Surface codes: Towards practical large-scale quantum computation|journal=Physical Review A|volume=86|issue=3|pages=032324|doi=10.1103/PhysRevA.86.032324|arxiv=1208.0928|bibcode=2012PhRvA..86c2324F|s2cid=119277773}} so it is not being pursued as a strategy for demonstrating supremacy.

{{Main|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. However, it has been shown that boson sampling in a system with large enough loss and noise can be simulated efficiently.{{Cite journal|last1=Rahimi-Keshari|first1=Saleh|last2=Ralph|first2=Timothy C.|last3=Caves|first3=Carlton M.|date=2016-06-20|title=Sufficient Conditions for Efficient Classical Simulation of Quantum Optics|journal=Physical Review X|volume=6|issue=2|pages=021039|doi=10.1103/PhysRevX.6.021039|bibcode=2016PhRvX...6b1039R|arxiv=1511.06526|s2cid=23490704}}

The largest experimental implementation of boson sampling to date had 6 modes so could handle up to 6 photons at a time.{{Cite journal |last1=Carolan |first1=Jacques |last2=Harrold |first2=Christopher |last3=Sparrow |first3=Chris |last4=Martín-López |first4=Enrique |last5=Russell |first5=Nicholas J. |last6=Silverstone |first6=Joshua W. |last7=Shadbolt |first7=Peter J. |last8=Matsuda |first8=Nobuyuki |last9=Oguma |first9=Manabu |date=2015-08-14 |title=Universal linear optics |journal=Science |volume=349 |issue=6249 |pages=711–716 |doi=10.1126/science.aab3642 |issn=0036-8075 |pmid=26160375|arxiv=1505.01182 |s2cid=19067232 }} The best proposed classical algorithm for simulating boson sampling runs in time $O(n2^n+mn^2)$ for a system with n photons and m output modes.{{cite arXiv |last1=Clifford |first1=Peter |last2=Clifford |first2=Raphaël |date=2017-06-05 |title=The Classical Complexity of Boson Sampling |eprint=1706.01260 |class=cs.DS}}{{Cite journal|last1=Neville|first1=Alex|last2=Sparrow|first2=Chris|last3=Clifford|first3=Raphaël|last4=Johnston|first4=Eric|last5=Birchall|first5=Patrick M.|last6=Montanaro|first6=Ashley|last7=Laing|first7=Anthony|date=2017-10-02|title=No imminent quantum supremacy by boson sampling|journal=Nature Physics|volume=13|issue=12|pages=1153–1157|doi=10.1038/nphys4270|issn=1745-2473|arxiv=1705.00686|bibcode=2017arXiv170500686N|s2cid=73635825 }} The algorithm leads to an estimate of 50 photons required to demonstrate quantum supremacy with boson sampling.

{{main|Cross-entropy benchmarking}}

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. Bouland, Fefferman, Nirkhe and Vazirani 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. The largest universal quantum circuit simulator running on classical supercomputers at the time was able to simulate 48 qubits.{{cite journal |author1=De Raedt |first=Hans |author2=Jin |first2=Fengping |author3=Willsch |first3=Dennis |author4=Willsch |first4=Madita |author5=Yoshioka |first5=Naoki |author6=Ito |first6=Nobuyasu |author7=Yuan |first7=Shengjun |author8=Michielsen |first8=Kristel |date=November 2018 |title=Massively parallel quantum computer simulator, eleven years later |journal=Computer Physics Communications |volume=237 |pages=47–61 |arxiv=1805.04708 |doi=10.1016/j.cpc.2018.11.005 |doi-access=free}} But for particular kinds of circuits, larger quantum circuit simulations with 56 qubits are possible.{{cite arXiv |eprint=1710.05867 |class=quant-ph |first=Edwin |last=Pednault |author2=John A. Gunnels |title=Breaking the 49-Qubit Barrier in the Simulation of Quantum Circuits |date=October 2017 |author3=Giacomo Nannicini |author4=Lior Horesh |author5=Thomas Magerlein |author6=Edgar Solomonik |author7=Robert Wisnieff}} This may require increasing the number of qubits to demonstrate quantum supremacy. 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.{{Cite web|url=http://ai.googleblog.com/2019/10/quantum-supremacy-using-programmable.html|title=Quantum Supremacy Using a Programmable Superconducting Processor|website=Google AI Blog|access-date=2019-11-02}} 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.{{cite news |last1=Metz |first1=Cade |title=Google Claims a Quantum Breakthrough That Could Change Computing |url=https://www.nytimes.com/2019/10/23/technology/quantum-computing-google.html |access-date=14 January 2020 |work=The New York Times |date=23 October 2019}}{{cite arXiv |author1=Edwin Pednault |author2=John Gunnels |author3=Giacomo Nannicini |author4=Lior Horesh |author5=Robert Wisnieff |date=October 2019 |title=Leveraging Secondary Storage to Simulate Deep 54-qubit Sycamore Circuits |eprint=1910.09534 |class=quant-ph}}

{{Cite web|title=Google and IBM Clash Over Quantum Supremacy Claim|url=https://www.quantamagazine.org/google-and-ibm-clash-over-quantum-supremacy-claim-20191023/|access-date=2020-10-29|website=Quanta Magazine|date=23 October 2019|language=en}}

{{Further|Quantum computing#Challenges}}

Quantum computers are much more susceptible to errors than classical computers due to decoherence and noise.{{cite arXiv |last=Kalai |first=Gil |date=2011-06-02 |title=How Quantum Computers Fail: Quantum Codes, Correlations in Physical Systems, and Noise Accumulation |eprint=1106.0485 |class=quant-ph}} The threshold theorem states that a noisy quantum computer can use quantum error-correcting codes{{Cite journal |last=Shor |first=Peter W. |date=1995-10-01 |title=Scheme for reducing decoherence in quantum computer memory |journal=Physical Review A |volume=52 |issue=4 |pages=R2493–R2496 |doi=10.1103/PhysRevA.52.R2493 |pmid=9912632 |bibcode=1995PhRvA..52.2493S}}{{Cite journal |last=Steane |first=A. M. |date=1996-07-29 |title=Error Correcting Codes in Quantum Theory |journal=Physical Review Letters |volume=77 |issue=5 |pages=793–797 |doi=10.1103/PhysRevLett.77.793 |pmid=10062908 |bibcode=1996PhRvL..77..793S}} to simulate a noiseless quantum computer, assuming the error introduced in each computer cycle is less than some number.{{cite arXiv |last1=Aharonov |first1=Dorit |last2=Ben-Or |first2=Michael |date=1999-06-30 |title=Fault-Tolerant Quantum Computation With Constant Error Rate |eprint=quant-ph/9906129}} Numerical simulations suggest that that number may be as high as 3%.{{Cite journal |last=Knill |first=E. |date=2005-03-03 |title=Quantum computing with realistically noisy devices |journal=Nature |volume=434 |issue=7029 |pages=39–44 |doi=10.1038/nature03350 |pmid=15744292 |issn=0028-0836 |bibcode=2005Natur.434...39K |arxiv=quant-ph/0410199|s2cid=4420858 }} However, it is not yet definitively known how the resources needed for error correction will scale with the number of qubits.{{cite arXiv |last=Kalai |first=Gil |date=2016-05-03|title=The Quantum Computer Puzzle (Expanded Version)|eprint=1605.00992|class=quant-ph}} Skeptics point to the unknown behavior of noise in scaled-up quantum systems as a potential roadblock for successfully implementing quantum computing and demonstrating quantum supremacy.{{Cite book |last=Dyakonov |first=M. I. |title=Future Trends in Microelectronics. Up the Nano Creek |publisher=Wiley |year=2007 |editor1=Luryi |editor-first=S. |pages=4–18 |language=en |chapter=Is Fault-Tolerant Quantum Computation Really Possible? |bibcode=2006quant.ph.10117D |editor2=Xu |editor-first2=J. |editor3=Zaslavsky |editor-first3=A. |arxiv=quant-ph/0610117}}

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{{Cite news|url=https://www.wsj.com/articles/achieving-quantum-wokeness-11576540808|title=Opinion {{!}} Achieving Quantum Wokeness|last=Board|first=The Editorial|newspaper=Wall Street Journal|date=17 December 2019|language=en-US|access-date=2019-12-21}}{{Cite news|url=https://www.telegraph.co.uk/science/2019/12/17/academics-derided-claiming-quantum-supremacy-racist-colonialist/|title=Academics derided for claiming 'quantum supremacy' is a racist and colonialist term|last=Knapton|first=Sarah|date=2019-12-17|work=The Telegraph|access-date=2019-12-21|language=en-GB|issn=0307-1235}} commentary article in the journal Nature signed by thirteen researchers asserts that the alternative phrase "quantum advantage" should be used instead.{{Cite journal|last1=Palacios-Berraquero|first1=Carmen|last2=Mueck|first2=Leonie|last3=Persaud|first3=Divya M.|date=2019-12-10|title=Instead of 'supremacy' use 'quantum advantage'|journal=Nature|language=en|volume=576|issue=7786|pages=213|doi=10.1038/d41586-019-03781-0|pmid=31822842|doi-access=free}} 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.{{Cite web|title=John Preskill Explains 'Quantum Supremacy'|url=https://www.quantamagazine.org/john-preskill-explains-quantum-supremacy-20191002/|access-date=2020-04-21|website=Quanta Magazine|date=2 October 2019|language=en}} Nature's Philip Ball wrote in December 2020 that the term "quantum advantage" has "largely replaced" the term "quantum supremacy".{{cite journal |last1=Ball |first1=Philip |title=Physicists in China challenge Google's 'quantum advantage' |url=https://www.nature.com/articles/d41586-020-03434-7 |access-date=16 December 2020 |journal=Nature |date=17 December 2020 |volume=588 |issue=7838 |pages=380 |doi=10.1038/d41586-020-03434-7|pmid=33273711 |bibcode=2020Natur.588..380B |s2cid=227282052 }}

• Gottesman–Knill theorem
• List of quantum processors
• Sycamore processor
• Jiuzhang (quantum computer)
• Noisy intermediate-scale quantum era

{{reflist}}

{{Quantum information|state=collapsed}}

Category:Quantum computing

Category:Computational complexity theory