Quantum algorithm: Difference between revisions

Revision as of 15:12, 28 June 2010

Revision as of 09:51, 30 June 2010

Line 13:

The most well known algorithms are [[Shor's algorithm]] for factoring, and [[Grover's algorithm]] for searching an unstructured database or an unordered list. Shor's algorithms runs exponentially faster than the best known classical algorithm for factoring, the [[general number field sieve]]. Grover's algorithm runs quadratically faster than the best possible classical algorithm for the same task.

== Overview ==

Quantum algorithms are usually described, in the commonly-used circuit model of quantum computation, by a [[quantum circuit]] which acts on some input [[qubit]]s and terminates with a [[measurement]]. A quantum circuit consists of simple [[quantum gate]]s which act on at most a fixed number of qubits, usually 2 or 3. Quantum algorithms may also be stated in other models of quantum computation, such as the [[Hamiltonian oracle model]].<ref>{{Cite journal

Line 37:

}}</ref>

== Algorithms based on the quantum Fourier transform ==

The [[quantum Fourier transform]] is the quantum analogue of the [[discrete Fourier transform]], and is used in several quantum algorithms. The [[Hadamard transform]] is also an example of a quantum Fourier transform. The quantum Fourier transform can be efficiently implemented on a quantum computer using only a polynomial number of [[quantum gate]]s.

=== Deutsch–Jozsa algorithm ===

{{main|Deutsch–Jozsa algorithm}}

The Deutsch–Jozsa algorithm solves a [[black-box]] problem which provably requires exponentially many queries to the black box for any deterministic classical computer, but can be done with exactly 1 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.

=== Simon's algorithm ===

{{main|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.

=== Shor's algorithm ===

{{main|Shor's Algorithm}}

Line 64:

}}</ref> whereas the best known classical algorithms take super-polynomial time. These problems are not known to be 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 ===

The [[Abelian group|abelian]] [[hidden subgroup problem]] is a generalization of many problems that can be solved by a quantum computer, such as Simon's problem, solving [[Pell's equation]], testing the [[principal ideal]] of a [[ring (mathematics)|ring]]R and [[integer factorization|factoring]]. There are efficient quantum algorithms known for the Abelian hidden subgroup problem.<ref>D. Boneh and R. J. Lipton. ''Quantum cryptoanalysis of hidden linear functions.'' In Don Coppersmith, editor, CRYPTO '95, Lecture Notes in Computer Science, pages 424-437. Springer-Verlag, 1995.</ref> The more general hidden subgroup problem, where the group isn't necessarily abelian, is a generalization of the previously-mentioned problems and [[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|eprint=quant-ph/0501056v3|author1=Cristopher Moore|author2=Alexander Russell|last3=Schulman | first3=Leonard J.|title=The Symmetric Group Defies Strong Fourier Sampling: Part I|class=quant-ph|year=2005|author3=Schulman}}</ref> and the [[dihedral group]], which would solve certain lattice problems.<ref>{{Cite journal

Line 76:

}}</ref>

=== Estimating Gauss sums ===

A [[Gauss sum]] is a type of [[exponential sum]]. The best known classical algorithm for estimating these sums takes exponential time. Since the discrete logarithm problem reduces to Gauss sum estimation, an efficient classical algorithm for estimating Gauss sums would imply an efficient classical algorithm for computing discrete logarithms, which is considered unlikely. However, quantum computers can estimate Gauss sums to polynomial precision in polynomial time.<ref>{{Cite journal

Line 89:

}}</ref>

== Algorithms based on amplitude amplification ==

[[Amplitude amplification]] is a technique that allows the amplification of a chosen subspace of a quantum state. Applications of amplitude amplification usually lead to quadratic speedups over the corresponding classical algorithms. It can be considered to be a generalization of Grover's algorithm.

=== Grover's algorithm ===

