Appendix A: Quantum Algorithm Zoo - math.nist.gov
Source: https://search.usa.gov/search?affiliate=usagov&page=2&query=quantum+computing
This is a comprehensive catalog of quantum algorithms. If you notice any errors or omissions, please email me at 
. Your help is appreciated and will be acknowledged.
Algorithm: Factoring
Speedup: Superpolynomial
Description: Given an n-bit integer, find the prime factorization. The quantum algorithm of Peter Shor solves this in O˜(n3) time [82,125]. The fastest known classical algorithm for integer factorization is the general number field sieve, which is believed to run in time 2O˜(n1/3). The best rigorously proven upper bound on the classical complexity of factoring is O(2n/4+o(1)) via the Pollard-Strassen algorithm [252, 362]. Shor's factoring algorithm breaks RSA public-key encryption and the closely related quantum algorithms for discrete logarithms break the DSA and ECDSA digital signature schemes and the Diffie-Hellman key-exchange protocol. A quantum algorithm even faster than Shor's for the special case of factoring “semiprimes”, which are widely used in cryptography, is given in [271]. If small factors exist, Shor's algorithm can be beaten by a quantum algorithm using Grover search to speed up the elliptic curve factorization method [366]. Additional optimized versions of Shor's algorithm are given in [384, 386]. There are proposed classical public-key cryptosystems not believed to be broken by quantum algorithms, cf. [248]. At the core of Shor's factoring algorithm is order finding, which can be reduced to the Abelian hidden subgroup problem, which is solved using the quantum Fourier transform. A number of other problems are known to reduce to integer factorization including the membership problem for matrix groups over fields of odd order [253], and certain diophantine problems relevant to the synthesis of quantum circuits [254].
Algorithm: Discrete-log
Speedup: Superpolynomial
Description: We are given three n-bit numbers a, b, and N, with the promise that b=asmodN for some s. The task is to find s. As shown by Shor [82], this can be achieved on a quantum computer in poly(n) time. The fastest known classical algorithm requires time superpolynomial in n. By similar techniques to those in [82], quantum computers can solve the discrete logarithm problem on elliptic curves, thereby breaking elliptic curve cryptography [109, 14]. A further optimization to Shor's algorithm is given in [385]. The superpolynomial quantum speedup has also been extended to the discrete logarithm problem on semigroups [203, 204]. See also Abelian Hidden Subgroup.
Algorithm: Pell's Equation
Speedup: Superpolynomial
Description: Given a positive nonsquare integer d, Pell's equation is x2−dy2=1. For any such d there are infinitely many pairs of integers (x,y) solving this equation. Let (x1,y1) be the pair that minimizes x+yd−−√. If d is an n-bit integer (i.e. 0≤d<2n ), (x1,y1) may in general require exponentially many bits to write down. Thus it is in general impossible to find (x1,y1) in polynomial time. Let R=log(x1+y1d−−√). ⌊R⌉ uniquely identifies (x1,y1). As shown by Hallgren [49], given a n-bit number d, a quantum computer can find ⌊R⌉ in poly(n) time. No polynomial time classical algorithm for this problem is known. Factoring reduces to this problem. This algorithm breaks the Buchman-Williams cryptosystem. See also Abelian hidden subgroup.
Algorithm: Principal Ideal
Speedup: Superpolynomial
Description: We are given an n-bit integer d and an invertible ideal I of the ring Z[d−−√]. I is a principal ideal if there exists α∈Q(d−−√) such that I=αZ[d−−√]. α may be exponentially large in d. Therefore α cannot in general even be written down in polynomial time. However, ⌊logα⌉ uniquely identifies α. The task is to determine whether I is principal and if so find ⌊logα⌉. As shown by Hallgren, this can be done in polynomial time on a quantum computer [49]. A modified quantum algorithm for this problem using fewer qubits was given in [131]. A quantum algorithm solving the principal ideal problem in number fields of arbitrary degree (i.e. scaling polynomially in the degree) was subsequently given in [329]. Factoring reduces to solving Pell's equation, which reduces to the principal ideal problem. Thus the principal ideal problem is at least as hard as factoring and therefore is probably not in P. See also Abelian hidden subgroup.
Algorithm: Unit Group
Speedup: Superpolynomial
Description: The number field Q(θ) is said to be of degree d if the lowest degree polynomial of which θ is a root has degree d. The set O of elements of Q(θ) which are roots of monic polynomials in Z[x] forms a ring, called the ring of integers of Q(θ). The set of units (invertible elements) of the ring O form a group denoted O∗. As shown by Hallgren [50], and independently by Schmidt and Vollmer [116], for any Q(θ) of fixed degree, a quantum computer can find in polynomial time a set of generators for O∗ given a description of θ. No polynomial time classical algorithm for this problem is known. Hallgren and collaborators subsequently discovered how to achieve polynomial scaling in the degree [213]. See also [329]. The algorithms rely on solving Abelian hidden subgroup problems over the additive group of real numbers.
Algorithm: Class Group
Speedup: Superpolynomial
Description: The number field Q(θ) is said to be of degree d if the lowest degree polynomial of which θ is a root has degree d. The set O of elements of Q(θ) which are roots of monic polynomials in Z[x] forms a ring, called the ring of integers of Q(θ). For a ring, the ideals modulo the prime ideals form a group called the class group. As shown by Hallgren [50], a quantum computer can find in a set of generators for the class group of the ring of integers of any constant degree number field, given a description of θ in time poly(log(|O|)). An improved quantum algorithm, whose runtime is also polynomial in d was subsequently given in [329]. No polynomial time classical algorithm for these problems are known. See also Abelian hidden subgroup.
Algorithm: Gauss Sums
Speedup: Superpolynomial
Description: Let Fq be a finite field. The elements other than zero of Fq form a group F×q under multiplication, and the elements of Fq form an (Abelian but not necessarily cyclic) group F+q under addition. We can choose some character χ× of F×q and some character χ+ of F+q. The corresponding Gauss sum is the inner product of these characters: ∑x≠0∈Fqχ+(x)χ×(x) As shown by van Dam and Seroussi [90], Gauss sums can be estimated to polynomial precision on a quantum computer in polynomial time. Although a finite ring does not form a group under multiplication, its set of units does. Choosing a representation for the additive group of the ring, and choosing a representation for the multiplicative group of its units, one can obtain a Gauss sum over the units of a finite ring. These can also be estimated to polynomial precision on a quantum computer in polynomial time [90]. No polynomial time classical algorithm for estimating Gauss sums is known. Discrete log reduces to Gauss sum estimation [90]. Certain partition functions of the Potts model can be computed by a polynomial-time quantum algorithm related to Gauss sum estimation [47].
Algorithm:Solving Exponential Congruences
Speedup:Polynomial
Description: We are given a,b,c,f,g∈Fq. We must find integers x,y such that afx+bgy=c. As shown in [111], quantum computers can solve this problem in O˜(q3/8) time whereas the best classical algorithm requires O˜(q9/8) time. The quantum algorithm of [111] is based on the quantum algorithms for discrete logarithms and searching.
Algorithm: Matrix Elements of Group Representations
Speedup: Superpolynomial
Description: All representations of finite groups and compact linear groups can be expressed as unitary matrices given an appropriate choice of basis. Conjugating the regular representation of a group by the quantum Fourier transform circuit over that group yields a direct sum of the group's irreducible representations. Thus, the efficient quantum Fourier transform over the symmetric group [196], together with the Hadamard test, yields a fast quantum algorithm for additively approximating individual matrix elements of the arbitrary irreducible representations of Sn. Similarly, using the quantum Schur transform [197], one can efficiently approximate matrix elements of the irreducible representations of SU(n) that have polynomial weight. Direct implementations of individual irreducible representations for the groups U(n), SU(n), SO(n), and An by efficient quantum circuits are given in [106]. Instances that appear to be exponentially hard for known classical algorithms are also identified in [106].
Algorithm: Verifying Matrix Products
Speedup: Polynomial
Description: Given three n×n matrices, A,B, and C, the matrix product verification problem is to decide whether AB=C. Classically, the best known algorithm achieves this in time O(n2), whereas the best known classical algorithm for matrix multiplication runs in time O(n2.373). Ambainis et al. discovered a quantum algorithm for this problem with runtime O(n7/4) [6]. Subsequently, Buhrman and Špalek improved upon this, obtaining a quantum algorithm for this problem with runtime O(n5/3) [19]. This latter algorithm is based on results regarding quantum walks that were proven in [85].
Algorithm: Subset-sum
Speedup: Polynomial
Description: Given a list of integers x1,…,xn, and a target integer s, the subset-sum problem is to determine whether the sum of any subset of the given integers adds up to s. This problem is NP-complete, and therefore is unlikely to be solvable by classical or quantum algorithms with polynomial worst-case complexity. In the hard instances the given integers are of order 2n. In [178], a quantum algorithm is given that solves this problem in time 20.241n, up to polynomial factors. This quantum algorithm works by applying a variant of Ambainis's quantum walk algorithm for element-distinctness [7]to speed up a sophisticated classical algorithm for this problem due to Howgrave-Graham and Joux. The fastest known classical algorithm for subset-sum runs in time 20.291n, up to polynomial factors.
Algorithm: Decoding
Speedup: Varies
Description: Classical error correcting codes allow the detection and correction of bit-flips by storing data reduntantly. Maximum-likelihood decoding for arbitrary linear codes is NP-complete in the worst case, but for structured codes or bounded error efficient decoding algorithms are known. Quantum algorithms have been formulated to speed up the decoding of convolutional codes [238] and simplex codes [239].
Algorithm: Constraint Satisfaction
Speedup: Polynomial
Description: Constraint satisfaction problems, many of which are NP-hard, are ubiquitous in computer science, a canonical example being 3-SAT. If one wishes to satisfy as many constraints as possible rather than all of them, these become combinatorial optimization problems. (See also entry on adiabatic algorithms.) The brute force solution to constraint satisfaction problems can be quadratically sped up using Grover's algorithm. However, most constaint satisfaction problems are solvable by classical algorithms that (although still exponential-time) run more than quadratically faster than brute force checking of all possible solutions. Nevertheless, a polynomial quantum speedup over the fastest known classical algorithm for 3-SAT is given in [133], and polynomial quantum speedups for some other constraint satisfaction problems are given in [134, 298]. A commonly used classical algorithm for constraint satisfaction is backtracking, and for some problems this algorithm is the fastest known. A general quantum speedup for backtracking algorithms is given in [264].
Algorithm: Quantum Cryptanalysis
Speedup: Various
Description: It is well-known that Shor's algorithms for factoring and discrete logarithms [82,125] completely break the RSA and Diffie-Hellman cryptosystems, as well as their elliptic-curve-based variants [109, 14]. (A number of "post-quantum" public-key cryptosystems have been proposed to replace these primitives, which are not known to be broken by quantum attacks.) Beyond Shor's algorithm, there is a growing body of work on quantum algorithms specifically designed to attack cryptosystems. These generally fall into three categories. The first is quantum algorithms providing polynomial or sub-exponential time attacks on cryptosystems under standard assumptions. In particular, the algorithm of Childs, Jao, and Soukharev for finding isogenies of elliptic curves breaks certain elliptic curve based cryptosystems in subexponential time that were not already broken by Shor's algorithm [283]. The second category is quantum algorithms achieving polynomial improvement over known classical cryptanalytic attacks by speeding up parts of these classical algorithms using Grover search, quantum collision finding, etc. Such attacks on private-key [284, 285, 288, 315, 316] and public-key [262, 287] primitives, do not preclude the use of the associated cryptosystems but may influence choice of key size. The third category is attacks that make use of quantum superposition queries to block ciphers. These attacks in many cases completely break the cryptographic primitives [286, 289, 290, 291, 292]. However, in most practical situations such superposition queries are unlikely to be feasible.
Algorithm: Searching
Speedup: Polynomial
Description: We are given an oracle with N allowed inputs. For one input w ("the winner") the corresponding output is 1, and for all other inputs the corresponding output is 0. The task is to find w. On a classical computer this requires Ω(N) queries. The quantum algorithm of Lov Grover achieves this using O(N−−√) queries [48], which is optimal [216]. This has algorithm has subsequently been generalized to search in the presence of multiple "winners" [