Quantum algorithm: Difference between revisions

Revision as of 12:52, 1 June 2018

Revision as of 02:29, 2 June 2018

Line 49:

===Deutsch–Jozsa algorithm===

{{main article|Deutsch–Jozsa algorithm}}

The Deutsch–Jozsa algorithm solves a [[black-box]] problem which probably requires exponentially many queries to the black box for any deterministic classical computer, but can be done with exactly one query by a quantum computer. If we allow both bounded-error quantum and classical algorithms, then there is no speedup since a classical probabilistic algorithm can solve the problem with a constant number of queries with small probability of error. The algorithm determines whether a function ''f'' is either constant (0 on all inputs or 1 on all inputs) or balanced (returns 1 for half of the input ___domain and 0 for the other half).

===Simon's algorithm===

{{main article|Simon's algorithm}}

Simon's algorithm solves a black-box problem exponentially faster than any classical algorithm, including bounded-error probabilistic algorithms. This algorithm, which achieves an exponential speedup over all classical algorithms that we consider efficient, was the motivation for Shor's factoring algorithm.

===Quantum phase estimation algorithm===

{{main article|Quantum phase estimation algorithm}}

The [[quantum phase estimation algorithm]] is used to determine the eigenphase of an eigenvector of a unitary gate given a quantum state proportional to the eigenvector and access to the gate. The algorithm is frequently used as a subroutine in other algorithms.

===Shor's algorithm===

{{main article|Shor's algorithm}}

Shor's algorithm solves the [[discrete logarithm]] problem and the [[integer factorization]] problem in polynomial time,<ref>

Line 110:

===Boson sampling problem===

{{main article|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, 2014|volume=113|doi=10.1103/PhysRevLett.113.100502|arxiv = 1305.4346 |bibcode = 2014PhRvL.113j0502L|pmid=25238340|page=100502}}</ref> Solving this problem with a classical computer algorithm requires computing the 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 }}</ref> the sampling problem had similar complexity for inputs other than [[Fock state]] photons and identified a transition in computational complexity from classically simulatable to just as hard as the Boson Sampling Problem, dependent on the size of coherent amplitude inputs.

Line 146:

===Grover's algorithm===

{{main article|Grover's algorithm}}

Grover's algorithm searches an unstructured database (or an unordered list) with N entries, for a marked entry, using only <math>O(\sqrt{N})</math> queries instead of the <math>O({N})</math> queries required classically.<ref>

Line 185:

==Algorithms based on quantum walks==

{{main article|Quantum walk}}

A quantum walk is the quantum analogue of a classical [[random walk]], which can be described by a [[probability distribution]] over some states. 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>

Line 220:

===Element distinctness problem===

{{main article|Element distinctness problem}}

The element distinctness problem is the problem of determining whether all the elements of a list are distinct. Classically, Ω(''N'') queries are required for a list of size ''N'', since this problem is harder than the search problem which requires Ω(''N'') queries. However, it can be solved in <math>\Theta(N^{2/3})</math> queries on a quantum computer. The optimal algorithm is by [[Andris Ambainis]].<ref>

Line 263:

===Triangle-finding problem===

{{main article|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 Ω(''N''), but the best algorithm known requires O(''N''^1.297) 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''^1.3) queries.<ref name=Search_via_quantum_walk>

Line 465:

=== QAOA ===

The quantum approximate optimization algorithm is a toy model of quantum annealing which can be used to solve problems in graph theory.<ref>{{Citecite journalarxiv|last=Farhi|first=Edward|last2=Goldstone|first2=Jeffrey|last3=Gutmann|first3=Sam|date=2014-11-14|title=A Quantum Approximate Optimization Algorithm|url=http://arxiv.org/abs/1411.4028|journal=arXiv:1411.4028 [quant-ph]}}</ref>. The algorithm makes use of classical optimization of quantum operations to maximize an objective function.

=== Variational Quantum Eigensolver ===

The VQE algorithm applies classical optimization to minimize the energy expectation of an ansatz state to find the ground state energy of a molecule.<ref>{{Cite journal|last=Peruzzo|first=Alberto|last2=McClean|first2=Jarrod|last3=Shadbolt|first3=Peter|last4=Yung|first4=Man-Hong|last5=Zhou|first5=Xiao-Qi|last6=Love|first6=Peter J.|last7=Aspuru-Guzik|first7=Alán|last8=O’Brien|first8=Jeremy L.|date=2014-07-23|title=A variational eigenvalue solver on a photonic quantum processor|url=https://www.nature.com/articles/ncomms5213|journal=Nature Communications|language=En|volume=5|issue=1|doi=10.1038/ncomms5213|issn=2041-1723}}</ref>. This can also be extended to find excited energies of molecules.<ref>{{Citecite journalarxiv|last=Higgott|first=Oscar|last2=Wang|first2=Daochen|last3=Brierley|first3=Stephen|date=2018-05-21|title=Variational Quantum Computation of Excited States|url=http://arxiv.org/abs/1805.08138|journal=arXiv:1805.08138 [quant-ph]}}</ref>.

==See also==