Quantum algorithm

Last updated

In quantum computing, a quantum algorithm is an algorithm which runs on a realistic model of quantum computation, the most commonly used model being the quantum 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 classical computer. Similarly, a quantum algorithm is a step-by-step procedure, where each of the steps can be performed on a quantum computer. Although all classical algorithms can also be performed on a quantum computer, [3] :126 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 or quantum entanglement.


Problems which are undecidable 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 probably cannot be efficiently simulated on classical computers (see Quantum supremacy).

The best-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 much (almost exponentially) faster than the best-known classical algorithm for factoring, the general number field sieve. [5] Grover's algorithm runs quadratically faster than the best possible classical algorithm for the same task,[ citation needed ] a linear search.


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

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

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 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.[ citation needed ]

Deutsch–Jozsa algorithm

Deutsch-Jozsa algorithm Deutsch-Jozsa-algorithm-quantum-circuit.png
Deutsch-Jozsa 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).

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 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 nonblack-box problem in polynomial time where the best known classical algorithms run in super-polynomial time.

Hidden subgroup problem

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]

Boson sampling problem

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.

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

Fourier fishing and Fourier checking

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 z1,..., zn 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). [17]

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. [18] 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. [19]

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. [20] [21] 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, 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. [22] [23] They also provide polynomial speedups for many problems. A framework for the creation of quantum walk algorithms exists and is quite a versatile tool. [24]

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

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(N1.297) queries, [29] an improvement over the previous best O(N1.3) queries. [24] [30]

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. [31] This type of formula requires Θ(Nc) queries using randomness, [32] where . With a quantum algorithm however, it can be solved in Θ(N0.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]

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. [35] A quantum algorithm requires queries but the best known algorithm uses queries. [36]

BQP-complete problems

The complexity class BQP (bounded-error quantum polynomial time) is the set of decision problems solvable by a quantum computer in polynomial time with error probability of at most 1/3 for all instances. [37] 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. 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, [38] which as far as we know, is hard to compute classically in the worst-case scenario.[ citation needed ]

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

Solving a linear systems of equations

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 , 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. [47] These algorithms generally aim to determine the ground state eigenvector and eigenvalue of a Hermitian Operator.


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.

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. [49] This can also be extended to find excited energies of molecules. [50]

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. [51] It is based on classical methods for solving energies and two-electron reduced density matrices directly from the anti-Hermitian contracted Schrödinger equation. [52]

See also

Related Research Articles

In computational complexity theory, bounded-error quantum polynomial time (BQP) is the class of decision problems solvable by a quantum computer in polynomial time, with an error probability of at most 1/3 for all instances. It is the quantum analogue to the complexity class BPP.

Quantum computing Study of a model of computation

Quantum computing is the exploitation of collective properties of quantum states, such as superposition and entanglement, to perform computation. The devices that perform quantum computations are known as quantum computers. They are believed to be able to solve certain computational problems, such as integer factorization, substantially faster than classical computers. The study of quantum computing is a subfield of quantum information science. Expansion is expected in the next few years as the field shifts toward real-world use in pharmaceutical, data security and other applications.

Shor's algorithm is a polynomial-time quantum computer algorithm for integer factorization. Informally, it solves the following problem: Given an integer , find its prime factors. It was discovered in 1994 by the American mathematician Peter Shor.

In quantum computing, Grover's algorithm, also known as the quantum search algorithm, refers to a quantum algorithm for unstructured search that finds with high probability the unique input to a black box function that produces a particular output value, using just evaluations of the function, where is the size of the function's domain. It was devised by Lov Grover in 1996.

Time complexity Estimate of time taken for running an algorithm

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 the algorithm, supposing that each elementary operation takes a fixed amount of time to perform. Thus, the amount of time taken and the number of elementary operations performed by the algorithm are taken to differ by at most a constant factor.

PP (complexity) Class of problems in computer science

In complexity theory, PP is the class of decision problems solvable by a probabilistic Turing machine in polynomial time, with an error probability of less than 1/2 for all instances. The abbreviation PP refers to probabilistic polynomial time. The complexity class was defined by Gill in 1977.

