In
quantum computing, a quantum algorithm is an
algorithm
In mathematics and computer science, an algorithm () is a finite sequence of rigorous instructions, typically used to solve a class of specific problems or to perform a computation. Algorithms are used as specifications for performing ...
which runs on a realistic model of
quantum computation, the most commonly used model being the
quantum circuit model of computation. 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 classical
computer
A computer is a machine that can be programmed to carry out sequences of arithmetic or logical operations ( computation) automatically. Modern digital electronic computers can perform generic sets of operations known as programs. These prog ...
. Similarly, a quantum algorithm is a step-by-step procedure, where each of the steps can be performed on a
quantum computer
Quantum computing is a type of computation whose operations can harness the phenomena of quantum mechanics, such as superposition, interference, and entanglement. Devices that perform quantum computations are known as quantum computers. Thoug ...
. Although all classical algorithms can also be performed on a quantum computer, the term quantum algorithm is usually used for those algorithms which seem inherently quantum, or use some essential feature of quantum computation such as
quantum superposition
Quantum superposition is a fundamental principle of quantum mechanics. It states that, much like waves in classical physics, any two (or more) quantum states can be added together ("superposed") and the result will be another valid quantum ...
or
quantum entanglement.
Problems which are
undecidable using classical computers remain undecidable using quantum computers.
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 probably cannot be efficiently simulated on classical computers (see
Quantum supremacy
In quantum computing, quantum supremacy or quantum advantage is the goal of demonstrating that a programmable quantum device can solve a problem that no classical computer can solve in any feasible amount of time (irrespective of the usefulness o ...
).
The best-known algorithms are
Shor's algorithm
Shor's algorithm is a quantum computer algorithm for finding the prime factors of an integer. It was developed in 1994 by the American mathematician Peter Shor.
On a quantum computer, to factor an integer N , Shor's algorithm runs in polynom ...
for factoring and
Grover's algorithm for searching an unstructured database or an unordered list. Shor's algorithms runs much (almost exponentially) faster than the best-known classical algorithm for factoring, the
general number field sieve
In number theory, the general number field sieve (GNFS) is the most efficient classical algorithm known for factoring integers larger than . Heuristically, its complexity for factoring an integer (consisting of bits) is of the form
:\exp\lef ...
. Grover's algorithm runs quadratically faster than the best possible classical algorithm for the same task, a
linear search.
Overview
Quantum algorithms are usually described, in the commonly used circuit model of quantum computation, by a
quantum circuit which acts on some input
qubits and terminates with a
measurement
Measurement is the quantification of attributes of an object or event, which can be used to compare with other objects or events.
In other words, measurement is a process of determining how large or small a physical quantity is as compared ...
. A quantum circuit consists of simple
quantum gates which act on at most a fixed number of qubits. The number of qubits has to be fixed because a changing number of qubits implies non-unitary evolution. Quantum algorithms may also be stated in other models of quantum computation, such as the
Hamiltonian oracle model.
Quantum algorithms can be categorized by the main techniques used by the algorithm. Some commonly used techniques/ideas in quantum algorithms include
phase kick-back,
phase estimation, the
quantum Fourier transform,
quantum walks,
amplitude amplification and
topological quantum field theory. Quantum algorithms may also be grouped by the type of problem solved, for instance see the survey on quantum algorithms for algebraic problems.
Algorithms based on the quantum Fourier transform
The
quantum Fourier transform is the quantum analogue of the
discrete Fourier transform
In mathematics, the discrete Fourier transform (DFT) converts a finite sequence of equally-spaced samples of a function into a same-length sequence of equally-spaced samples of the discrete-time Fourier transform (DTFT), which is a comple ...
, and is used in several quantum algorithms. The
Hadamard transform is also an example of a quantum Fourier transform over an n-dimensional vector space over the field
F2. The quantum Fourier transform can be efficiently implemented on a quantum computer using only a polynomial number of
quantum gates.
Deutsch–Jozsa algorithm
The Deutsch–Jozsa algorithm solves a
black-box
In science, computing, and engineering, a black box is a system which can be viewed in terms of its inputs and outputs (or transfer characteristics), without any knowledge of its internal workings. Its implementation is "opaque" (black). The te ...
problem which probably requires exponentially many queries to the black box for any deterministic classical computer, but can be done with 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).
Bernstein–Vazirani algorithm
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
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
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
Shor's algorithm solves the
discrete logarithm
In mathematics, for given real numbers ''a'' and ''b'', the logarithm log''b'' ''a'' is a number ''x'' such that . Analogously, in any group ''G'', powers ''b'k'' can be defined for all integers ''k'', and the discrete logarithm log''b ...
problem and the
integer factorization
In number theory, integer factorization is the decomposition of a composite number into a product of smaller integers. If these factors are further restricted to prime numbers, the process is called prime factorization.
When the numbers are s ...
problem in polynomial time, 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.
Hidden subgroup problem
The
abelian
Abelian may refer to:
Mathematics Group theory
* Abelian group, a group in which the binary operation is commutative
** Category of abelian groups (Ab), has abelian groups as objects and group homomorphisms as morphisms
* Metabelian group, a grou ...
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
In mathematics, specifically ring theory, a principal ideal is an ideal I in a ring R that is generated by a single element a of R through multiplication by every element of R. The term also has another, similar meaning in order theory, where ...
of a
ring R and
factoring. There are efficient quantum algorithms known for the Abelian hidden subgroup problem. 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 In computer science, lattice problems are a class of optimization problems related to mathematical objects called lattices. The conjectured intractability of such problems is central to the construction of secure lattice-based cryptosystems: La ...
. 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 and the
dihedral group, which would solve certain lattice problems.
Boson sampling problem
The Boson Sampling Problem in an experimental configuration assumes 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
In quantum physics, unitarity is the condition that the time evolution of a quantum state according to the Schrödinger equation is mathematically represented by a unitary operator. This is typically taken as an axiom or basic postulate of qua ...
. The problem is then to produce a fair sample of the
probability distribution
In probability theory and statistics, a probability distribution is the mathematical function that gives the probabilities of occurrence of different possible outcomes for an experiment. It is a mathematical description of a random phenomenon ...
of the output which is dependent on the input arrangement of bosons and the Unitarity. 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 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 the sampling problem had similar complexity for inputs other than
Fock state photons and identified a transition in
computational complexity
In computer science, the computational complexity or simply complexity of an algorithm is the amount of resources required to run it. Particular focus is given to computation time (generally measured by the number of needed elementary operations) ...
from classically simulatable to just as hard as the Boson Sampling Problem, dependent on the size of coherent amplitude inputs.
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.
Fourier fishing and Fourier checking
We have an
oracle
An oracle is a person or agency considered to provide wise and insightful counsel or prophetic predictions, most notably including precognition of the future, inspired by deities. As such, it is a form of divination.
Description
The word ...
consisting of n random Boolean functions mapping n-bit strings to a Boolean value. We are required to find n n-bit strings z
1,..., z
n such that for the Hadamard-Fourier transform, at least 3/4 of the strings satisfy
:
and at least 1/4 satisfies
:
This can be done in
bounded-error quantum polynomial time (BQP).
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
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. 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 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
steps. This is slightly faster than the
steps taken by
Grover's algorithm. Neither search method would allow either model of quantum computer to solve
NP-complete problems in polynomial time.
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
-element list, with error
making only
queries, where
is the number of marked elements in the list. More precisely, the algorithm outputs an estimate
for
, the number of marked entries, with the following accuracy:
.
Algorithms based on quantum walks
A quantum walk is the quantum analogue of a classical
random walk
In mathematics, a random walk is a random process that describes a path that consists of a succession of random steps on some mathematical space.
An elementary example of a random walk is the random walk on the integer number line \mathbb Z ...
, which can be described by a
probability distribution
In probability theory and statistics, a probability distribution is the mathematical function that gives the probabilities of occurrence of different possible outcomes for an experiment. It is a mathematical description of a random phenomenon ...
over some states. A quantum walk can be described by a
quantum superposition
Quantum superposition is a fundamental principle of quantum mechanics. It states that, much like waves in classical physics, any two (or more) quantum states can be added together ("superposed") and the result will be another valid quantum ...
over states. Quantum walks are known to give exponential speedups for some black-box problems. They also provide polynomial speedups for many problems. A framework for the creation of quantum walk algorithms exists and is quite a versatile tool.
[
]
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''. However, it can be solved in queries on a quantum computer. The optimal algorithm is by Andris Ambainis
Andris Ambainis (born 18 January 1975) is a Latvian computer scientist active in the fields of quantum information theory and quantum computing.
Education and career
Ambainis has held past positions at the Institute for Advanced Study at Princet ...
. Yaoyun Shi first proved a tight lower bound when the size of the range is sufficiently large. Ambainis and Kutin independently (and via different proofs) extended his work to obtain the lower bound for all functions.
Triangle-finding problem
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, an improvement over the previous best O(''N''1.3) queries.[
]
Formula evaluation
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. This type of formula requires Θ(''N''c) queries using randomness, where . 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.[ The same result for the standard setting soon followed.
Fast quantum algorithms for more complicated formulas are also known.
]
Group commutativity
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 and respectively. A quantum algorithm requires queries but the best known algorithm uses queries.
BQP-complete problems
The complexity class
In computational complexity theory, a complexity class is a set of computational problems of related resource-based complexity. The two most commonly analyzed resources are time and memory.
In general, a complexity class is defined in terms o ...
BQP (bounded-error quantum polynomial time) is the set of decision problems solvable by a quantum computer
Quantum computing is a type of computation whose operations can harness the phenomena of quantum mechanics, such as superposition, interference, and entanglement. Devices that perform quantum computations are known as quantum computers. Thoug ...
in polynomial time
In computer science, the time complexity is the computational complexity that describes the amount of computer time it takes to run an algorithm. Time complexity is commonly estimated by counting the number of elementary operations performed by ...
with error probability of at most 1/3 for all instances.[Michael Nielsen and Isaac Chuang (2000). ''Quantum Computation and Quantum Information''. Cambridge: Cambridge University Press. .] It is the quantum analogue to the classical complexity class BPP.
A problem is BQP-complete if it is in BQP and any problem in BQP can be reduced to it in polynomial time
In computer science, the time complexity is the computational complexity that describes the amount of computer time it takes to run an algorithm. Time complexity is commonly estimated by counting the number of elementary operations performed by ...
. Informally, the class of BQP-complete problems are those that are as hard as the hardest problems in BQP and are themselves efficiently solvable by a quantum computer (with bounded error).
Computing knot invariants
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, which as far as we know, is hard to compute classically in the worst-case scenario.
Quantum simulation
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. 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 and in particular, the simulation of chemical reactions beyond the capabilities of current classical supercomputers requires only a few hundred qubits. Quantum computers can also efficiently simulate topological quantum field theories. In addition to its intrinsic interest, this result has led to efficient quantum algorithms for estimating quantum topological invariants such as Jones and HOMFLY polynomial
In the mathematical field of knot theory, the HOMFLY polynomial or HOMFLYPT polynomial, sometimes called the generalized Jones polynomial, is a 2-variable knot polynomial, i.e. a knot invariant in the form of a polynomial of variables ''m'' an ...
s, and the Turaev-Viro invariant of three-dimensional manifolds.
Solving a linear systems of equations
In 2009 Aram Harrow
Aram Wettroth Harrow (born 1980) is a professor of physics in the Massachusetts Institute of Technology's Center for Theoretical Physics.
Harrow works in quantum information science and quantum computing. Together with Avinatan Hassidim and Set ...
, Avinatan Hassidim, and Seth Lloyd, formulated a quantum algorithm for solving linear systems. The algorithm
In mathematics and computer science, an algorithm () is a finite sequence of rigorous instructions, typically used to solve a class of specific problems or to perform a computation. Algorithms are used as specifications for performing ...
estimates the result of a scalar measurement on the solution vector to a given linear system of equations.
Provided the linear system is a sparse and has a low condition 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
Hybrid Quantum/Classical Algorithms combine quantum state preparation and measurement with classical optimization. These algorithms generally aim to determine the ground state eigenvector and eigenvalue of a Hermitian Operator.
QAOA
The quantum approximate optimization algorithm is a toy model of quantum annealing which can be used to solve problems in graph theory. The algorithm makes use of classical optimization of quantum operations to maximize an objective function.
Variational quantum eigensolver
The variational quantum eigensolver (VQE) algorithm applies classical optimization to minimize the energy expectation of an ansatz state to find the ground state energy of a molecule. This can also be extended to find excited energies of molecules.
Contracted quantum eigensolver
The 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. It is based on classical methods for solving energies and two-electron reduced density matrices directly from the anti-Hermitian contracted Schrödinger equation.
See also
* Quantum machine learning
Quantum machine learning is the integration of quantum algorithms within machine learning programs. The most common use of the term refers to machine learning algorithms for the analysis of classical data executed on a quantum computer, i.e. quan ...
* Quantum optimization algorithms
Quantum optimization algorithms are quantum algorithms that are used to solve optimization problems. Mathematical optimization deals with finding the best solution to a problem (according to some criteria) from a set of possible solutions. Mostl ...
* Quantum sort
* Primality test
References
External links
* Th
Quantum Algorithm Zoo
A comprehensive list of quantum algorithms that provide a speedup over the fastest known classical algorithms.
Andrew Childs' lecture notes on quantum algorithms
The Quantum search algorithm - brute force
Surveys
*
*
{{DEFAULTSORT:Quantum Algorithm
Quantum computing
Theoretical computer science
Emerging technologies