Quantum algorithm: Difference between revisions

Revision as of 00:09, 21 November 2024

Latest revision as of 18:07, 18 July 2025

(5 intermediate revisions by 5 users not shown)

Line 1:

{{Short description|AlgorithmsAlgorithm to be run on quantum computers, typically relying on superposition and/or entanglement}}

{{Use American English|date=January 2019}}

{{Use dmy dates|date=December 2020}}

Line 6:

Problems that are [[Undecidable problem|undecidable]] using classical computers remain undecidable using quantum computers.<ref name=nielchuan>{{cite book|title=Quantum Computation and Quantum Information|last1=Nielsen|first1=Michael A.|last2=Chuang|first2=Isaac L.|publisher=Cambridge University Press|year=2010|isbn=978-1-107-00217-3|edition=2nd|___location=Cambridge|author-link=Michael A. Nielsen|author-link2=Isaac Chuang|url=https://books.google.com/books?id=-s4DEy7o-a0C}}</ref>{{rp|127}} What makes quantum algorithms interesting is that they might be able to solve some problems faster than classical algorithms because the quantum superposition and quantum entanglement that quantum algorithms exploit generally cannot be efficiently simulated on classical computers (see [[Quantum supremacy]]).

The best-known algorithms are [[Shor's algorithm]] for factoring and [[Grover's algorithm]] for searching an unstructured database or an unordered list. Shor's algorithm runs much (almost exponentially) faster than the best-most efficient known classical algorithm for factoring, the [[general number field sieve]].<ref>{{Cite web|url=https://quantum-computing.ibm.com/docs/iqx/guide/shors-algorithm|title = Shor's algorithm|access-date=21 October 2020|archive-date=12 January 2023|archive-url=https://web.archive.org/web/20230112064753/https://quantum-computing.ibm.com/docs/iqx/guide/shors-algorithm|url-status=dead}}</ref> Grover's algorithm runs quadratically faster than the best possible classical algorithm for the same task,<ref>{{cite web |url=https://quantum-computing.ibm.com/composer/docs/iqx/guide/grovers-algorithm |title=IBM quantum composer user guide: Grover's algorithm |access-date=7 June 2022 |website=quantum-computing.ibm.com |archive-date=27 September 2022 |archive-url=https://web.archive.org/web/20220927192200/https://quantum-computing.ibm.com/composer/docs/iqx/guide/grovers-algorithm |url-status=dead }}</ref> a [[linear search]].

==Overview==

Line 62:

| doi=10.1137/s0097539795293172

| s2cid = 2337707

}}</ref> whereas the best known classical algorithms take super-polynomial time. TheseIt problemsis areunknown notwhether knownthese toproblems beare in [[P (complexity)|P]] or [[NP-complete]]. It is also one of the few quantum algorithms that solves a non&ndash;-black-box problem in polynomial time, where the best known classical algorithms run in super-polynomial time.

===Hidden subgroup problem===

Line 75:

|publisher=[[Springer-Verlag]]

|isbn=3-540-60221-6

}}</ref> The more general hidden subgroup problem, where the group isn'tis not necessarily abelian, is a generalization of the previously mentioned problems, as well as [[graph isomorphism]] and certain [[lattice problems]]. Efficient quantum algorithms are known for certain non-abelian groups. However, no efficient algorithms are known for the [[symmetric group]], which would give an efficient algorithm for graph isomorphism<ref>{{cite arXiv

|last1=Moore |first1=C.|author1-link=Cris Moore

|last2=Russell |first2=A.

Line 200:

{{main|Boson sampling}}