The hidden subgroup problem (HSP) is a topic of research in mathematics and theoretical computer science. The framework captures problems like factoring, discrete logarithm, graph isomorphism, and the shortest vector problem. This makes it especially important in the theory of quantum computing because Shor's quantum algorithm for factoring is essentially equivalent to the hidden subgroup problem for finite Abelian groups, while the other problems correspond to finite groups that are not Abelian.

Quantum annealing (QA) is a metaheuristic for finding the global minimum of a given objective function over a given set of candidate solutions, by a process using quantum fluctuations. Quantum annealing is used mainly for problems where the search space is discrete with many local minima; such as finding the ground state of a spin glass or the traveling salesman problem. Quantum annealing was first proposed in 1988 by B. Apolloni, N. Cesa Bianchi and D. De Falco. It was formulated in its present form by T. Kadowaki and H. Nishimori in "Quantum annealing in the transverse Ising model" though a proposal in a different form had been made by A. B. Finnila, M. A. Gomez, C. Sebenik and J. D. Doll, in Quantum annealing is a new method for minimizing multidimensional functions".

Adiabatic quantum computation (AQC) is a form of quantum computing which relies on the adiabatic theorem to do calculations and is closely related to quantum annealing.

In computational complexity theory, QMA, which stands for Quantum Merlin Arthur, is the set of languages for which, when the answer is YES, there is a polynomial-size quantum proof that convinces a polynomial time quantum verifier of this fact with high probability. Moreover, when the answer is NO, every polynomial-size quantum state is rejected by the verifier with high probability.

Quantum complexity theory is the subfield of computational complexity theory that deals with complexity classes defined using quantum computers, a computational model based on quantum mechanics. It studies the hardness of computational problems in relation to these complexity classes, as well as the relationship between quantum complexity classes and classical complexity classes.

Quantum finance is an interdisciplinary research field, applying theories and methods developed by quantum physicists and economists in order to solve problems in finance. It is a branch of econophysics.

In quantum computing, the Brasard-Hoyer-Tappar algorithm or BHT algorithm is a quantum algorithm that solves the collision problem. In this problem, one is given n and an r-to-1 function and needs to find two inputs that f maps to the same output. The BHT algorithm only makes queries to f, which matches the lower bound of in the black box model.

The quantum algorithm for linear systems of equations, also called HHL algorithm, designed by Aram Harrow, Avinatan Hassidim, and Seth Lloyd, is a quantum algorithm formulated in 2009 for solving linear systems. The algorithm estimates the result of a scalar measurement on the solution vector to a given linear system of equations.

Quantum machine learning Interdisciplinary research area at the intersection of quantum physics and 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. quantum-enhanced machine learning. While machine learning algorithms are used to compute immense quantities of data, quantum machine learning utilizes qubits and quantum operations or specialized quantum systems to improve computational speed and data storage done by algorithms in a program. This includes hybrid methods that involve both classical and quantum processing, where computationally difficult subroutines are outsourced to a quantum device. These routines can be more complex in nature and executed faster on a quantum computer. Furthermore, quantum algorithms can be used to analyze quantum states instead of classical data. Beyond quantum computing, the term "quantum machine learning" is also associated with classical machine learning methods applied to data generated from quantum experiments, such as learning the phase transitions of a quantum system or creating new quantum experiments. Quantum machine learning also extends to a branch of research that explores methodological and structural similarities between certain physical systems and learning systems, in particular neural networks. For example, some mathematical and numerical techniques from quantum physics are applicable to classical deep learning and vice versa. Furthermore, researchers investigate more abstract notions of learning theory with respect to quantum information, sometimes referred to as "quantum learning theory".

Andrew MacGregor Childs is an American computer scientist and physicist known for his work on quantum computing. He is currently a Professor in the Department of Computer Science and Institute for Advanced Computer Studies at the University of Maryland. He also co-directs the Joint Center for Quantum Information and Computer Science, a partnership between the University of Maryland and the National Institute of Standards and Technology.

