Content deleted Content added
m Added hybrid quantum/classical algorithms |
m cleanup |
||
Line 49:
===Deutsch–Jozsa algorithm===
{{main
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
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
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
Shor's algorithm solves the [[discrete logarithm]] problem and the [[integer factorization]] problem in polynomial time,<ref>
Line 110:
===Boson sampling problem===
{{main
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
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
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
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
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''<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>
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>{{
=== 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>
==See also==
|