The Boson Sampling Problem in an experimental configuration assumes<ref>{{cite journal |last1=Ralph |first1=T.C. |date=July 2013 |title=Figure 1: The boson-sampling problem |url=http://www.nature.com/nphoton/journal/v7/n7/fig_tab/nphoton.2013.175_F1.html |journal=Nature Photonics |publisher=Nature |volume=7 |issue=7 |pages=514–515 |doi=10.1038/nphoton.2013.175 |s2cid=110342419 |access-date=12 September 2014|url-access=subscription }}</ref> an input of [[boson]]s (e.g., photons) of moderate number that are randomly scattered into a large number of output modes, constrained by a defined [[unitarity]]. When individual photons are used, the problem is isomorphic to a multi-photon quantum walk.<ref>{{Cite journal |last1=Peruzzo |first1=Alberto |last2=Lobino |first2=Mirko |last3=Matthews |first3=Jonathan C. F. |last4=Matsuda |first4=Nobuyuki |last5=Politi |first5=Alberto |last6=Poulios |first6=Konstantinos |last7=Zhou |first7=Xiao-Qi |last8=Lahini |first8=Yoav |last9=Ismail |first9=Nur |last10=Wörhoff |first10=Kerstin |last11=Bromberg |first11=Yaron |last12=Silberberg |first12=Yaron |last13=Thompson |first13=Mark G. |last14=OBrien |first14=Jeremy L. |date=2010-09-17 |title=Quantum Walks of Correlated Photons |url=https://www.science.org/doi/10.1126/science.1193515 |journal=Science |language=en |volume=329 |issue=5998 |pages=1500–1503 |doi=10.1126/science.1193515 |pmid=20847264 |arxiv=1006.4764 |bibcode=2010Sci...329.1500P |hdl=10072/53193 |s2cid=13896075 |issn=0036-8075}}</ref> The problem is then to produce a fair sample of the [[probability distribution]] of the output that depends on the input arrangement of bosons and the unitarity.<ref>{{cite journal |last1=Lund |first1=A.P. |last2=Laing |first2=A. |last3=Rahimi-Keshari |first3=S. |last4=Rudolph |first4=T. |last5=O'Brien |first5=J.L. |last6=Ralph |first6=T.C. |date=5 September 2014 |title=Boson Sampling from Gaussian States |journal=Phys. Rev. Lett. |volume=113 |issue=10 |page=100502 |arxiv=1305.4346 |bibcode=2014PhRvL.113j0502L |doi=10.1103/PhysRevLett.113.100502 |pmid=25238340 |s2cid=27742471}}</ref> Solving this problem with a classical computer algorithm requires computing the [[Permanent (mathematics)|permanent]] of the unitary transform matrix, which may take a prohibitively long time or be outright impossible. In 2014, it was proposed<ref>{{cite web |title=The quantum revolution is a step closer |url=http://phys.org/news/2014-09-quantum-revolution-closer.html |access-date=12 September 2014 |website=Phys.org |publisher=Omicron Technology Limited}}</ref> that existing technology and standard probabilistic methods of generating single-photon states could be used as an input into a suitable quantum computable [[Linear optical quantum computing|linear optical network]] and that sampling of the output probability distribution would be demonstrably superior using quantum algorithms. In 2015, investigation predicted<ref>{{cite journal |last1=Seshadreesan |first1=Kaushik P. |last2=Olson |first2=Jonathan P. |last3=Motes |first3=Keith R. |last4=Rohde |first4=Peter P. |last5=Dowling |first5=Jonathan P. |year=2015 |title=Boson sampling with displaced single-photon Fock states versus single-photon-added coherent states: The quantum-classical divide and computational-complexity transitions in linear optics |journal=Physical Review A |volume=91 |issue=2 |page=022334 |arxiv=1402.0531 |bibcode=2015PhRvA..91b2334S |doi=10.1103/PhysRevA.91.022334 |s2cid=55455992}}</ref> the sampling problem had similar complexity for inputs other than [[Fock state|Fock-state]] photons and identified a transition in [[Quantum complexity theory|computational complexity]] from classically simulable to just as hard as the Boson Sampling Problem, depending on the size of coherent amplitude inputs.

===Element distinctness problem===

Line 456:

}}</ref>

===Solving a linear systemssystem of equations===

{{main|Quantum algorithm for linear systems of equations}}