Boson sampling constitutes a restricted model of non-universal quantum computation introduced by S. Aaronson and A. Arkhipov after the original work of L. Troyansky and N. Tishby, that explored possible usage of boson scattering to evaluate expectation values of permanents of matrices. The model consists of sampling from the probability distribution of identical bosons scattered by a linear interferometer. Although the problem is well defined for any bosonic particles, its photonic version is currently considered as the most promising platform for a scalable implementation of a boson sampling device, which makes it a non-universal approach to linear optical quantum computing. Moreover, while not universal, the boson sampling scheme is strongly believed to implement computing tasks, which are hard to implement with classical computers, by using far fewer physical resources than a full linear-optical quantum computing setup. This makes it an ideal candidate for demonstrating the power of quantum computation in the near term.

Quantum optimization algorithms are quantum algorithms that are used to solve optimization problems. Mathematical optimization deals with finding the best solution to a problem from a set of possible solutions. Mostly, the optimization problem is formulated as a minimization problem, where one tries to minimize an error which depends on the solution: the optimal solution has the minimal error. Different optimization techniques are applied in various fields such as mechanics, economics and engineering, and as the complexity and amount of data involved rise, more efficient ways of solving optimization problems are needed. The power of quantum computing may allow problems which are not practically feasible on classical computers to be solved, or suggest a considerable speed up with respect to the best known classical algorithm.

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. Conceptually, quantum supremacy involves both the engineering task of building a powerful quantum computer and the computational-complexity-theoretic task of finding a problem that can be solved by that quantum computer and has a superpolynomial speedup over the best known or possible classical algorithm for that task. The term was coined by John Preskill in 2012, but the concept of a quantum computational advantage, specifically for simulating quantum systems, dates back to Yuri Manin's (1980) and Richard Feynman's (1981) proposals of quantum computing. Examples of proposals to demonstrate quantum supremacy include the boson sampling proposal of Aaronson and Arkhipov, D-Wave's specialized frustrated cluster loop problems, and sampling the output of random quantum circuits.

