Editing Quantum algorithm (section)

==Algorithms based on quantum walks==
{{main|Quantum walk}}

A quantum walk is the quantum analogue of a classical [[random walk]]. A classical random walk can be described by a [[probability distribution]] over some states, while a quantum walk can be described by a [[quantum superposition]] over states. Quantum walks are known to give exponential speedups for some black-box problems.<ref>
{{cite conference
 |last1=Childs |first1=A. M.
 |last2=Cleve |first2=R.
 |last3=Deotto |first3=E.
 |last4=Farhi |first4=E.
 |last5=Gutmann |first5=S.
 |last6=Spielman |first6=D. A.
 |year=2003
 |title=Exponential algorithmic speedup by quantum walk
 |book-title=Proceedings of the 35th Symposium on Theory of Computing
 |pages=59–68
 |publisher=[[Association for Computing Machinery]]
 |arxiv=quant-ph/0209131
 |doi=10.1145/780542.780552
 |isbn=1-58113-674-9
}}</ref><ref>
{{cite conference
 |last1=Childs |first1=A. M.
 |last2=Schulman |first2=L. J.
 |last3=Vazirani |first3=U. V.
 |year=2007
 |title=Quantum Algorithms for Hidden Nonlinear Structures
 |book-title=Proceedings of the 48th Annual IEEE Symposium on Foundations of Computer Science
 |pages=395–404
 |publisher=[[IEEE]]
 |arxiv=0705.2784
 |doi=10.1109/FOCS.2007.18
 |isbn=978-0-7695-3010-9
}}</ref> They also provide polynomial speedups for many problems. A framework for the creation of quantum walk algorithms exists and is a versatile tool.<ref name="Search_via_quantum_walk" />

===Boson sampling problem===
{{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}}</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===
{{main|Element distinctness problem}}

The element distinctness problem is the problem of determining whether all the elements of a list are distinct. Classically, <math>\Omega(N)</math> queries are required for a list of size <math>N</math>; however, it can be solved in <math>\Theta(N^{2/3})</math> queries on a quantum computer. The optimal algorithm was put forth by [[Andris Ambainis]],<ref>
{{cite journal
 |last=Ambainis |first=A.
 |year=2007
 |title=Quantum Walk Algorithm for Element Distinctness
 |journal=[[SIAM Journal on Computing]]
 |volume=37 |issue=1 |pages=210–239
 |arxiv= quant-ph/0311001
 |doi=10.1137/S0097539705447311
|s2cid=6581885
 }}</ref> and [[Yaoyun Shi]] first proved a tight lower bound when the size of the range is sufficiently large.<ref>
{{cite conference
 | last1=Shi | first1=Y.
 | title=The 43rd Annual IEEE Symposium on Foundations of Computer Science, 2002. Proceedings.
 | year=2002
 | chapter=Quantum lower bounds for the collision and the element distinctness problems
 | conference = Proceedings of the 43rd [[Symposium on Foundations of Computer Science]]
 | pages=513–519
 | arxiv = quant-ph/0112086
 | doi=10.1109/SFCS.2002.1181975| isbn=0-7695-1822-2
 }}</ref> Ambainis<ref>
{{cite journal
 |last=Ambainis |first=A.
 |year=2005
 |title=Polynomial Degree and Lower Bounds in Quantum Complexity: Collision and Element Distinctness with Small Range
 |journal=[[Theory of Computing]]
 |volume=1 |issue=1 |pages=37–46
 |doi=10.4086/toc.2005.v001a003
|doi-access=free
 }}</ref> and Kutin<ref>
{{cite journal
 |last1=Kutin |first1=S.
 |year=2005
 |title=Quantum Lower Bound for the Collision Problem with Small Range
 |journal=[[Theory of Computing]]
 |volume=1 |issue=1 |pages=29–36
 |doi=10.4086/toc.2005.v001a002
|doi-access=free
 }}</ref> independently (and via different proofs) extended that work to obtain the lower bound for all functions.

===Triangle-finding problem===
{{main|Triangle finding problem}}

