Quantum 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).

The Bernstein–Vazirani algorithm is the first quantum algorithm that solves a problem more efficiently than the best known classical algorithm. It was designed to create an oracle separation between BQP and BPP.

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.

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 solves the discrete logarithm problem and the integer factorization problem in polynomial time,[8] whereas the best known classical algorithms take super-polynomial time. These problems are not known to be in P or NP-complete. It is also one of the few quantum algorithms that solves a non–black-box problem in polynomial time where the best known classical algorithms run in super-polynomial time.

The 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 R and factoring. There are efficient quantum algorithms known for the Abelian hidden subgroup problem.[9] 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[10] and the dihedral group, which would solve certain lattice problems.[11]

The Boson Sampling Problem in an experimental configuration assumes[12] an input of bosons (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.[13] 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[14] that existing technology and standard probabilistic methods of generating single photon states could be used as input into a suitable quantum computable linear optical network and that sampling of the output probability distribution would be demonstrably superior using quantum algorithms. In 2015, investigation predicted[15] 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.

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.[16]

We have an oracle consisting of n random Boolean functions mapping n-bit strings to a Boolean value. We are required to find n n-bit strings z₁,..., z_n such that for the Hadamard-Fourier transform, at least 3/4 of the strings satisfy

${\displaystyle |{\tilde {f}}(z_{i})|\geqslant 1}$

and at least 1/4 satisfies

${\displaystyle |{\tilde {f}}(z_{i})|\geqslant 2.}$

This can be done in bounded-error quantum polynomial time (BQP).[17]

Grover's algorithm searches an unstructured database (or an unordered list) with N entries, for a marked entry, using only ${\displaystyle O({\sqrt {N}})}$ queries instead of the ${\displaystyle O({N})}$ queries required classically.[18] Classically, ${\displaystyle O({N})}$ queries are required even allowing bounded-error probabilistic algorithms.

Theorists have considered a hypothetical generalization of a standard quantum computer that could access the histories of the hidden variables in Bohmian mechanics. (Such a computer is completely hypothetical and would not be a standard quantum computer, or even possible under the standard theory of quantum mechanics.) Such a hypothetical computer could implement a search of an N-item database at most in ${\displaystyle O({\sqrt[{3}]{N}})}$ steps. This is slightly faster than the ${\displaystyle O({\sqrt {N}})}$ steps taken by Grover's algorithm. Neither search method would allow either model of quantum computer to solve NP-complete problems in polynomial time.[19]

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 ${\displaystyle N}$-element list, with error ${\displaystyle \varepsilon }$ making only ${\displaystyle \Theta \left({\frac {1}{\varepsilon }}{\sqrt {\frac {N}{k}}}\right)}$ queries, where ${\displaystyle k}$ is the number of marked elements in the list.[20][21] More precisely, the algorithm outputs an estimate ${\displaystyle k'}$ for ${\displaystyle k}$, the number of marked entries, with the following accuracy: ${\displaystyle |k-k'|\leq \varepsilon k}$.

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. However, it can be solved in ${\displaystyle \Theta (N^{2/3})}$ queries on a quantum computer. The optimal algorithm is by Andris Ambainis.[25] Yaoyun Shi first proved a tight lower bound when the size of the range is sufficiently large.[26] Ambainis[27] and Kutin[28] independently (and via different proofs) extended his work to obtain the lower bound for all functions.

The triangle-finding problem is the problem of determining whether a given graph contains a triangle (a 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,[29] an improvement over the previous best O(N^1.3) queries.[24][30]

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.[31] This type of formula requires Θ(N^c) queries using randomness,[32] where ${\displaystyle c=\log _{2}(1+{\sqrt {33}})/4\approx 0.754}$. With a quantum algorithm however, it can be solved in Θ(N^0.5) queries. No better quantum algorithm for this case was known until one was found for the unconventional Hamiltonian oracle model.[6] The same result for the standard setting soon followed.[33]

Fast quantum algorithms for more complicated formulas are also known.[34]

The problem is to determine if a black box group, given by k generators, is 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). We are interested in the query complexity, which is the number of oracle calls needed to solve the problem. The deterministic and randomized query complexities are ${\displaystyle \Theta (k^{2})}$ and ${\displaystyle \Theta (k)}$ respectively.[35] A quantum algorithm requires ${\displaystyle \Omega (k^{2/3})}$ queries but the best known algorithm uses ${\displaystyle O(k^{2/3}\log k)}$ queries.[36]

Witten had shown that the Chern-Simons topological quantum field theory (TQFT) can be solved in terms of Jones polynomials. A quantum computer can simulate a TQFT, and thereby approximate the Jones polynomial,[38] which as far as we know, is hard to compute classically in the worst-case scenario.

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.[39] 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[40] and in particular, the simulation of chemical reactions beyond the capabilities of current classical supercomputers requires only a few hundred qubits.[41] Quantum computers can also efficiently simulate topological quantum field theories.[42] In addition to its intrinsic interest, this result has led to efficient quantum algorithms for estimating quantum topological invariants such as Jones[43] and HOMFLY polynomials,[44] and the Turaev-Viro invariant of three-dimensional manifolds.[45]

In 2009 Aram Harrow, Avinatan Hassidim, and Seth Lloyd, formulated a quantum algorithm for solving linear systems. The algorithm estimates the result of a scalar measurement on the solution vector to a given linear system of equations.[46]

Provided the linear system is a sparse and has a low condition number ${\displaystyle \kappa }$, and that the user is interested in the result of a scalar measurement on the solution vector, instead of the values of the solution vector itself, then the algorithm has a runtime of ${\displaystyle O(\log(N)\kappa ^{2})}$, where ${\displaystyle N}$ is the number of variables in the linear system. This offers an exponential speedup over the fastest classical algorithm, which runs in ${\displaystyle O(N\kappa )}$ (or ${\displaystyle O(N{\sqrt {\kappa }})}$ for positive semidefinite matrices).

The quantum approximate optimization algorithm is a toy model of quantum annealing which can be used to solve problems in graph theory.[48] The algorithm makes use of classical optimization of quantum operations to maximize an objective function.

The VQE algorithm applies classical optimization to minimize the energy expectation of an ansatz state to find the ground state energy of a molecule.[49] This can also be extended to find excited energies of molecules.[50]

• Smith, J.; Mosca, M. (2012). "Algorithms for Quantum Computers". Handbook of Natural Computing. p. 1451. doi:10.1007/978-3-540-92910-9_43. ISBN 978-3-540-92909-3. S2CID 16565723.
• Childs, A. M.; Van Dam, W. (2010). "Quantum algorithms for algebraic problems". Reviews of Modern Physics. 82 (1): 1–52. arXiv:0812.0380. Bibcode:2010RvMP...82....1C. doi:10.1103/RevModPhys.82.1. S2CID 119261679.