Continuous-variable (CV) quantum information is the area of quantum information science that makes use of physical observables, like the strength of an electromagnetic field, whose numerical values belong to continuous intervals. One primary application is quantum computing. In a sense, continuous-variable quantum computation is "analog", while quantum computation using qubits is "digital." In more technical terms, the former makes use of Hilbert spaces that are infinite-dimensional, while the Hilbert spaces for systems comprising collections of qubits are finite-dimensional. One motivation for studying continuous-variable quantum computation is to understand what resources are necessary to make quantum computers more powerful than classical ones.


  1. Nielsen, Michael A.; Chuang, Isaac L. (2000). Quantum Computation and Quantum Information. Cambridge University Press. ISBN   978-0-521-63503-5.
  2. Mosca, M. (2008). "Quantum Algorithms". arXiv: 0808.0369 [quant-ph].
  3. Lanzagorta, Marco; Uhlmann, Jeffrey K. (1 January 2009). Quantum Computer Science. Morgan & Claypool Publishers. ISBN   9781598297324.
  4. Nielsen, Michael A.; Chuang, Isaac L. (2010). Quantum Computation and Quantum Information (2nd ed.). Cambridge: Cambridge University Press. ISBN   978-1-107-00217-3.
  5. "Shor's algorithm".
  6. 1 2 Farhi, E.; Goldstone, J.; Gutmann, S. (2007). "A Quantum Algorithm for the Hamiltonian NAND Tree". arXiv: quant-ph/0702144 .
  7. Childs, Andrew 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.
  8. Shor, P. W. (1997). "Polynomial-Time Algorithms for Prime Factorization and Discrete Logarithms on a Quantum Computer". SIAM Journal on Scientific and Statistical Computing . 26 (5): 1484–1509. arXiv: quant-ph/9508027 . Bibcode:1995quant.ph..8027S. doi:10.1137/s0097539795293172. S2CID   2337707.
  9. Boneh, D.; Lipton, R. J. (1995). "Quantum cryptoanalysis of hidden linear functions". In Coppersmith, D. (ed.). Proceedings of the 15th Annual International Cryptology Conference on Advances in Cryptology. Springer-Verlag. pp. 424–437. ISBN   3-540-60221-6.
  10. Moore, C.; Russell, A.; Schulman, L. J. (2005). "The Symmetric Group Defies Strong Fourier Sampling: Part I". arXiv: quant-ph/0501056 .
  11. Regev, O. (2003). "Quantum Computation and Lattice Problems". arXiv: cs/0304005 .
  12. Ralph, T.C. (July 2013). "Figure 1: The boson-sampling problem". Nature Photonics. Nature. 7 (7): 514–515. doi:10.1038/nphoton.2013.175 . Retrieved 12 September 2014.
  13. Lund, A.P.; Laing, A.; Rahimi-Keshari, S.; Rudolph, T.; O'Brien, J.L.; Ralph, T.C. (5 September 2014). "Boson Sampling from Gaussian States". Phys. Rev. Lett. 113 (10): 100502. arXiv: 1305.4346 . Bibcode:2014PhRvL.113j0502L. doi:10.1103/PhysRevLett.113.100502. PMID   25238340. S2CID   27742471.
  14. "The quantum revolution is a step closer". Phys.org. Omicron Technology Limited. Retrieved 12 September 2014.
  15. Seshadreesan, Kaushik P.; Olson, Jonathan P.; Motes, Keith R.; Rohde, Peter P.; Dowling, Jonathan P. (2015). "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". Physical Review A. 91 (2): 022334. arXiv: 1402.0531 . Bibcode:2015PhRvA..91b2334S. doi:10.1103/PhysRevA.91.022334. S2CID   55455992.
  16. van Dam, W.; Seroussi, G. (2002). "Efficient Quantum Algorithms for Estimating Gauss Sums". arXiv: quant-ph/0207131 .
  17. Aaronson, S. (2009). "BQP and the Polynomial Hierarchy". arXiv: 0910.4698 [quant-ph].
  18. Grover, Lov K. (1996). "A fast quantum mechanical algorithm for database search". arXiv: quant-ph/9605043 .
  19. Aaronson, Scott. "Quantum Computing and Hidden Variables" (PDF).
  20. Brassard, G.; Hoyer, P.; Tapp, A. (1998). Quantum Counting. Lecture Notes in Computer Science. 1443. pp. 820–831. arXiv: quant-ph/9805082 . doi:10.1007/BFb0055105. ISBN   978-3-540-64781-2. S2CID   14147978.
  21. Brassard, G.; Hoyer, P.; Mosca, M.; Tapp, A. (2002). "Quantum Amplitude Amplification and Estimation". In Samuel J. Lomonaco, Jr. (ed.). Quantum Computation and Quantum Information. AMS Contemporary Mathematics. 305. pp. 53–74. arXiv: quant-ph/0005055 . Bibcode:2000quant.ph..5055B. doi:10.1090/conm/305/05215. ISBN   9780821821404. S2CID   54753.
  22. Childs, A. M.; Cleve, R.; Deotto, E.; Farhi, E.; Gutmann, S.; Spielman, D. A. (2003). "Exponential algorithmic speedup by quantum walk". Proceedings of the 35th Symposium on Theory of Computing. Association for Computing Machinery. pp. 59–68. arXiv: quant-ph/0209131 . doi:10.1145/780542.780552. ISBN   1-58113-674-9.
  23. Childs, A. M.; Schulman, L. J.; Vazirani, U. V. (2007). "Quantum Algorithms for Hidden Nonlinear Structures". Proceedings of the 48th Annual IEEE Symposium on Foundations of Computer Science. IEEE. pp. 395–404. arXiv: 0705.2784 . doi:10.1109/FOCS.2007.18. ISBN   978-0-7695-3010-9.
  24. 1 2 Magniez, F.; Nayak, A.; Roland, J.; Santha, M. (2007). "Search via quantum walk". Proceedings of the 39th Annual ACM Symposium on Theory of Computing. Association for Computing Machinery. pp. 575–584. arXiv: quant-ph/0608026 . doi:10.1145/1250790.1250874. ISBN   978-1-59593-631-8.
  25. Ambainis, A. (2007). "Quantum Walk Algorithm for Element Distinctness". SIAM Journal on Computing . 37 (1): 210–239. arXiv: quant-ph/0311001 . doi:10.1137/S0097539705447311. S2CID   6581885.
  26. Shi, Y. (2002). Quantum lower bounds for the collision and the element distinctness problems. Proceedings of the 43rd Symposium on Foundations of Computer Science. pp. 513–519. arXiv: quant-ph/0112086 . doi:10.1109/SFCS.2002.1181975.
  27. Ambainis, A. (2005). "Polynomial Degree and Lower Bounds in Quantum Complexity: Collision and Element Distinctness with Small Range". Theory of Computing . 1 (1): 37–46. doi: 10.4086/toc.2005.v001a003 .
  28. Kutin, S. (2005). "Quantum Lower Bound for the Collision Problem with Small Range". Theory of Computing . 1 (1): 29–36. doi: 10.4086/toc.2005.v001a002 .
  29. Aleksandrs Belovs (2011). "Span Programs for Functions with Constant-Sized 1-certificates". arXiv: 1105.4024 [quant-ph].
  30. Magniez, F.; Santha, M.; Szegedy, M. (2007). "Quantum Algorithms for the Triangle Problem". SIAM Journal on Computing . 37 (2): 413–424. arXiv: quant-ph/0310134 . doi:10.1137/050643684. S2CID   594494.
  31. Aaronson, S. (3 February 2007). "NAND now for something completely different". Shtetl-Optimized. Retrieved 17 December 2009.
  32. Saks, M.E.; Wigderson, A. (1986). "Probabilistic Boolean Decision Trees and the Complexity of Evaluating Game Trees" (PDF). Proceedings of the 27th Annual Symposium on Foundations of Computer Science. IEEE. pp. 29–38. doi:10.1109/SFCS.1986.44. ISBN   0-8186-0740-8.
  33. Ambainis, A. (2007). "A nearly optimal discrete query quantum algorithm for evaluating NAND formulas". arXiv: 0704.3628 [quant-ph].
  34. Reichardt, B. W.; Spalek, R. (2008). "Span-program-based quantum algorithm for evaluating formulas". Proceedings of the 40th Annual ACM symposium on Theory of Computing. Association for Computing Machinery. pp. 103–112. arXiv: 0710.2630 . doi:10.1145/1374376.1374394. ISBN   978-1-60558-047-0.
  35. Pak, Igor (2012). "Testing commutativity of a group and the power of randomization". LMS Journal of Computation and Mathematics . 15: 38–43. doi: 10.1112/S1461157012000046 .
  36. Magniez, F.; Nayak, A. (2007). "Quantum Complexity of Testing Group Commutativity". Algorithmica . 48 (3): 221–232. arXiv: quant-ph/0506265 . doi:10.1007/s00453-007-0057-8. S2CID   3163328.
  37. Michael Nielsen and Isaac Chuang (2000). Quantum Computation and Quantum Information. Cambridge: Cambridge University Press. ISBN   0-521-63503-9.
  38. Aharonov, D.; Jones, V.; Landau, Z. (2006). "A polynomial quantum algorithm for approximating the Jones polynomial". Proceedings of the 38th Annual ACM symposium on Theory of Computing. Association for Computing Machinery. pp. 427–436. arXiv: quant-ph/0511096 . doi:10.1145/1132516.1132579.
  39. Feynman, R. P. (1982). "Simulating physics with computers". International Journal of Theoretical Physics . 21 (6–7): 467–488. Bibcode:1982IJTP...21..467F. CiteSeerX . doi:10.1007/BF02650179. S2CID   124545445.
  40. Abrams, D. S.; Lloyd, S. (1997). "Simulation of many-body Fermi systems on a universal quantum computer". Physical Review Letters . 79 (13): 2586–2589. arXiv: quant-ph/9703054 . Bibcode:1997PhRvL..79.2586A. doi:10.1103/PhysRevLett.79.2586. S2CID   18231521.
  41. Kassal, I.; Jordan, S. P.; Love, P. J.; Mohseni, M.; Aspuru-Guzik, A. (2008). "Polynomial-time quantum algorithm for the simulation of chemical dynamics". Proceedings of the National Academy of Sciences of the United States of America . 105 (48): 18681–86. arXiv: 0801.2986 . Bibcode:2008PNAS..10518681K. doi: 10.1073/pnas.0808245105 . PMC   2596249 . PMID   19033207.
  42. Freedman, M.; Kitaev, A.; Wang, Z. (2002). "Simulation of Topological Field Theories by Quantum Computers". Communications in Mathematical Physics . 227 (3): 587–603. arXiv: quant-ph/0001071 . Bibcode:2002CMaPh.227..587F. doi:10.1007/s002200200635. S2CID   449219.
  43. Aharonov, D.; Jones, V.; Landau, Z. (2009). "A polynomial quantum algorithm for approximating the Jones polynomial". Algorithmica . 55 (3): 395–421. arXiv: quant-ph/0511096 . doi:10.1007/s00453-008-9168-0. S2CID   7058660.
  44. Wocjan, P.; Yard, J. (2008). "The Jones polynomial: quantum algorithms and applications in quantum complexity theory". Quantum Information and Computation . 8 (1): 147–180. arXiv: quant-ph/0603069 . Bibcode:2006quant.ph..3069W. doi:10.26421/QIC8.1-2-10. S2CID   14494227.
  45. Alagic, G.; Jordan, S.P.; König, R.; Reichardt, B. W. (2010). "Approximating Turaev-Viro 3-manifold invariants is universal for quantum computation". Physical Review A . 82 (4): 040302. arXiv: 1003.0923 . Bibcode:2010PhRvA..82d0302A. doi:10.1103/PhysRevA.82.040302. S2CID   28281402.
  46. Harrow, Aram W; Hassidim, Avinatan; Lloyd, Seth (2008). "Quantum algorithm for solving linear systems of equations". Physical Review Letters. 103 (15): 150502. arXiv: 0811.3171 . Bibcode:2009PhRvL.103o0502H. doi:10.1103/PhysRevLett.103.150502. PMID   19905613. S2CID   5187993.
  47. Moll, Nikolaj; Barkoutsos, Panagiotis; Bishop, Lev S.; Chow, Jerry M.; Cross, Andrew; Egger, Daniel J.; Filipp, Stefan; Fuhrer, Andreas; Gambetta, Jay M.; Ganzhorn, Marc; Kandala, Abhinav; Mezzacapo, Antonio; Müller, Peter; Riess, Walter; Salis, Gian; Smolin, John; Tavernelli, Ivano; Temme, Kristan (2018). "Quantum optimization using variational algorithms on near-term quantum devices". Quantum Science and Technology. 3 (3): 030503. arXiv: 1710.01022 . doi:10.1088/2058-9565/aab822. S2CID   56376912.
  48. Farhi, Edward; Goldstone, Jeffrey; Gutmann, Sam (14 November 2014). "A Quantum Approximate Optimization Algorithm". arXiv: 1411.4028 [quant-ph].
  49. Peruzzo, Alberto; McClean, Jarrod; Shadbolt, Peter; Yung, Man-Hong; Zhou, Xiao-Qi; Love, Peter J.; Aspuru-Guzik, Alán; O’Brien, Jeremy L. (23 July 2014). "A variational eigenvalue solver on a photonic quantum processor". Nature Communications. 5 (1): 4213. arXiv: 1304.3061 . Bibcode:2014NatCo...5E4213P. doi:10.1038/ncomms5213. ISSN   2041-1723. PMC   4124861 . PMID   25055053.
  50. Higgott, Oscar; Wang, Daochen; Brierley, Stephen (2019). "Variational Quantum Computation of Excited States". Quantum. 3: 156. arXiv: 1805.08138 . doi:10.22331/q-2019-07-01-156. S2CID   119185497.
  51. Smart, Scott; Mazziotti, David (18 February 2021). "Quantum Solver of Contracted Eigenvalue Equations for Scalable Molecular Simulations on Quantum Computing Devices". Phys. Rev. Lett. 125 (7): 070504. arXiv: 2004.11416 . doi:10.1103/PhysRevLett.126.070504. PMID   33666467. S2CID   216144443.
  52. Mazziotti, David (6 October 2006). "Anti-Hermitian Contracted Schrödinger Equation: Direct Determination of the Two-Electron Reduced Density Matrices of Many-Electron Molecules". Phys. Rev. Lett. 97 (14): 143002. doi:10.1103/PhysRevLett.97.143002. PMID   17155245.