Quantum algorithm: Difference between revisions

Revision as of 01:35, 7 December 2020

Revision as of 10:56, 17 December 2020

Line 1:

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

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

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

{{Use dmy dates|date=SeptemberDecember 20112020}}

In [[quantum computing]], a '''quantum algorithm''' is an [[algorithm]] which runs on a realistic model of [[quantum computation]], the most commonly used model being the [[quantum circuit]] model of computation.<ref>{{cite book|title=Quantum Computation and Quantum Information|last1=Nielsen|first1=Michael A.|last2=Chuang|first2=Isaac L.|publisher=[[Cambridge University Press]]|year=2000|isbn=978-0-521-63503-5|author-link=Michael Nielsen|author-link2=Isaac Chuang|title-link=Quantum Computation and Quantum Information}}</ref><ref>{{cite arXiv|eprint=0808.0369|class=quant-ph|first=M.|last=Mosca|author-link=Michele Mosca|title=Quantum Algorithms|date=2008}}</ref> A classical (or non-quantum) algorithm is a finite sequence of instructions, or a step-by-step procedure for solving a problem, where each step or instruction can be performed on a classical [[computer]]. Similarly, a quantum algorithm is a step-by-step procedure, where each of the steps can be performed on a [[quantum computer]]. Although all classical algorithms can also be performed on a quantum computer,<ref>{{Cite book|title = Quantum Computer Science|url = https://books.google.com/books?id=-wkJIuw0YRsC&q=quantum%2520computer%2520equivalent%2520classical%2520computer&pg=PA23|publisher = Morgan & Claypool Publishers|date = 2009-01-01|isbn = 9781598297324|first1 = Marco|last1 = Lanzagorta|first2 = Jeffrey K.|last2 = Uhlmann}}</ref>{{rp|126}} the term quantum algorithm is usually used for those algorithms which seem inherently quantum, or use some essential feature of quantum computation such as [[quantum superposition]] or [[quantum entanglement]].

Line 86 ⟶ 87:

===Boson sampling problem===

{{main|Boson sampling}}

The Boson Sampling Problem in an experimental configuration assumes<ref>{{cite web|last1=Ralph|first1=T.C.|title=Figure 1: The boson-sampling problem|url=http://www.nature.com/nphoton/journal/v7/n7/fig_tab/nphoton.2013.175_F1.html|website=Nature Photonics|publisher=Nature|accessdate=12 September 2014}}</ref> an input of [[boson]]s (ex. photons of light) of moderate number getting randomly scattered into a large number of output modes constrained by a defined [[unitarity]]. The problem is then to produce a fair sample of the [[probability distribution]] of the output which is dependent 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.|title=Boson Sampling from Gaussian States|journal=Phys. Rev. Lett.|date=September 5, September 2014|volume=113|issue=10|doi=10.1103/PhysRevLett.113.100502|arxiv = 1305.4346 |bibcode = 2014PhRvL.113j0502L|pmid=25238340|page=100502|s2cid=27742471}}</ref> Solving this problem with a classical computer algorithm requires computing the [[Permanent_Permanent (mathematics)|permanent]] of the unitary transform matrix, which may be either impossible or take a prohibitively long time. 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|website=Phys.org|publisher=Omicron Technology Limited|accessdate=12 September 2014}}</ref> that existing technology and standard probabilistic methods of generating single photon states could be used as 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.|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|doi=10.1103/PhysRevA.91.022334|arxiv = 1402.0531 |bibcode = 2015PhRvA..91b2334S |year=2015|s2cid=55455992}}</ref> the sampling problem had similar complexity for inputs other than [[Fock state]] photons and identified a transition in [[Quantum complexity theory|computational complexity]] from classically simulatable to just as hard as the Boson Sampling Problem, dependent on the size of coherent amplitude inputs.

===Estimating Gauss sums===

Line 461 ⟶ 462:

==References==

{{reflist|2}}

==External links==

Line 475 ⟶ 476:

{{Quantum mechanics topics}}

{{emerging technologies|quantum=yes|other=yes}}

{{Use dmy dates|date=September 2011}}

{{DEFAULTSORT:Quantum Algorithm}}