Editing Quantum computing (section)

== History ==
{{For timeline|Timeline of quantum computing and communication}}

For many years, the fields of [[quantum mechanics]] and [[computer science]] formed distinct academic communities.{{sfn|Aaronson|2013|p=132}} [[Modern quantum theory]] developed in the 1920s to explain perplexing physical phenomena observed at atomic scales,<ref name="Zwiebach2022">{{cite book|first=Barton |last=Zwiebach |title=Mastering Quantum Mechanics: Essentials, Theory, and Applications |author-link=Barton Zwiebach |publisher=MIT Press |year=2022 |isbn=978-0-262-04613-8 |at=§1 |quote=Quantum physics has replaced classical physics as the correct fundamental description of our physical universe. It is used routinely to describe most phenomena that occur at short distances. [...] The era of quantum physics began in earnest in 1925 with the discoveries of Erwin Schrödinger and Werner Heisenberg. The seeds for these discoveries were planted by Max Planck, Albert Einstein, Niels Bohr, Louis de Broglie, and others.}}</ref><ref>{{cite book|first=Steven |last=Weinberg |author-link=Steven Weinberg |title=Lectures on Quantum Mechanics |year=2015 |publisher=Cambridge University Press |edition=2nd |isbn=978-1-107-11166-0|chapter=Historical Introduction |pages=1–30}}</ref> and [[digital computers]] emerged in the following decades to replace [[human computers]] for tedious calculations.<ref>{{Cite book |last=Ceruzzi |first=Paul E. |title=Computing: A Concise History |date=2012 |isbn=978-0-262-31038-3 |publisher=MIT Press |location=[[Cambridge, Massachusetts]] |pages=3, 46 |language=en-US |oclc=796812982}}</ref> Both disciplines had practical applications during [[World War II]]; computers played a major role in [[World War II cryptography|wartime cryptography]],<ref>{{Cite book |last=Hodges |first=Andrew |author-link=Andrew Hodges |title=Alan Turing: The Enigma |publisher=[[Princeton University Press]] |year=2014 |isbn=9780691164724 |location=Princeton, New Jersey |page=xviii |language=en-US}}</ref> and quantum physics was essential for [[nuclear physics]] used in the [[Manhattan Project]].<ref>{{Cite journal |last=Mårtensson-Pendrill |first=Ann-Marie |date=2006-11-01 |title=The Manhattan project—a part of physics history |journal=Physics Education |language=en-US |volume=41 |issue=6 |pages=493–501 |bibcode=2006PhyEd..41..493M |doi=10.1088/0031-9120/41/6/001 |issn=0031-9120 |s2cid=120294023}}</ref>