The triangle-finding problem is the problem of determining whether a given graph contains a triangle (a [[clique (graph theory)|clique]] of size 3). The best-known lower bound for quantum algorithms is <math>\Omega(N)</math>, but the best algorithm known requires O(''N''<sup>1.297</sup>) queries,<ref>{{cite arXiv| eprint=1105.4024| author1=Aleksandrs Belovs| title=Span Programs for Functions with Constant-Sized 1-certificates| class=quant-ph| year=2011}}</ref> an improvement over the previous best O(''N''<sup>1.3</sup>) queries.<ref name=Search_via_quantum_walk>
{{cite conference
 |last1=Magniez |first1=F.
 |last2=Nayak |first2=A.
 |last3=Roland |first3=J.
 |last4=Santha |first4=M.
 |year=2007
 |title=Search via quantum walk
 |book-title=Proceedings of the 39th Annual ACM Symposium on Theory of Computing
 |publisher=[[Association for Computing Machinery]]
 |pages=575–584
 |doi=10.1145/1250790.1250874
 |isbn=978-1-59593-631-8
|arxiv=quant-ph/0608026}}</ref><ref>
{{cite journal
 |last1=Magniez |first1=F.
 |last2=Santha |first2=M.
 |last3=Szegedy |first3=M.
 |year=2007
 |title=Quantum Algorithms for the Triangle Problem
 |journal=[[SIAM Journal on Computing]]
 |volume=37 |issue=2 |pages=413–424
 |arxiv= quant-ph/0310134
 |doi=10.1137/050643684
|s2cid=594494
 }}</ref>

===Formula evaluation===
A formula is a tree with a gate at each internal node and an input bit at each leaf node. The problem is to evaluate the formula, which is the output of the root node, given oracle access to the input.

A well studied formula is the balanced binary tree with only NAND gates.<ref>
{{cite web
 |last=Aaronson |first=S.
 |date=3 February 2007
 |title=NAND now for something completely different
 |url=http://scottaaronson.com/blog/?p=207
 |work=Shtetl-Optimized
 |access-date=2009-12-17
}}</ref> This type of formula requires <math>\Theta(N^c)</math> queries using randomness,<ref>
{{cite conference
 |last1=Saks |first1=M.E.
 |last2=Wigderson |first2=A.
 |year=1986
 |title=Probabilistic Boolean Decision Trees and the Complexity of Evaluating Game Trees
 |url=http://www.math.ias.edu/~avi/PUBLICATIONS/MYPAPERS/SW86/SW86.pdf
 |book-title=Proceedings of the 27th Annual Symposium on Foundations of Computer Science
 |pages=29–38
 |publisher=[[IEEE]]
 |doi=10.1109/SFCS.1986.44
 |isbn=0-8186-0740-8
}}</ref> where <math>c = \log_2(1+\sqrt{33})/4 \approx 0.754</math>. With a quantum algorithm, however, it can be solved in <math>\Theta(N^{1/2})</math> queries. No better quantum algorithm for this case was known until one was found for the unconventional Hamiltonian oracle model.<ref name=Hamiltonian_NAND_Tree/> The same result for the standard setting soon followed.<ref>
{{cite arXiv
 |last=Ambainis |first=A.
 |year=2007
 |title=A nearly optimal discrete query quantum algorithm for evaluating NAND formulas
 |class=quant-ph
 |eprint=0704.3628
}}</ref>

Fast quantum algorithms for more complicated formulas are also known.<ref>
{{cite conference
 |last1=Reichardt |first1=B. W.
 |last2=Spalek |first2=R.
 |year=2008
 |title=Span-program-based quantum algorithm for evaluating formulas
 |book-title=Proceedings of the 40th Annual ACM symposium on Theory of Computing
 |publisher=[[Association for Computing Machinery]]
 |pages=103–112
 |isbn=978-1-60558-047-0
 |doi=10.1145/1374376.1374394
|arxiv=0710.2630}}</ref>

===Group commutativity===
The problem is to determine if a [[black box group|black-box group]], given by ''k'' generators, is [[Commutativity|commutative]]. A black-box group is a group with an oracle function, which must be used to perform the group operations (multiplication, inversion, and comparison with identity). The interest in this context lies in the query complexity, which is the number of oracle calls needed to solve the problem. The deterministic and randomized query complexities are <math>\Theta(k^2)</math> and <math>\Theta(k)</math>, respectively.<ref>
{{cite journal
 |last=Pak |first=Igor |author1-link=Igor Pak
 |year=2012
 |title=Testing commutativity of a group and the power of randomization
 |journal= [[LMS Journal of Computation and Mathematics]]
 |volume=15 |pages=38–43
 |doi=10.1112/S1461157012000046
 |doi-access=free
 }}</ref> A quantum algorithm requires <math>\Omega(k^{2/3})</math> queries, while the best-known classical algorithm uses <math>O(k^{2/3} \log k)</math> queries.<ref>
{{cite journal
 |last1=Magniez |first1=F.
 |last2=Nayak |first2=A.
 |year=2007
 |title=Quantum Complexity of Testing Group Commutativity
 |journal=[[Algorithmica]]
 |volume=48 |issue=3 |pages=221–232
 |doi=10.1007/s00453-007-0057-8
|arxiv=quant-ph/0506265|s2cid=3163328
 }}</ref>