{{main|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 &Omega;Ω(''N'') queries required classically.<ref>{{Cite journal

| last = Grover

| first = Lov K

Line 104:

| date = 1996-05-29

| url = http://arxiv.org/abs/quant-ph/9605043

}}</ref> Classically, &Omega;Ω(''N'') queries are required, even if we allow bounded-error probabilistic algorithms.

=== Quantum counting ===

Quantum counting solves a generalization of the search problem. It solves the problem of counting the number of marked entries in an unordered list, instead of just detecting if one exists. Specifically, it counts the number of marked entries in an <math>N</math>-element list, with error <math>\epsilon</math> making only <math>\Theta\left(\frac{1}{\epsilon} \sqrt{\frac{N}{k}}\right)</math> queries, where <math>k</math> is the number of marked elements in the list.<ref>{{Cite journal

Line 119:

}}</ref><ref>{{cite arxiv|eprint=quant-ph/0005055|author1=Gilles Brassard|title=Quantum Amplitude Amplification and Estimation|class=quant-ph|year=2000|author2=Peter Hoyer|author3=Michele Mosca|author4=Alain Tapp}}</ref>

== Algorithms based on quantum walks ==

{{main|Quantum walk}}

Line 127:

{{main|element distinctness problem}}

The element distinctness problem is the problem of determining whether all the elements of a list are distinct. Classically, &Omega;Ω(''N'') queries are required for a list of size ''N'', since this problem is harder than the search problem which requires &Omega;Ω(''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>A. Ambainis, Quantum walk algorithm for element distinctness, SIAM J. Comput. 37 (2007), no. 1, 210–239, quant-ph/0311001, preliminary version in FOCS 2004.</ref> and the lower bound is due to [[Scott Aaronson]] and Yaoyun Shi.<ref>{{Cite journal | last1=Aaronson | first1=S. | last2=Shi | first2=Y. | title=Quantum lower bounds for the collision and the element distinctness problems | publisher=Association for Computing Machinery, Inc, One Astor Plaza, 1515 Broadway, New York, NY, 10036-5701, USA, | year=2004 | journal=[[Journal of the ACM]] | issn=0004-5411 | volume=51 | issue=4 | pages=595–605 | doi=10.1145/1008731.1008735}}</ref>

===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 &Omega;Ω(''N''), but the best algorithm known requires O(''N''^1.3) queries.<ref>F. Magniez, M. Santha, and [[Mario Szegedy|M. Szegedy]], Quantum algorithms for the triangle problem, Proc. 16th ACM-SIAMSymposium on Discrete Algorithms, pp. 1109–1117, 2005, quant-ph/0310134.</ref>

===Evaluating NAND trees===

The problem is to compute the value of a formula given by a balanced binary tree with bits at the leaves, and NAND gates at the inner vertices.<ref>{{cite web |url=http://scottaaronson.com/blog/?p=207 |title=NAND now for something completely different |author=[[Scott Aaronson]] |date=2007-02-03 |work=Shtetl-Optimized |accessdate=2009-12-17}}</ref> This problem requires &Theta;Θ(''N''^0.753) queries classically, but can be solved in &Theta;Θ(''N''^0.5) queries by a quantum algorithm.<ref>E. Farhi, [[Jeffrey Goldstone|J. Goldstone]], and S. Gutmann, A quantum algorithm for the Hamiltonian NAND tree, Theory of Computing 4 (2008), no. 1, 169–190, quant-ph/0702144</ref>

==Quantum Simulation==

Line 142:

The idea that quantum computers might be more powerful than classical computers originated in Richard Feynman's observation that classical computers seem to require exponential time to simulate many-particle quantum systems.<ref>{{Citation | last1=Feynman | first1=Richard P. | author1-link=Richard Feynman | title=Simulating physics with computers | year=1982 | journal=International Journal of Theoretical Physics | issn=0020-7748 | volume=21 | page=467}}</ref> Since then, the idea that quantum computers can simulate quantum physical processes exponentially faster than classical computers has been greatly fleshed out and elaborated. Efficient (that is, polynomial-time) quantum algorithms have been developed for simulating both Bosonic and Fermionic systems<ref>{{Citation | last1=Abrams | first1=D.S. | last2=Lloyd | first2=Seth | author2-link=Seth Lloyd | title=Simulation of many-body Fermi systems on a universal quantum computer | publisher=APS | year=1997 | journal=[[Physical Review Letters]] | issn=0031-9007 | volume=79 | issue=13 | pages=2586–2589}}. {{arXiv|quant-ph/9703054}}</ref> and in particular, the simulation chemical reactions beyond the capabilities of current classical supercomputers requires only a few hundred qubits.<ref>{{Citation | last1=Kassal | first1=I. | last2=Jordan | first2=S.P. | last3=Love | first3=P.J. | last4=Mohseni | first4=M. | last5=Aspuru-Guzik | first5=A. | title=Polynomial-time quantum algorithm for the simulation of chemical dynamics | year=2008 | journal=[[Proceedings of the National Academy of Sciences|Proceedings of the National Academy of Sciences of the United States of America]] | issn=0027-8424 | volume=105 | issue=48 | pages=18681–18686}}. {{arXiv|0801.2986}}</ref> Quantum computers can also efficiently simulate topological quantum field theories.<ref>{{Citation | last1=Freedman | first1=Michael | last2=Kitaev | first2=Alexei | last3=Wang | first3=Zhenghan | title=Simulation of Topological Field Theories by Quantum Computers | publisher=[[Springer-Verlag]] | ___location=Berlin, New York | year=2002 | journal=Communications in Mathematical Physics | issn=0010-3616 | volume=227 | issue=3 | pages=587–603}}</ref> In addition to its intrinsic interest, this result has let to efficient quantum algorithms for estimating "quantum" topological invariants such as Jones<ref>{{Citation | last1=Aharonov | first1=Dorit | last2=Jones | first2=V. | last3=Landau | first3=Z. | title=A polynomial quantum algorithm for approximating the Jones polynomial | publisher=[[Springer-Verlag]] | ___location=Berlin, New York | year=2009 | journal=Algorithmica | volume=55 | issue=3 | pages=395–421}}. {{arXiv|quant-ph/0511096}}</ref> and HOMFLY<ref>{{Citation | last1=Wocjan | first1=P. | last2=Yard | first2=J. | title=The Jones polynomial: quantum algorithms and applications in quantum complexity theory | year=2008 | journal=Quantum Information and Computation | volume=8 | issue=1 | pages=147–180}}. {{arXiv|quant-ph/0603069}}</ref> polynomials, and the Turaev-Viro invariant of three-dimensional manifolds.<ref>{{Citation | last1=Alagic | first1=G. | last2=Jordan | first2=S.P. | last3=Koenig | first3=R. | last4=Reichardt | first4=Ben W. | title=Approximating Turaev-Viro 3-manifold invariants is universal for quantum computation | year=2010}}. {{arXiv|1003.0923}}</ref>

== References ==

{{reflist|2}}

==External Linkslinks==

*The [http://www.its.caltech.edu/~sjordan/zoo.html Quantum Algorithm Zoo]: A comprehensive list of quantum algorithms that provide a speedup over the fastest known classical algorithms.

{{quantum computing}}

{{DEFAULTSORT:Quantum Algorithm}}

[[Category:Quantum information science]]

[[Category:Theoretical computer science]]