Inquantum computing, aquantum algorithm is analgorithm that runs on a realistic model ofquantum computation, the most commonly used model being thequantum circuit model of computation.[1][2] 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 classicalcomputer. Similarly, a quantum algorithm is a step-by-step procedure, where each of the steps can be performed on aquantum computer. Although all classical algorithms can also be performed on a quantum computer,[3]: 126 the term quantum algorithm is generally reserved for algorithms that seem inherently quantum, or use some essential feature of quantum computation such asquantum superposition orquantum entanglement.
Problems that areundecidable using classical computers remain undecidable using quantum computers.[4]: 127 What makes quantum algorithms interesting is that they might be able to solve some problems faster than classical algorithms because the quantum superposition and quantum entanglement that quantum algorithms exploit generally cannot be efficiently simulated on classical computers (seeQuantum supremacy).
The best-known algorithms areShor's algorithm for factoring andGrover's algorithm for searching an unstructured database or an unordered list. Shor's algorithm would, if implemented, run much (almost exponentially) faster than the most efficient known classical algorithm for factoring, thegeneral number field sieve.[5] Likewise, Grover's algorithm would run quadratically faster than the best possible classical algorithm for the same task,[6] alinear search.
Quantum algorithms are usually described, in the commonly used circuit model of quantum computation, by aquantum circuit that acts on some inputqubits and terminates with ameasurement. A quantum circuit consists of simplequantum gates, each of which acts on some finite number of qubits. Quantum algorithms may also be stated in other models of quantum computation, such as theHamiltonian oracle model.[7]
Quantum algorithms can be categorized by the main techniques involved in the algorithm. Some commonly used techniques/ideas in quantum algorithms includephase kick-back,phase estimation, thequantum Fourier transform,quantum walks,amplitude amplification andtopological quantum field theory. Quantum algorithms may also be grouped by the type of problem solved; see, e.g., the survey on quantum algorithms for algebraic problems.[8]
Thequantum Fourier transform is the quantum analogue of thediscrete Fourier transform, and is used in several quantum algorithms. TheHadamard transform is also an example of a quantum Fourier transform over an n-dimensional vector space over the fieldF2. The quantum Fourier transform can be efficiently implemented on a quantum computer using only a polynomial number ofquantum gates.[citation needed]
The Deutsch–Jozsa algorithm solves ablack-box problem that requires exponentially many queries to the black box for any deterministic classical computer, but can be done with a single query by a quantum computer. However, when comparing bounded-error classical and quantum algorithms, 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 functionf 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 anoracle separation betweenBQP andBPP.
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 forShor's algorithm for factoring.
Thequantum 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 thediscrete logarithm problem and theinteger factorization problem in polynomial time,[9] whereas the best known classical algorithms take super-polynomial time. It is unknown whether these problems are inP orNP-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.
Theabelianhidden subgroup problem is a generalization of many problems that can be solved by a quantum computer, such as Simon's problem, solvingPell's equation, testing theprincipal ideal of aring R andfactoring. There are efficient quantum algorithms known for the Abelian hidden subgroup problem.[10] The more general hidden subgroup problem, where the group is not necessarily abelian, is a generalization of the previously mentioned problems, as well asgraph isomorphism and certainlattice problems. Efficient quantum algorithms are known for certain non-abelian groups. However, no efficient algorithms are known for thesymmetric group, which would give an efficient algorithm for graph isomorphism[11] and thedihedral group, which would solve certain lattice problems.[12]
AGauss sum is a type ofexponential 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.[13]
Consider anoracle consisting ofn random Boolean functions mappingn-bit strings to a Boolean value, with the goal of finding nn-bit stringsz1,...,zn such that for the Hadamard-Fourier transform, at least 3/4 of the strings satisfy
and at least 1/4 satisfy
This can be done inbounded-error quantum polynomial time (BQP).[14]
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 as a generalization of Grover's algorithm.[citation needed]
Grover's algorithm searches an unstructured database (or an unordered list) with N entries for a marked entry, using only queries instead of the queries required classically.[15] Classically, 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 inBohmian mechanics. (Such a computer is completely hypothetical and wouldnot 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 in at most steps. This is slightly faster than the steps taken by Grover's algorithm. However, neither search method would allow either model of quantum computer to solveNP-complete problems in polynomial time.[16]
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 whether one exists. Specifically, it counts the number of marked entries in an-element list with an error of at most by making only queries, where is the number of marked elements in the list.[17][18] More precisely, the algorithm outputs an estimate for, the number of marked entries, with accuracy.
A quantum walk is the quantum analogue of a classicalrandom walk. A classical random walk can be described by aprobability distribution over some states, while a quantum walk can be described by aquantum superposition over states. Quantum walks are known to give exponential speedups for some black-box problems.[19][20] They also provide polynomial speedups for many problems. A framework for the creation of quantum walk algorithms exists and is a versatile tool.[21]
The Boson Sampling Problem in an experimental configuration assumes[22] an input ofbosons (e.g., photons) of moderate number that are randomly scattered into a large number of output modes, constrained by a definedunitarity. When individual photons are used, the problem is isomorphic to a multi-photon quantum walk.[23] The problem is then to produce a fair sample of theprobability distribution of the output that depends on the input arrangement of bosons and the unitarity.[24] Solving this problem with a classical computer algorithm requires computing thepermanent of the unitary transform matrix, which may take a prohibitively long time or be outright impossible. In 2014, it was proposed[25] that existing technology and standard probabilistic methods of generating single-photon states could be used as an input into a suitable quantum computablelinear optical network and that sampling of the output probability distribution would be demonstrably superior using quantum algorithms. In 2015, investigation predicted[26] the sampling problem had similar complexity for inputs other thanFock-state photons and identified a transition incomputational complexity from classically simulable to just as hard as the Boson Sampling Problem, depending on the size of coherent amplitude inputs.
The element distinctness problem is the problem of determining whether all the elements of a list are distinct. Classically, queries are required for a list of size; however, it can be solved in queries on a quantum computer. The optimal algorithm was put forth byAndris Ambainis,[27] andYaoyun Shi first proved a tight lower bound when the size of the range is sufficiently large.[28] Ambainis[29] and Kutin[30] independently (and via different proofs) extended that work to obtain the lower bound for all functions.
The triangle-finding problem is the problem of determining whether a given graph withN vertices contains a triangle (aclique of size 3). Given oracle access to the adjacency matrix of the graph, the classical query complexity is, since for a graph with only one triangle this is the query complexity needed to find any edge at all. Meanwhile, for quantum algorithms the lower bound is, the number of queries needed to find any edge with Grover's algorithm. However, finding any edge does not guarantee finding a triangle if there exists any. A Grover search over all potential triangles does solve the problem, but the query complexity, O(N3/2), can be improved upon.[31]
While remains the best-known lower bound for quantum algorithms, the best algorithm known requires O(N5/4) queries,[32] an improvement over the previous best O(N1.3) queries.[21][33]
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.[34] This type of formula requires queries using randomness,[35] where. With a quantum algorithm, however, it can be solved in queries. No better quantum algorithm for this case was known until one was found for the unconventional Hamiltonian oracle model.[7] The same result for the standard setting soon followed.[36]
Fast quantum algorithms for more complicated formulas are also known.[37]
The problem is to determine if ablack-box group, given byk generators, iscommutative. 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). The interest in this context lies in the query complexity, which is the number of oracle calls needed to solve the problem. The deterministic and randomized query complexities are and, respectively.[38] A quantum algorithm requires queries, while the best-known classical algorithm uses queries.[39]
Thecomplexity classBQP (bounded-error quantum polynomial time) is the set ofdecision problems solvable by aquantum computer inpolynomial time with error probability of at most 1/3 for all instances.[40] It is the quantum analogue to the classical complexity classBPP.
A problem isBQP-complete if it is inBQP and any problem inBQP can bereduced to it inpolynomial time. Informally, the class ofBQP-complete problems are those that are as hard as the hardest problems inBQP and are themselves efficiently solvable by a quantum computer (with bounded error).
Witten had shown that theChern-Simonstopological quantum field theory (TQFT) can be solved in terms ofJones polynomials. A quantum computer can simulate a TQFT, and thereby approximate the Jones polynomial,[41] which as far as we know, is hard to compute classically in the worst-case scenario.[citation needed]
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, yet quantum many-body systems are able to "solve themselves."[42] 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 (i.e., polynomial-time) quantum algorithms have been developed for simulating both Bosonic and Fermionic systems,[43] as well as the simulation of chemical reactions beyond the capabilities of current classical supercomputers using only a few hundred qubits.[44] Quantum computers can also efficiently simulate topological quantum field theories.[45] In addition to its intrinsic interest, this result has led to efficient quantum algorithms for estimatingquantum topological invariants such asJones[46] andHOMFLY polynomials,[47] and theTuraev-Viro invariant of three-dimensional manifolds.[48]
In 2009,Aram Harrow, Avinatan Hassidim, andSeth Lloyd, formulated a quantum algorithm for solvinglinear systems. Thealgorithm estimates the result of a scalar measurement on the solution vector to a given linear system of equations.[49]
Provided that the linear system issparse and has a lowcondition number, 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, where is the number of variables in the linear system. This offers an exponential speedup over the fastest classical algorithm, which runs in (or for positive semidefinite matrices).
Hybrid Quantum/Classical Algorithms combine quantum state preparation and measurement with classical optimization.[50] These algorithms generally aim to determine the ground-state eigenvector and eigenvalue of a Hermitian operator.
Thequantum approximate optimization algorithm takes inspiration from quantum annealing, performing a discretized approximation of quantum annealing using a quantum circuit. It can be used to solve problems in graph theory.[51] The algorithm makes use of classical optimization of quantum operations to maximize an "objective function."
Thevariational quantum eigensolver (VQE) algorithm applies classical optimization to minimize the energy expectation value of anansatz state to find the ground state of a Hermitian operator, such as a molecule's Hamiltonian.[52] It can also be extended to find excited energies of molecular Hamiltonians.[53]
The contracted quantum eigensolver (CQE) algorithm minimizes the residual of a contraction (or projection) of the Schrödinger equation onto the space of two (or more) electrons to find the ground- or excited-state energy and two-electron reduced density matrix of a molecule.[54] It is based on classical methods for solving energies and two-electron reduced density matrices directly from the anti-Hermitian contracted Schrödinger equation.[55]
| General | |||||||||
|---|---|---|---|---|---|---|---|---|---|
| Theorems | |||||||||
| Quantum communication |
| ||||||||
| Quantum algorithms | |||||||||
| Quantum complexity theory | |||||||||
| Quantum processor benchmarks | |||||||||
| Quantum computing models | |||||||||
| Quantum error correction | |||||||||
| Physical implementations |
| ||||||||
| Quantum programming | |||||||||