As [[physicists]] applied quantum mechanical models to computational problems and swapped digital [[bit]]s for [[qubits]], the fields of quantum mechanics and computer science began to converge. In 1980, [[Paul Benioff]] introduced the [[quantum Turing machine]], which uses quantum theory to describe a simplified computer.<ref name="The computer as a physical system">{{cite journal|last1=Benioff|first1=Paul |author-link=Paul Benioff |year=1980|title=The computer as a physical system: A microscopic quantum mechanical Hamiltonian model of computers as represented by Turing machines|journal=Journal of Statistical Physics|volume=22|issue=5|pages=563–591|bibcode=1980JSP....22..563B|doi=10.1007/bf01011339|s2cid=122949592}}</ref>
When digital computers became faster, physicists faced an [[exponential time|exponential]] increase in overhead when [[simulating quantum dynamics]],<ref>{{Cite journal |last1=Buluta |first1=Iulia |last2=Nori |first2=Franco |date=2009-10-02 |title=Quantum Simulators |journal=Science |language=en |volume=326 |issue=5949 |pages=108–111 |doi=10.1126/science.1177838 |pmid=19797653 |bibcode=2009Sci...326..108B |s2cid=17187000 |issn=0036-8075}}</ref> prompting [[Yuri Manin]] and [[Richard Feynman]] to independently suggest that hardware based on quantum phenomena might be more efficient for computer simulation.<ref name="manin1980vychislimoe">{{cite book |author=Manin |first=Yu. I. |author-link=Yuri Manin |url=http://publ.lib.ru/ARCHIVES/M/MANIN_Yuriy_Ivanovich/Manin_Yu.I._Vychislimoe_i_nevychislimoe.(1980).%5bdjv-fax%5d.zip |title=Vychislimoe i nevychislimoe |publisher=Soviet Radio |year=1980 |pages=13–15 |language=ru |trans-title=Computable and Noncomputable |access-date=4 March 2013 |archive-url=https://web.archive.org/web/20130510173823/http://publ.lib.ru/ARCHIVES/M/MANIN_Yuriy_Ivanovich/Manin_Yu.I._Vychislimoe_i_nevychislimoe.(1980).%5Bdjv%5D.zip |archive-date=10 May 2013 |url-status=dead}}</ref><ref>{{cite journal |last1=Feynman |first1=Richard |author-link=Richard Feynman |title=Simulating Physics with Computers |journal=International Journal of Theoretical Physics |date=June 1982 |volume=21 |issue=6/7 |pages=467–488 |doi=10.1007/BF02650179 |url=https://people.eecs.berkeley.edu/~christos/classics/Feynman.pdf |access-date=28 February 2019 |bibcode=1982IJTP...21..467F |s2cid=124545445 |archive-url=https://web.archive.org/web/20190108115138/https://people.eecs.berkeley.edu/~christos/classics/Feynman.pdf |archive-date=8 January 2019 |url-status=dead}}</ref>{{sfn|Nielsen|Chuang|2010|p=214}}
In a 1984 paper, [[Charles H. Bennett (physicist)|Charles Bennett]] and [[Gilles Brassard]] applied quantum theory to [[cryptography]] protocols and demonstrated that quantum key distribution could enhance [[information security]].<ref name="bb84">{{cite book|first1=C. H. |last1=Bennett |first2=G. |last2=Brassard |chapter=Quantum cryptography: Public key distribution and coin tossing |title=Proceedings of the International Conference on Computers, Systems & Signal Processing, Bangalore, India |volume=1 |pages=175–179 |publisher=IEEE |year=1984 |location=New York }} Reprinted as {{cite journal|first1=C. H. |last1=Bennett |first2=G. |last2=Brassard |title=Quantum cryptography: Public key distribution and coin tossing |journal=Theoretical Computer Science |series=Theoretical Aspects of Quantum Cryptography – celebrating 30 years of BB84 |volume=560 |number=1 |date=4 December 2014 |pages=7–11 |doi=10.1016/j.tcs.2014.05.025 |doi-access=free|arxiv=2003.06557 }}</ref><ref name="personal">{{Cite book |last=Brassard |first=G. |title=IEEE Information Theory Workshop on Theory and Practice in Information-Theoretic Security, 2005 |chapter=Brief history of quantum cryptography: A personal perspective |date=2005 |chapter-url=https://ieeexplore.ieee.org/document/1543949 |location=Awaji Island, Japan |publisher=IEEE |pages=19–23 |doi=10.1109/ITWTPI.2005.1543949 |arxiv=quant-ph/0604072 |isbn=978-0-7803-9491-9|s2cid=16118245 }}</ref>

[[Quantum algorithm]]s then emerged for solving [[oracle machine|oracle problems]], such as [[Deutsch's algorithm]] in 1985,<ref>{{Cite journal |date=1985-07-08 |title=Quantum theory, the Church–Turing principle and the universal quantum computer |journal=Proceedings of the Royal Society of London. A. Mathematical and Physical Sciences |language=en |volume=400 |issue=1818 |pages=97–117 |doi=10.1098/rspa.1985.0070 |bibcode=1985RSPSA.400...97D |s2cid=1438116 |issn=0080-4630|last1=Deutsch |first1=D. }}</ref> the [[Bernstein{{en dash}}Vazirani algorithm]] in 1993,<ref>{{Cite book |last1=Bernstein |first1=Ethan |title=Proceedings of the twenty-fifth annual ACM symposium on Theory of computing – STOC '93 |last2=Vazirani |first2=Umesh |date=1993 |publisher=ACM Press |isbn=978-0-89791-591-5 |location=San Diego, California, United States |pages=11–20 |language=en |chapter=Quantum complexity theory |doi=10.1145/167088.167097 |chapter-url=http://portal.acm.org/citation.cfm?doid=167088.167097 |s2cid=676378}}</ref> and [[Simon's algorithm]] in 1994.<ref>{{Cite book |last=Simon |first=D. R. |title=Proceedings 35th Annual Symposium on Foundations of Computer Science |chapter=On the power of quantum computation |date=1994 |chapter-url=https://ieeexplore.ieee.org/document/365701 |location=Santa Fe, New Mexico, USA |publisher=IEEE Comput. Soc. Press |pages=116–123 |doi=10.1109/SFCS.1994.365701 |isbn=978-0-8186-6580-6 |s2cid=7457814}}</ref>
These algorithms did not solve practical problems, but demonstrated mathematically that one could gain more information by querying a [[black box]] with a quantum state in [[quantum superposition|superposition]], sometimes referred to as ''quantum parallelism''.{{sfn|Nielsen|Chuang|2010|p=30-32}}

[[File:Peter Shor 2017 Dirac Medal Award Ceremony.png|thumb|[[Peter Shor]] (pictured here in 2017) showed in 1994 that a scalable quantum computer would be able to break [[RSA encryption]].|upright=0.9]]
[[Peter Shor]] built on these results with [[Shor's algorithm|his 1994 algorithm]] for breaking the widely used [[RSA (cryptosystem)|RSA]] and [[Diffie{{en dash}}Hellman]] encryption protocols,{{sfn|Shor|1994}} which drew significant attention to the field of quantum computing. In 1996, [[Grover's algorithm]] established a quantum speedup for the widely applicable [[unstructured data|unstructured]] search problem.<ref>{{Cite conference |last=Grover |first=Lov K. |date=1996 |title=A fast quantum mechanical algorithm for database search |conference=ACM symposium on Theory of computing |language=en |location=[[Philadelphia]] |publisher=ACM Press |pages=212–219 |doi=10.1145/237814.237866 |isbn=978-0-89791-785-8 |arxiv=quant-ph/9605043}}</ref>{{sfn|Nielsen|Chuang|2010 |p=7}} The same year, [[Seth Lloyd]] proved that quantum computers could simulate quantum systems without the exponential overhead present in classical simulations,<ref name="273.5278.1073">{{Cite journal |last=Lloyd |first=Seth |date=1996-08-23 |title=Universal Quantum Simulators |journal=Science |volume=273 |issue=5278 |pages=1073–1078 |pmid=8688088 |s2cid=43496899 |bibcode=1996Sci...273.1073L |doi=10.1126/science.273.5278.1073 |issn=0036-8075}}</ref> validating Feynman's 1982 conjecture.<ref>{{Cite journal |last1=Cao |first1=Yudong |last2=Romero |first2=Jonathan |last3=Olson |first3=Jonathan P. |last4=Degroote |first4=Matthias |last5=Johnson |first5=Peter D. |last6=Kieferová |first6=Mária |last7=Kivlichan |first7=Ian D. |last8=Menke |first8=Tim |last9=Peropadre |first9=Borja |last10=Sawaya |first10=Nicolas P. D. |last11=Sim |first11=Sukin |last12=Veis |first12=Libor |last13=Aspuru-Guzik |first13=Alán |date=2019-10-09 |title=Quantum Chemistry in the Age of Quantum Computing |journal=Chemical Reviews |language=en-US |volume=119 |issue=19 |pages=10856–10915 |arxiv=1812.09976 |doi=10.1021/acs.chemrev.8b00803 |issn=0009-2665 |pmid=31469277 |s2cid=119417908 |display-authors=5}}</ref>

Over the years, [[experimental physics|experimentalists]] have constructed small-scale quantum computers using [[trapped ion quantum computer|trapped ions]] and superconductors.{{sfn|Grumbling|Horowitz|2019|pp=164-169}}
In 1998, a two-qubit quantum computer demonstrated the feasibility of the technology,<ref>{{cite journal |last1=Chuang |first1=Isaac L. |last2=Gershenfeld |first2=Neil |last3=Kubinec |first3=Markdoi |date=April 1998 |title=Experimental Implementation of Fast Quantum Searching |journal=Physical Review Letters |publisher=[[American Physical Society]] |volume=80 |issue=15 |pages=3408–3411 |bibcode=1998PhRvL..80.3408C |doi=10.1103/PhysRevLett.80.3408}}</ref><ref>{{cite news |last=Holton |first=William Coffeen |title=quantum computer |url=https://www.britannica.com/technology/quantum-computer |access-date=4 Dec 2021 |newspaper=Encyclopedia Britannica |publisher=[[Encyclopædia Britannica]]}}</ref> and subsequent experiments have increased the number of qubits and reduced error rates.{{sfn|Grumbling|Horowitz|2019 |pp=164-169}}

In 2019, [[Google AI]] and [[NASA]] announced that they had achieved [[quantum supremacy]] with a 54-qubit machine, performing a computation that is impossible for any classical computer.<ref>{{Cite journal |last=Gibney |first=Elizabeth |date=2019-10-23 |title=Hello quantum world! Google publishes landmark quantum supremacy claim |journal=Nature |language=en |volume=574 |issue=7779 |pages=461–462 |doi=10.1038/d41586-019-03213-z |pmid=31645740 |bibcode=2019Natur.574..461G |doi-access=free}}</ref><ref name="1910.11333">Lay summary: {{cite journal |url=https://ai.googleblog.com/2019/10/quantum-supremacy-using-programmable.html |title=Quantum Supremacy Using a Programmable Superconducting Processor |journal=Nature |publisher=[[Google AI]] |first1=John |last1=Martinis |first2=Sergio |last2=Boixo |date=October 23, 2019 |volume=574 |issue=7779 |pages=505–510 |doi=10.1038/s41586-019-1666-5 |pmid=31645734 |arxiv=1910.11333 |bibcode=2019Natur.574..505A |s2cid=204836822 |access-date=2022-04-27}}<br />{{*}}Journal article: {{cite journal |last1=Arute |first1=Frank |last2=Arya |first2=Kunal |last3=Babbush |first3=Ryan |last4=Bacon |first4=Dave |last5=Bardin |first5=Joseph C. |last6=Barends |first6=Rami |last7=Biswas |first7=Rupak |last8=Boixo |first8=Sergio |last9=Brandao |first9=Fernando G. S. L. |last10=Buell |first10=David A. |last11=Burkett |first11=Brian |first15=Roberto |first57=Murphy Yuezhen |last64=Rubin |first63=Pedram |last63=Roushan |first62=Eleanor G. |last62=Rieffel |first61=Chris |last61=Quintana |first60=John C. |last60=Platt |first59=Andre |last59=Petukhov |first58=Eric |last58=Ostby |last57=Niu |last65=Sank |first56=Charles |last56=Neill |first55=Matthew |last55=Neeley |first54=Ofer |last54=Naaman |first53=Josh |last53=Mutus |first52=Masoud |last52=Mohseni |first51=Kristel |last51=Michielsen |first50=Xiao |last50=Mi |first64=Nicholas C. |first65=Daniel |last49=Megrant |last74=Yeh |last12=Chen |first12=Yu |last13=Chen |first13=Zijun |last14=Chiaro |first14=Ben |first77=John M. |last77=Martinis |first76=Hartmut |last76=Neven |first75=Adam |last75=Zalcman |first74=Ping |first73=Z. Jamie |last66=Satzinger |last73=Yao |first72=Theodore |last72=White |first71=Benjamin |last71=Villalonga |first70=Amit |last70=Vainsencher |first69=Matthew D. |last69=Trevithick |first68=Kevin J. |last68=Sung |first67=Vadim |last67=Smelyanskiy |first66=Kevin J. |first49=Anthony |first48=Matthew |last16=Courtney |last24=Guerin |first30=Trent |last30=Huang |first29=Markus |last29=Hoffman |first28=Alan |last28=Ho |first27=Michael J. |last27=Hartmann |first26=Matthew P. |last26=Harrigan |first25=Steve |last25=Habegger |first24=Keith |first23=Rob |first31=Travis S. |last23=Graff |first22=Marissa |last22=Giustina |first21=Craig |last21=Gidney |first20=Austin |last20=Fowler |first19=Brooks|last19=Foxen |first18=Edward |last18=Farhi |first17=Andrew |last17=Dunsworsth |first16=William |last31=Humble |last32=Isakov |last48=McEwen |first40=Alexander |first47=Jarrod R. |last47=McClean |first46=Salvatore |last46=Mandrà |first45=Dmitry |last45=Lyakh |first44=Erik |last44=Lucero |first43=Mike |last43=Lindmark |first42=David |last42=Landhuis |first41=Fedor |last15=Collins |last40=Korotov |first32=Sergei V. |first39=Sergey |last39=Knysh |first38=Paul V. |last38=Klimov |first37=Julian |last37=Kelly |first36=Kostyantyn |last36=Kechedzhi |first35=Dvir |last35=Kafri |first34=Zhang |last34=Jiang |first33=Evan |last33=Jeffery |last41=Kostritsa |display-authors=5 |title=Quantum supremacy using a programmable superconducting processor |journal=Nature |date=October 23, 2019 |volume=574 |issue=7779 |pages=505–510 |doi=10.1038/s41586-019-1666-5 |pmid=31645734 |arxiv=1910.11333 |bibcode=2019Natur.574..505A |s2cid=204836822}}</ref><ref>{{Cite news |last=Aaronson |first=Scott |date=2019-10-30 |title=Opinion {{!}} Why Google's Quantum Supremacy Milestone Matters |url=https://www.nytimes.com/2019/10/30/opinion/google-quantum-computer-sycamore.html |access-date=2021-09-25 |work=The New York Times |issn=0362-4331}}</ref> However, the validity of this claim is still being actively researched.<ref>{{cite web |last=Pednault |first=Edwin |date=22 October 2019 |title=On 'Quantum Supremacy' |url=https://www.ibm.com/blogs/research/2019/10/on-quantum-supremacy/ |access-date=9 February 2021 |website=IBM Research Blog}}</ref><ref>{{cite arXiv |last1=Pan |first1=Feng |last2=Zhang |first2=Pan |date=2021-03-04 |title=Simulating the Sycamore quantum supremacy circuits |class=quant-ph |eprint=2103.03074}}</ref>