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.
Algebraic and Number Theoretic Algorithms
Algorithm: FactoringSpeedup: Superpolynomial
Description: Given an nbit integer, find the prime factorization. The quantum algorithm of Peter Shor solves this in poly(n) time [82,125]. The fastest known classical algorithm requires time superpolynomial in n. Shor's algorithm breaks the RSA cryptosystem. At the core of this algorithm is order finding, which can be reduced to the Abelian hidden subgroup problem.
Algorithm: Discretelog
Speedup: Superpolynomial
Description: We are given three nbit numbers a, b, and N, with the promise that \( b = a^s \mod N \) 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]. 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 \( x^2  d y^2 = 1 \). For any such d there are infinitely many pairs of integers (x,y) solving this equation. Let \( (x_1,y_1) \) be the pair that minimizes \( x+y\sqrt{d} \). If d is an nbit integer (i.e. \( 0 \leq d \lt 2^n \) ), \( (x_1,y_1) \) may in general require exponentially many bits to write down. Thus it is in general impossible to find \( (x_1,y_1) \) in polynomial time. Let \( R = \log(x_1+y_1 \sqrt{d}) \). \( \lfloor R \rceil \) uniquely identifies \( (x_1,y_1) \). As shown by Hallgren [49], given a nbit number d, a quantum computer can find \( \lfloor R \rceil \) in poly(n) time. No polynomial time classical algorithm for this problem is known. Factoring reduces to this problem. This algorithm breaks the BuchmanWilliams cryptosystem. See also Abelian hidden subgroup.
Algorithm: Principal Ideal
Speedup: Superpolynomial
Description: We are given an nbit integer d and an invertible ideal I of the ring \( \mathbb{Z}[\sqrt{d}] \). I is a principal ideal if there exists \( \alpha \in \mathbb{Q}(\sqrt{d}) \) such that \( I = \alpha \mathbb{Z}[\sqrt{d}] \). \( \alpha \) may be exponentially large in d. Therefore \( \alpha \) cannot in general even be written down in polynomial time. However, \( \lfloor \log \alpha \rceil \) uniquely identifies \( \alpha \). The task is to determine whether I is principal and if so find \( \lfloor \log \alpha \rceil \) 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]. 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 \( \mathbb{Q}(\theta) \) is said to be of degree d if the lowest degree polynomial of which \( \theta \) is a root has degree d. The set \( \mathcal{O} \) of elements of \( \mathbb{Q}(\theta) \) which are roots of monic polynomials in \( \mathbb{Z}[x] \) forms a ring, called the ring of integers of \( \mathbb{Q}(\theta) \). The set of units (invertible elements) of the ring \( \mathcal{O} \) form a group denoted \( \mathcal{O}^* \). As shown by Hallgren [50], and independently by Schmidt and Vollmer [116], for any \( \mathbb{Q}(\theta) \) of fixed degree, a quantum computer can find in polynomial time a set of generators for \( \mathcal{O}^* \) given a description of \( \theta \). No polynomial time classical algorithm for this problem is known. Hallgren and collaborators subsequently discovered how to achieve polynomial scaling in the degree [213]. The algorithm relies on solving Abelian hidden subgroup problems over the additive group of real numbers.
Algorithm: Class Group
Speedup: Superpolynomial
Description: The number field The number field \( \mathbb{Q}(\theta) \) is said to be of degree d if the lowest degree polynomial of which \( \theta \) is a root has degree d. The set \( \mathcal{O} \) of elements of \( \mathbb{Q}(\theta) \) which are roots of monic polynomials in \( \mathbb{Z}[x] \) forms a ring, called the ring of integers of \( \mathbb{Q}(\theta) \). 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 polynomial time a set of generators for the class group of the ring of integers of any constant degree number field, given a description of \( \theta \). No polynomial time classical algorithm for this problem is known. See also Abelian hidden subgroup.
Algorithm: Gauss Sums
Speedup: Superpolynomial
Description: Let \( \mathbb{F}_q \) be a finite field. The elements other than zero of \( \mathbb{F}_q \) form a group \( \mathbb{F}_q^\times \) under multiplication, and the elements of \( \mathbb{F}_q \) form an (Abelian but not necessarily cyclic) group \( \mathbb{F}_q^+ \) under addition. We can choose some character \( \chi^\times \) of \( \mathbb{F}_q^\times \) and some character \( \chi^+ \) of \( \mathbb{F}_q^+ \). The corresponding Gauss sum is the inner product of these characters: \( \sum_{x \neq 0 \in \mathbb{F}_q} \chi^+(x) \chi^\times(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 polynomialtime quantum algorithm related to Gauss sum estimation [47].
Algorithm:Solving Exponential Congruences
Speedup:Polynomial
Description: We are given \( a,b,c,f,g \in \mathbb{F}_q \). We must find \( x,y \in \mathbb{F}_q \) such that \( a f^x + b g^y = c \). As shown in [111], quantum computers can solve this problem in \( \widetilde{O}(q^{3/8}) \) time whereas the best classical algorithm requires \( \widetilde{O}(q^{9/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 \( S_n \). 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 \( A_n \) 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 \times 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(n^2) \), whereas the best known classical algorithm for matrix multiplication runs in time \( O(n^{2.373}) \). Ambainis et al. discovered a quantum algorithm for this problem with runtime \( O(n^{7/4}) \) [6]. Subsequently, Buhrman and Špalek improved upon this, obtaining a quantum algorithm for this problem with runtime \( O(n^{5/3}) \) [19]. This latter algorithm is based on results regarding quantum walks that were proven in [85].
Algorithm: Subsetsum
Speedup: Polynomial
Description: Given a list of integers \( x_1,\ldots,x_n \), and a target integer s, the subsetsum problem is to determine whether the sum of any subset of the given integers adds up to s. This problem is NPcomplete, and therefore is unlikely to be solvable by classical or quantum algorithms with polynomial worstcase complexity. In the hard instances the given integers are of order \( 2^n \). In [178], a quantum algorithm is given that solves this problem in time \( 2^{0.241n} \), up to polynomial factors. This quantum algorithm works by applying a variant of Ambainis's quantum walk algorithm for elementdistinctness [7]to speed up a sophisticated classical algorithm for this problem due to HowgraveGraham and Joux. The fastest known classical algorithm for subsetsum runs in time \( 2^{0.291n} \), up to polynomial factors.
Oracular Algorithms
Algorithm: SearchingSpeedup: 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 \( \Omega(N) \) queries. The quantum algorithm of Lov Grover achieves this using \( O(\sqrt{N}) \) queries [48].This has algorithm has subsequently been generalized to search in the presence of multiple "winners" [15], evaluate the sum of an arbitrary function [15,16,73], find the global minimum of an arbitrary function [35,75], take advantage of alternative initial states [100] or nonuniform probabilistic priors [123], work with oracles whose runtime varies between inputs [138], approximate definite integrals [77], and converge to a fixedpoint [208, 209]. The generalization of Grover's algorithm known as amplitude estimation [17] is now an important primitive in quantum algorithms. Amplitude estimation forms the core of most known quantum algorithms related to collision finding and graph properties. One of the natural applications for Grover search is speeding up the solution to NPcomplete problems such as 3SAT. Doing so is nontrivial, because the best classical algorithm for 3SAT is not quite a brute force search. Nevertheless, amplitude amplification enables a quadratic quantum speedup over the best classical 3SAT algorithm, as shown in [133]. Quadratic speedups for other constraint satisfaction problems are obtained in [134].
Algorithm: Abelian Hidden Subgroup
Speedup: Superpolynomial
Description: Let G be a finitely generated Abelian group, and let H be some subgroup of G such that G/H is finite. Let f be a function on G such that for any \( g_1,g_2 \in G \), \( f(g_1) = f(g_2) \) if and only if \( g_1 \) and \( g_2 \) are in the same coset of H. The task is to find H (i.e. find a set of generators for H) by making queries to f. This is solvable on a quantum computer using \( O(\log \vert G\vert) \) queries, whereas classically \( \Omega(G) \) are required. This algorithm was first formulated in full generality by Boneh and Lipton in [14]. However, proper attribution of this algorithm is difficult because, as described in chapter 5 of [76], it subsumes many historically important quantum algorithms as special cases, including Simon's algorithm [108], which was the inspiration for Shor's period finding algorithm, which forms the core of his factoring and discretelog algorithms. The Abelian hidden subgroup algorithm is also at the core of the Pell's equation, principal ideal, unit group, and class group algorithms. In certain instances, the Abelian hidden subgroup problem can be solved using a single query rather than order \( \log(\vert G\vert) \), as shown in [30].
Algorithm: NonAbelian Hidden Subgroup
Speedup: Superpolynomial
Description: Let G be a finitely generated group, and let H be some subgroup of G that has finitely many left cosets. Let f be a function on G such that for any \( g_1, g_2 \), \( f(g_1) = f(g_2) \) if and only if \( g_1 \) and \( g_2 \) are in the same left coset of H. The task is to find H (i.e. find a set of generators for H) by making queries to f. This is solvable on a quantum computer using \( O(\log(G) \) queries, whereas classically \( \Omega(G) \) are required [37,51]. However, this does not qualify as an efficient quantum algorithm because in general, it may take exponential time to process the quantum states obtained from these queries. Efficient quantum algorithms for the hidden subgroup problem are known for certain specific nonAbelian groups [81,55,72,53,9,22,56,71,57,43,44,28,126,207]. A slightly outdated survey is given in [69]. Of particular interest are the symmetric group and the dihedral group. A solution for the symmetric group would solve graph isomorphism. A solution for the dihedral group would solve certain lattice problems [78]. Despite much effort, no polynomialtime solution for these groups is known. However, Kuperburg [66] found a time \( 2^{O( \sqrt{\log N})}) \) algorithm for finding a hidden subgroup of the dihedral group \( D_N \). Regev subsequently improved this algorithm so that it uses not only subexponential time but also polynomial space [79].
Algorithm: BernsteinVazirani
Speedup: Polynomial
Description: We are given an oracle whose input is n bits and whose output is one bit. Given input \( x \in \{0,1\}^n \), the output is \( x \odot h \), where h is the "hidden" string of n bits, and \( \odot \) denotes the bitwise inner product modulo 2. The task is to find h. On a classical computer this requires n queries. As shown by Bernstein and Vazirani [11], this can be achieved on a quantum computer using a single query. Furthermore, one can construct a recursive version of this problem, called recursive Fourier sampling, such that quantum computers require exponentially fewer queries than classical computers [11].
Algorithm: DeutschJozsa
Speedup: Exponential over P, none over BPP
Description: We are given an oracle whose input is n bits and whose output is one bit. We are promised that out of the \( 2^n \) possible inputs, either all of them, none of them, or half of them yield output 1. The task is to distinguish the balanced case (half of all inputs yield output 1) from the constant case (all or none of the inputs yield output 1). It was shown by Deutsch [32] that for n=1, this can be solved on a quantum computer using one query, whereas any deterministic classical algorithm requires two. This was historically the first welldefined quantum algorithm achieving a speedup over classical computation. A singlequery quantum algorithm for arbitrary n was developed by Deutsch and Jozsa in [33]. Although probabilistically easy to solve with O(1) queries, the DeutschJozsa problem has exponential worst case deterministic query complexity classically.
Algorithm: Formula Evaluation
Speedup: Polynomial
Description: A Boolean expression is called a formula if each variable is used only once. A formula corresponds to a circuit with no fanout, which consequently has the topology of a tree. By Reichardt's spanprogram formalism, it is now known [158] that the quantum query complexity of any formula of O(1) fanin on N variables is \( \Theta(\sqrt{N}) \). This result culminates from a long line of work [27,8,80,159,160], which started with the discovery by Farhi et al. [38] that NAND trees on \( 2^n \) variables can be evaluated on quantum computers in time \( O(2^{0.5n}) \) using a continuoustime quantum walk, whereas classical computers require \( \Omega(2^{0.753n}) \) queries. In many cases, the quantum formulaevaluation algorithms are efficient not only in query complexity but also in timecomplexity. The spanprogram formalism also yields quantum query complexity lower bounds [149]. Although originally discovered from a different point of view, Grover's algorithm can be regarded as a special case of formula evaluation in which every gate is OR. The quantum complexity of evaluating nonboolean formulas has also been studied [29], but is not as fully understood. Childs et al. have generalized to the case in which input variables may be repeated (i.e. the first layer of the circuit may include fanout) [101]. They obtained a quantum algorithm using \( O(\min \{N,\sqrt{S},N^{1/2} G^{1/4} \}) \) queries, where N is the number of input variables not including multiplicities, S is the number of inputs counting multiplicities, and G is the number of gates in the formula. References [164] and [165] consider special cases of the NAND tree problem in which the number of NAND gates taking unequal inputs is limited. Some of these cases yield superpolynomial separation between quantum and classical query complexity.
Algorithm: Gradients, Structured Search, and Learning Polynomials
Speedup: Polynomial
Description: Suppose we are given a oracle for computing some smooth function \( f:\mathbb{R}^d \to \mathbb{R} \). The inputs and outputs to f are given to the oracle with finitely many bits of precision. The task is to estimate \( \nabla f \) at some specified point \( \mathbf{x}_0 \in \mathbb{R}^d \). As shown in [61], a quantum computer can achieve this using one query, whereas a classical computer needs at least d+1 queries. In [20], Bulger suggested potential applications for optimization problems. As shown in appendix D of [62], a quantum computer can use the gradient algorithm to find the minimum of a quadratic form in d dimensions using O(d) queries, whereas, as shown in [94], a classical computer needs at least \( \Omega(d^2) \) queries. Single query quantum algorithms for finding the minima of basins based on Hamming distance were earlier given in [147,148]. The quantum algorithm of [62] can also extract all \( d^2 \) matrix elements of the quadratic form using O(d) queries, and more generally, all \( d^n \) nth derivatives of a smooth function of d variables in \( O(d^{n1}) \) queries. As shown in [130,146], quadratic forms and multilinear polynomials in d variables over a finite field may be extracted with a factor of d fewer quantum queries than are required classically.
Algorithm: Hidden Shift
Speedup: Superpolynomial
Description: We are given oracle access to some function f on \( \mathbb{Z}_N \). We know that f(x) = g(x+s) where g is a known function and s is an unknown shift. The hidden shift problem is to find s. By reduction from Grover's problem it is clear that at least \( \sqrt{N} \) queries are necessary to solve hidden shift in general. However, certain special cases of the hidden shift problem are solvable on quantum computers using O(1) queries. In particular, van Dam et al. showed that this can be done if f is a multiplicative character of a finite ring or field [89]. The previously discovered shifted Legendre symbol algorithm [88,86] is subsumed as a special case of this, because the Legendre symbol \( \left(\frac{x}{p} \right) \) is a multiplicative character of \( \mathbb{F}_p \). No classical algorithm running in time O(polylog(N)) is known for these problems. Furthermore, the quantum algorithm for the shifted Legendre symbol problem would break a certain cryptographic pseudorandom generator given the ability to make quantum queries to the generator [89]. Roetteler has found exponential quantum speedups for finding hidden shifts of certain nonlinear Boolean functions [105,130]. Building on this work, Gavinsky, Roetteler, and Roland have shown [142] that the hidden shift problem on random boolean functions \( f:\mathbb{Z}_2^n \to \mathbb{Z}_2 \) has O(n) average case quantum complexity, whereas the classical query complexity is \( \Omega(2^{n/2}) \). The results in [143], though they are phrased in terms of the hidden subgroup problem for the dihedral group, imply that the quantum query complexity of the hidden shift problem for an injective function on \( \mathbb{Z}_N \) is O(log n), whereas the classical query complexity is \( \Theta(\sqrt{N}) \). However, the best known quantum circuit complexity for injective hidden shift on \( \mathbb{Z}_N \) is \( O(2^{C \sqrt{\log N}}) \), achieved by Kuperberg's sieve algorithm [66].
Algorithm: Linear Systems
Speedup: Superpolynomial
Description: We are given oracle access to an \( n \times n \) matrix A and some description of a vector b. We wish to find some property of f(A)b for some efficiently computable function f. Suppose A is a Hermitian matrix with O(polylog n) nonzero entries in each row and condition number k. As shown in [104], a quantum computer can in \( O(k^2 \log n) \) time compute to polynomial precision various expectation values of operators with respect to the vector f(A)b (provided that a quantum state proportional to b is efficiently constructable). For certain functions, such as f(x)=1/x, this procedure can be extended to nonHermitian and even nonsquare A. The runtime of this algorithm was subsequently improved to \( O(k \log^3 k \log n) \) in [138]. Extensions of this quantum algorithm have been applied to problems of solving linear differential equations [156], leastsquares curvefitting [169], and machine learning [214].
Algorithm: Ordered Search
Speedup: Constant
Description: We are given oracle access to a list of N numbers in order from least to greatest. Given a number x, the task is to find out where in the list it would fit. Classically, the best possible algorithm is binary search which takes \( \log_2 N \) queries. Farhi et al. showed that a quantum computer can achieve this using 0.53 \( \log_2 N \) queries [39]. Currently, the best known deterministic quantum algorithm for this problem uses 0.433 \( \log_2 N \) queries [103]. A lower bound of \( \frac{1}{\pi} \log_2 N \) quantum queries has been proven for this problem [24]. In [10], a randomized quantum algorithm is given whose expected query complexity is less than \( \frac{1}{3} \log_2 N \).
Algorithm: Graph Properties in the Adjacency Matrix Model
Speedup: Polynomial
Description: Let G be a graph of n vertices. We are given access to an oracle, which given a pair of integers in {1,2,...,n} tells us whether the corresponding vertices are connected by an edge. Building on previous work [35,52,36], Dürr et al. [34] show that the quantum query complexity of finding a minimum spanning tree of weighted graphs, and deciding connectivity for directed and undirected graphs have \( \Theta(n^{3/2}) \) quantum query complexity, and that finding lowest weight paths has \( O(n^{3/2}\log^2 n) \) quantum query complexity. Berzina et al. [13] show that deciding whether a graph is bipartite can be achieved using \( O(n^{3/2}) \) quantum queries. All of these problems are thought to have \( \Omega(n^2) \) classical query complexity. A graph property is sparse if there exists a constant c such that every graph with the property has a ratio of edges to vertices at most c. Childs and Kothari have shown that all sparse graph properties have query complexity \( \Theta(n^{2/3}) \) if they cannot be characterized by a list of forbidden subgraphs and \( o(n^{2/3}) \) (littleo) if they can [140]. The former algorithm is based on Grover search, the latter on the quantum walk formalism of [141]. By Mader's theorem, sparse graph properties include all nontrivial minorclosed properties. These include planarity, being a forest, and not containing a path of given length. Another interesting computational problem is finding a subgraph H in a given graph G. The simplest case of this finding the triangle, that is, the clique of size three. The fastest known quantum algorithm for this finds a triangle in \( O(n^{9/7}) \) quantum queries [175, 171], improving on [70, 152, 21]. Classically, triangle finding requires \( \Omega(n^2) \) queries [21]. More generally, a quantum computer can find an arbitrary subgraph of k vertices using \( O(n^{22/kt}) \) queries where \( t=(2kd3)/(k(d+1)(m+2)) \) and d and m are such that H has a vertex of degree d and m+d edges [153]. This improves on the previous algorithm of [70]. In some cases, this query complexity is beaten by the quantum algorithm of [140], which finds H using \( \widetilde{O}\left( n^{\frac{3}{2}\frac{1}{\mathrm{vc}(H)+1}} \right) \) queries, provided G is sparse, where vc(H) is the size of the minimal vertex cover of H.
Algorithm: Graph Properties in the Adjacency List Model
Speedup: Polynomial
Description: Let G be a graph of N vertices, M edges, and degree d. We are given access to an oracle which, when queried with the label of a vertex and \( j \in \{1,2,\ldots,d\} \) outputs the jth neighbor of the vertex or null if the vertex has degree less than d. Suppose we are given the promise that G is either bipartite or is far from bipartite in the sense that a constant fraction of the edges would need to be removed to achieve bipartiteness. Then, as shown in [144], the quantum complexity of deciding bipartiteness is \( \widetilde{O}(N^{1/3}) \). Also in [144], it is shown that distinguishing expander graphs from graphs that are far from being expanders has quantum complexity \( \widetilde{O}(N^{1/3}) \) and \( \widetilde{\Omega}(N^{1/4}) \), whereas the classical complexity is \( \widetilde{\Theta}(\sqrt{N}) \). The key quantum algorithmic tool is Ambainis' algorithm for element distinctness. In [34], it is shown that finding a minimal spanning tree has quantum query complexity \( \Theta(\sqrt{NM}) \), deciding graph connectivity has quantum query complexity \( \Theta(N) \) in the undirected case, and \( \widetilde{\Theta}(\sqrt{NM}) \) in the directed case, and computing the lowest weight path from a given source to all other vertices on a weighted graph has quantum query complexity \( \widetilde{\Theta}(\sqrt{NM}) \).
Algorithm: Welded Tree
Speedup: Superpolynomial
Description: Some computational problems can be phrased in terms of the query complexity of finding one's way through a maze. That is, there is some graph G to which one is given oracle access. When queried with the label of a given node, the oracle returns a list of the labels of all adjacent nodes. The task is, starting from some source node (i.e. its label), to find the label of a certain marked destination node. As shown by Childs et al. [26], quantum computers can exponentially outperform classical computers at this task for at least some graphs. Specifically, consider the graph obtained by joining together two depthn binary trees by a random "weld" such that all nodes but the two roots have degree three. Starting from one root, a quantum computer can find the other root using poly(n) queries, whereas this is provably impossible using classical queries.
Algorithm: Collision Finding and Element Distinctness
Speedup: Polynomial
Description: Suppose we are given oracle access to a two to one function f on a domain of size N. The collision problem is to find a pair \( x,y \in \{1,2,\ldots,N\} \) such that f(x) = f(y). The classical randomized query complexity of this problem is \( \Theta(\sqrt{N}) \), whereas, as shown by Brassard et al., a quantum computer can achieve this using \(O(N^{1/3}) \) queries [18]. Removing the promise that f is twotoone yields a problem called element distinctness, which has \( \Theta(N) \) classical query complexity. Improving upon [21], Ambainis gives a quantum algorithm with query complexity of \( O(N^{2/3}) \) for element distinctness, which is optimal [7]. The problem of deciding whether any kfold collisions exist is called kdistinctness. Improving upon [7,154], the best quantum algorithms for kdistinctness have query complexity \( O(n^{3/4  1/(4(2^k1))}) \) [172, 173]. For k=2,3 this is also the timecomplexity, up to logarithmic factors, by [7]. Given two functions f and g, each on a domain of size N, a claw is a pair x,y such that f(x) = g(y). The algorithm of [7] solves clawfinding in \( O(N^{2/3}) \) queries as a special case, improving on the previous \( O(N^{3/4} \log N) \) quantum algorithm of [21]. See also graph collision.
Algorithm: Graph Collision
Speedup: Polynomial
Description: We are given an undirected graph of n vertices and oracle access to a labelling of the vertices by 1 and 0. The graph collision problem is, by querying this oracle, to decide whether there exist a pair of vertices, connected by an edge, both of which are labelled 1. One can embed Grover's unstructured search problem as an instance of graph collision by choosing the star graph, labelling the center 1, and labelling the remaining vertices by the database entries. Hence, this problem has quantum query complexity \( \Omega(\sqrt{n}) \) and classical query complexity \( \Theta (n) \). In [70], Magniez, Nayak, and Szegedy gave a \( O(N^{2/3}) \)query quantum algorithm for graph collision on general graphs. This remains the best upper bound on quantum query complexity for this problem on general graphs. However, stronger upper bounds have been obtained for several special classes of graphs. Specifically, the quantum query complexity on a graph G is \( \widetilde{O}(\sqrt{n} + \sqrt{l}) \) where l is the number of nonedges in G [161], \(O(\sqrt{n} \alpha^{1/6}) \) where \(\alpha\) is the size of the largest independent set of G [172], \(O(\sqrt{n} + \sqrt{\alpha^*})\) where \( \alpha^* \) is the maximum total degree of any independent set of G [200], and \(O(\sqrt{n} t^{1/6}) \) where t is the treewidth of G [201]. Furthermore, the quantum query complexity is \( \widetilde{O}(\sqrt{n}) \) with high probability for random graphs in which the presence or absence of an edge between each pair of vertices is chosen independently with fixed probability, (i.e. ErdősRényi graphs) [200]. See [201] for a summary of these results as well as new upper bounds for two additional classes of graph that are too complicated to describe here.
Algorithm: Matrix Commutativity
Speedup: Polynomial
Description: We are given oracle access to k matrices, each of which are \( n \times n \). Given integers \( i,j \in \{1,2,\ldots,n\} \), and \( x \in \{1,2,\ldots,k\} \) the oracle returns the ij matrix element of the \( x^{\mathrm{th}} \) matrix. The task is to decide whether all of these k matrices commute. As shown by Itakura [54], this can be achieved on a quantum computer using \( O(k^{4/5}n^{9/5}) \) queries, whereas classically this requires \( \Omega( k n^2 ) \) queries.
Algorithm: Group Commutativity
Speedup: Polynomial
Description: We are given a list of k generators for a group G and access to a blackbox implementing group multiplication. By querying this blackbox we wish to determine whether the group is commutative. The best known classical algorithm is due to Pak and requires O(k) queries. Magniez and Nayak have shown that the quantum query complexity of this task is \( \widetilde{\Theta}(k^{2/3}) \) [139].
Algorithm: Hidden Nonlinear Structures
Speedup: Superpolynomial
Description: Any Abelian group G can be visualized as a lattice. A subgroup H of G is a sublattice, and the cosets of H are all the shifts of that sublattice. The Abelian hidden subgroup problem is normally solved by obtaining superposition over a random coset of the Hidden subgroup, and then taking the Fourier transform so as to sample from the dual lattice. Rather than generalizing to nonAbelian groups (see nonAbelian hidden subgroup), one can instead generalize to the problem of identifying hidden subsets other than lattices. As shown by Childs et al. [23] this problem is efficiently solvable on quantum computers for certain subsets defined by polynomials, such as spheres. Decker et al. showed how to efficiently solve some related problems in [31, 212].
Algorithm: Center of Radial Function
Speedup: Polynomial
Description: We are given an oracle that evaluates a function f from \( \mathbb{R}^d \) to some arbitrary set S, where f is spherically symmetric. We wish to locate the center of symmetry, up to some precision. (For simplicity, let the precision be fixed.) In [110], Liu gives a quantum algorithm, based on a curvelet transform, that solves this problem using a constant number of quantum queries independent of d. This constitutes a polynomial speedup over the classical lower bound, which is \( \Omega(d) \) queries. The algorithm works when the function f fluctuates on sufficiently small scales, e.g., when the level sets of f are sufficiently thin spherical shells. The quantum algorithm is shown to work in an idealized continuous model, and nonrigorous arguments suggest that discretization effects should be small.
Algorithm: Group Order and Membership
Speedup: Superpolynomial
Description: Suppose a finite group G is given oracularly in the following way. To every element in G, one assigns a corresponding label. Given an ordered pair of labels of group elements, the oracle returns the label of their product. There are several classically hard problems regarding such groups. One is to find the group's order, given the labels of a set of generators. Another task is, given a bitstring, to decide whether it corresponds to a group element. The constructive version of this membership problem requires, in the yes case, a decomposition of the given element as a product of group generators. Classically, these problems cannot be solved using polylog(G) queries even if G is Abelian. For Abelian groups, quantum computers can solve these problems using polylog(G) queries by reduction to the Abelian hidden subgroup problem, as shown by Mosca [74]. Furthermore, as shown by Watrous [91], quantum computers can solve these problems using polylog(G) queries for any solvable group. For groups given as matrices over a finite field rather than oracularly, the order finding and constructive membership problems can be solved in polynomial time by using the quantum algorithms for discrete log and factoring [124]. See also group isomorphism.
Algorithm: Group Isomorphism
Speedup: Superpolynomial
Description: Let G be a finite group. To every element of G is assigned an arbitrary label (bit string). Given an ordered pair of labels of group elements, the group oracle returns the label of their product. Given access to the group oracles for two groups G and G', and a list of generators for each group, we must decide whether G and G' are isomorphic. For Abelian groups, we can solve this problem using poly(log G, log G') queries to the oracle by applying the quantum algorithm of [127], which decomposes any Abelian group into a canonical direct product of cyclic groups. The quantum algorithm of [128] solves the group isomorphism problem using poly(log G, log G') queries for a certain class of nonAbelian groups. Specifically, a group G is in this class if G has a normal Abelian subgroup A and an element y of order coprime to A such that G = A, y. Zatloukal has recently given an exponential quantum speedup for some instances of a problem closely related to group isomorphism, namely testing equivalence of group extensions [202].
Algorithm: Statistical Difference
Speedup: Polynomial
Description: Suppose we are given two black boxes A and B whose domain is the integers 1 through T and whose range is the integers 1 through N. By choosing uniformly at random among allowed inputs we obtain a probability distribution over the possible outputs. We wish to approximate to constant precision the L1 distance between the probability distributions determined by A and B. Classically the number of necessary queries scales essentially linearly with N. As shown in [117], a quantum computer can achieve this using \( O(\sqrt{N}) \) queries. Approximate uniformity and orthogonality of probability distributions can also be decided on a quantum computer using \( O(N^{1/3}) \) queries. The main tool is the quantum counting algorithm of [16].
Algorithm: Finite Rings and Ideals
Speedup: Superpolynomial
Description: Suppose we are given black boxes implementing the addition and multiplication operations on a finite ring R, not necessarily commutative, along with a set of generators for R. With respect to addition, R forms a finite Abelian group (R,+). As shown in [119], on a quantum computer one can find in poly(log R) time a set of additive generators \( \{h_1,\ldots,h_m\} \subset R \) such that \( (R,+) \simeq \langle h_1 \rangle \times \ldots \times \langle h_M \rangle\) and m is polylogarithmic in R. This allows efficient computation of a multiplication tensor for R. As shown in [118], one can similarly find an additive generating set for any ideal in R. This allows one to find the intersection of two ideals, find their quotient, prove whether a given ring element belongs to a given ideal, prove whether a given element is a unit and if so find its inverse, find the additive and multiplicative identities, compute the order of an ideal, solve linear equations over rings, decide whether an ideal is maximal, find annihilators, and test the injectivity and surjectivity of ring homomorphisms. As shown in [120], one can also use a quantum computer to efficiently decide whether a given polynomial is identically zero on a given finite black box ring. Known classical algorithms for these problems scale as poly(R).
Algorithm: Counterfeit Coins
Speedup: Polynomial
Description: Suppose we are given N coins, k of which are counterfeit. The real coins are all of equal weight, and the counterfeit coins are all of some other equal weight. We have a pan balance and can compare the weight of any pair of subsets of the coins. Classically, we need \( \Omega(k \log(N/k)) \) weighings to identify all of the counterfeit coins. We can introduce an oracle such that given a pair of subsets of the coins of equal cardinality, it outputs one bit indicating balanced or unbalanced. Building on previous work by Terhal and Smolin [137], Iwama et al. have shown [136] that on a quantum computer, one can identify all of the counterfeit coins using \( O(k^{1/4}) \) queries. The core techniques behind the quantum speedup are amplitude amplification and the BernsteinVazirani algorithm.
Algorithm: Matrix Rank
Speedup: Polynomial
Description: Suppose we are given oracle access to the (integer) entries of an \( n \times m \) matrix A. We wish to determine the rank of the matrix. Classically this requires order nm queries. Building on [149], Belovs [150] gives a quantum algorithm that can use fewer queries given a promise that the rank of the matrix is at least r. Specifically, Belovs' algorithm uses \( O(\sqrt{r(nr+1)}LT) \) queries, where L is the rootmeansquare of the reciprocals of the r largest singular values of A and T is a factor that depends on the sparsity of the matrix. For general A, \( T = O(\sqrt{nm}) \). If A has at most k nonzero entries in any row or column then \( T = O(k \log(n+m)) \). (To achieve the corresponding query complexity in the ksparse case, the oracle must take a column index as input, and provide a list of the nonzero matrix elements from that column as output.) As an important special case, one can use these quantum algorithms for the problem of determining whether a square matrix is singular, which is sometimes referred to as the determinant problem. For general A the quantum query complexity of the determinant problem is no lower than the classical query complexity [151]. However, [151] does not rule out a quantum speedup given a promise on A, such as sparseness or lack of small singular values.
Algorithm: Matrix Multiplication over Semirings
Speedup: Polynomial
Description: A semiring is a set endowed with addition and multiplication operations that obey all the axioms of a ring except the existence additive inverses. Matrix multiplication over various semirings has many applications to graph problems. Matrix multiplication over semirings can be sped up by straightforward Grover improvements upon schoolbook multiplication, yielding a quantum algorithm that multiplies a pair of \(n \times n\) matrices in \( \widetilde{O}(n^{5/2}) \) time. For some semirings this algorithm outperforms the fastest known classical algorithms and for some semirings it does not [206]. A case of particular interest is the Boolean semiring, in which OR serves as addition and AND serves as multiplication. No quantum algorithm is known for Boolean semiring matrix multiplication in the general case that beats the best classical algorithm, which has complexity \( n^{2.373} \). However, for sparse input our output, quantum speedups are known. Specifically, let A,B be n by n Boolean matrices. Let C=AB, and let l be the number of entries of C that are equal to 1 (i.e. TRUE). Improving upon [19, 155, 157], the best known upper bound on quantum query complexity is \(\widetilde{O}(n \sqrt{l}) \), as shown in [161]. If instead the input matrices are sparse, a quantum speedup over the fastest known classical algorithm also has been found in a certain regime [206]. For detailed comparison to classical algorithms, see [155, 206]. Quantum algorithms have been found to perform matrix multiplication over the (max,min) semiring in \(\widetilde{O}(n^{2.473})\) time and over the distance dominance semiring in \(\widetilde{O}(n^{2.458})\) time [206]. The fastest known classical algorithm for both of these problems has \(\widetilde{O}(n^{2.687})\) complexity.
Algorithm: Subset finding
Speedup: Polynomial
Description: We are oracle access to a function \( f:D \to R \) where D and R are finite sets. Some property \( P \subset (D \times R)^k \) is specified, for example as an explicit list. Our task is to find a sizek subset of D satisfying P, i.e. \( ((x_1,f(x_1)),\ldots,(x_k,f(x_k))) \in P \), or reject if none exists. As usual, we wish to do this with the minimum number of queries to f. Generalizing the result of [7], it was shown in [162] that this can be achieved using \(O(D^{k/(k+1)}) \) quantum queries. As an noteworthy special case, this algorithm solves the ksubsetsum problem of finding k numbers from a list with some desired sum. A matching lower bound for the quantum query complexity is proven in [163].
Algorithm: Search with Wildcards
Speedup: Polynomial
Description: The search with wildcards problem is to identify a hidden nbit string x by making queries to an oracle f. Given \( S \subseteq \{1,2,\ldots,n\} \) and \( y \in \{0,1\}^{S} \), f returns one if the substring of x specified by S is equal to y, and returns zero otherwise. Classically, this problem has query complexity \(\Theta(n)\). As shown in [167], the quantum query complexity of this problem is \( \Theta(\sqrt{n}) \). Interestingly, this quadratic speedup is achieved not through amplitude amplification or quantum walks, but rather through use of the socalled Pretty Good Measurement. The paper [167] also gives a quantum speedup for the related problem of combinatorial group testing. In combinatorial group testing, we again wish to identify a hidden nbit string x by querying an oracle f. However, in this problem, f takes a subset \(S \subseteq \{1,2,\ldots,n\} \) and returns the OR of the corresponding bits of x. If exactly k of the bits in x are one, then the classical query complexity of combinatorial group testing is \( \Theta(k \log(n/k) )\). The quantum complexity is at most O(k) (independent of n) and at least \( \Omega( \sqrt{k}) \).
Algorithm: Network flows
Speedup: Polynomial
Description: A network is a directed graph whose edges are labeled with numbers indicating their carrying capacities, and two of whose vertices are designated as the source and the sink. A flow on a network is an assignment of flows to the edges such that no flow exceeds that edge's capacity, and for each vertex other than the source and sink, the total inflow is equal to the total outflow. The network flow problem is, given a network, to find the flow that maximizes the total flow going from source to sink. For a network with n vertices, m edges, and integer capacities of maximum magnitude U, [168] gives a quantum algorithm to find the maximal flow in time \( O(\min \{n^{7/6} \sqrt{m} \ U^{1/3}, \sqrt{nU}m\} \times \log n) \). The network flow problem is closely related to the problem of finding a maximal matching of a graph, that is, a maximalsize subset of edges that connects each vertex to at most one other vertex. The paper [168] gives algorithms for finding maximal matchings that run in time \( O(n \sqrt{m+n} \log n) \) if the graph is bipartite, and \( O(n^2 ( \sqrt{m/n} + \log n) \log n) \) in the general case. The core of these algorithms is Grover search. The known upper bounds on classical complexity of the network flow and matching problems are complicated to state because different classical algorithms are preferable in different parameter regimes. However, in certain regimes, the above quantum algorithms beat all known classical algorithms. (See [168] for details.)
Algorithm: Electrical Resistance
Speedup: Exponential
Description: We are given oracle access to a weighted graph of n vertices and maximum degree d whose edge weights are to be interpreted as electrical resistances. Our task is to compute the resistance between a chosen pair of vertices. Wang gave a quantum algorithm [210] for this task that runs in time \(\mathrm{poly}( \log n, d, 1/\phi, 1/\epsilon) \), where \( \phi \) is the expansion of the graph, and the answer is to be given to within a factor of \( 1+\epsilon \). Known classical algorithms for this problem are polynomial in n rather than \( \log n \). The algorithm is based on a novel use of quantum walks.
Approximation and Simulation Algorithms
Algorithm: Quantum SimulationSpeedup: Superpolynomial
Description: It is believed that for any physically realistic Hamiltonian H on n degrees of freedom, the corresponding time evolution operator \( e^{i H t} \) can be implemented using poly(n,t) gates. Unless BPP=BQP, this problem is not solvable in general on a classical computer in polynomial time. Many techniques for quantum simulation have been developed for different applications [25,95,92,5,1,12,63,68,99,107,145,166, 170, 205, 211]. The exponential complexity of classically simulating quantum systems led Feynman to first propose that quantum computers might outperform classical computers on certain tasks [40]. Although the problem of finding ground energies of local Hamiltonians is QMAcomplete and therefore probably requires exponential time on a quantum computer in the worst case, quantum algorithms have been developed to approximate ground and thermal states for some classes of Hamiltonians [102,132,121].
Algorithm: Knot Invariants
Speedup: Superpolynomial
Description: As shown by Freedman [42, 41], et al., finding a certain additive approximation to the Jones polynomial of the plat closure of a braid at \( e^{i 2 \pi/5} \) is a BQPcomplete problem. This result was reformulated and extended to \( e^{i 2 \pi/k} \) for arbitrary k by Aharonov et al. [4,2]. Wocjan and Yard further generalized this, obtaining a quantum algorithm to estimate the HOMFLY polynomial [93], of which the Jones polynomial is a special case. Aharonov et al. subsequently showed that quantum computers can in polynomial time estimate a certain additive approximation to the even more general Tutte polynomial for planar graphs [3]. It is not fully understood for what range of parameters the approximation obtained in [3] is BQPhard. (See also partition functions.) Polynomialtime quantum algorithms have also been discovered for additively approximating link invariants arising from quantum doubles of finite groups [174]. (This problem is not known to be BQPhard.) As shown in [83], the problem of finding a certain additive approximation to the Jones polynomial of the trace closure of a braid at \( e^{i 2 \pi/5} \) is DQC1complete.
Algorithm: Threemanifold Invariants
Speedup: Superpolynomial
Description: The TuraevViro invariant is a function that takes threedimensional manifolds as input and produces a real number as output. Homeomorphic manifolds yield the same number. Given a threemanifold specified by a Heegaard splitting, a quantum computer can efficiently find a certain additive approximation to its TuraevViro invariant, and this approximation is BQPcomplete [129]. Earlier, in [114], a polynomialtime quantum algorithm was given to additively approximate the WittenReshitikhinTuraev (WRT) invariant of a manifold given by a surgery presentation. Squaring the WRT invariant yields the TuraevViro invariant. However, it is unknown whether the approximation achieved in [114] is BQPcomplete. A suggestion of a possible link between quantum computation and threemanifold invariants was also given in [115].
Algorithm: Partition Functions
Speedup: Superpolynomial
Description: For a classical system with a finite set of states S the partition function is \( Z = \sum_{s \in S} e^{E(s)/kT} \), where T is the temperature and k is Boltzmann's constant. Essentially every thermodynamic quantity can be calculated by taking an appropriate partial derivative of the partition function. The partition function of the Potts model is a special case of the Tutte polynomial. A quantum algorithm for approximating the Tutte polynomial is given in [3]. Some connections between these approaches are discussed in [67]. Additional algorithms for estimating partition functions on quantum computers are given in [112,113,45,47]. A BQPcompleteness result (where the "energies" are allowed to be complex) is also given in [113]. A method for approximating partition functions by simulating thermalization processes is given in [121]. A quadratic speedup for the approximation of general partition functions is given in [122].
Algorithm: Adiabatic Algorithms
Speedup: Unknown
Description: In adiabatic quantum computation one starts with an initial Hamiltonian whose ground state is easy to prepare, and slowly varies the Hamiltonian to one whose ground state encodes the solution to some computational problem. By the adiabatic theorem, the system will track the instantaneous ground state provided the variation of the Hamiltonian is sufficiently slow. The runtime of an adiabatic algorithm scales at worst as \(1/ \gamma^3 \) where \( \gamma \) is the minimum eigenvalue gap between the ground state and the first excited state [185]. Adiabatic quantum computation was first proposed by Farhi et al. as a method for solving NPcomplete combinatorial optimization problems [96, 186]. Adiabatic quantum algorithms for optimization problems typically use "stoquastic" Hamiltonians, which do not suffer from the sign problem. Such algorithms are sometimes referred to as quantum annealing. Adiabatic quantum computation with nonstoquastic Hamiltonians is as powerful as the quantum circuit model [97]. Adiabatic algorithms using stoquastic Hamiltonians are probably less powerful [183], but may be nevertheless more powerful than classical computation. The asymptotic runtime of adiabatic optimization algorithms is notoriously difficult to analyze, but some progress has been achieved [179,180,181,182,187,188,189,190,191]. (Also relevant is an earlier literature on quantum annealing, which originally referred to a classical optimization algorithm that works by simulating a quantum process, much as simulated annealing is a classical optimization algorithm that works by simulating a thermal process. See e.g. [199, 198].) Adiabatic quantum computers can perform a process somewhat analogous to Grover search in \( O(\sqrt{N}) \) time [98]. Adiabatic quantum algorithms achieving quadratic speedup for a more general class of problems are constructed in [184] by adapting techniques from [85]. Adiabatic quantum algorithms have been proposed for several specific problems, including PageRank [176], machine learning [192, 195], and graph problems [193, 194]. Some quantum simulation algorithms also use adiabatic state preparation.
Algorithm: Zeta Functions
Speedup: Superpolynomial
Description: Let f(x,y) be a degreed polynomial over a finite field \( \mathbb{F}_p \). Let \( N_r \) be the number of projective solutions to f(x,y = 0 over the extension field \( \mathbb{F}_{p^r} \). The zeta function for f is defined to be \( Z_f(T) = \exp \left( \sum_{r=1}^\infty \frac{N_r}{r} T^r \right) \). Remarkably, \( Z_f(T) \) always has the form \( Z_f(T) = \frac{Q_f(T)}{(1pT)(1T)} \) where \( Q_f(T) \) is a polynomial of degree 2g and \(g = \frac{1}{2} (d1)(d2) \) is called the genus of f. Given \( Z_f(T) \) one can easily compute the number of zeros of f over any extension field \( \mathbb{F}_{p^r} \). One can similarly define the zeta function when the original field over which f is defined does not have prime order. As shown by Kedlaya [64], quantum computers can determine the zeta function of a genus g curve over a finite field \( \mathbb{F}_{p^r} \) in \( \mathrm{poly}(\log p, r, g) \) time. The fastest known classical algorithms are all exponential in either log(p) or g. In a diffent, but somewhat related contex, van Dam has conjectured that due to a connection between the zeros of Riemann zeta functions and the eigenvalues of certain quantum operators, quantum computers might be able to efficiently approximate the number of solutions to equations over finite fields [87].
Algorithm: Weight Enumerators
Speedup: Superpolynomial
Description: Let C be a code on n bits, i.e. a subset of \( \mathbb{Z}_2^n \). The weight enumerator of C is \( S_C(x,y) = \sum_{c \in C} x^{c} y^{nc} \) where c denotes the Hamming weight of c. Weight enumerators have many uses in the study of classical codes. If C is a linear code, it can be defined by \( C = \{c: Ac = 0\} \) where A is a matrix over \( \mathbb{Z}_2 \) In this case \( S_C(x,y) = \sum_{c:Ac=0} x^{c} y^{nc} \). Quadratically signed weight enumerators (QWGTs) are a generalization of this: \( S(A,B,x,y) = \sum_{c:Ac=0} (1)^{c^T B c} x^{c} y^{nc} \). Now consider the following special case. Let A be an \( n \times n \) matrix over \( \mathbb{Z}_2 \) such that diag(A)=I. Let lwtr(A) be the lower triangular matrix resulting from setting all entries above the diagonal in A to zero. Let l,k be positive integers. Given the promise that \( S(A,\mathrm{lwtr}(A),k,l) \geq \frac{1}{2} (k^2+l^2)^{n/2} \) the problem of determining the sign of \( S(A,\mathrm{lwtr}(A),k,l) \) is BQPcomplete, as shown by Knill and Laflamme in [65]. The evaluation of QWGTs is also closely related to the evaluation of Ising and Potts model partition functions [67,45,46].
Algorithm: Simulated Annealing
Speedup: Polynomial
Description: In simulated annealing, one has a series of Markov chains defined by stochastic matrices \( M_1, M_2,\ldots,M_n \). These are slowly varying in the sense that their limiting distributions \( pi_1, \pi_2, \ldots, \pi_n \) satisfy \( \pi_{t+1} \pi_t \lt \epsilon \) for some small \( \epsilon \). These distributions can often be thought of as thermal distributions at successively lower temperatures. If \( \pi_1 \) can be easily prepared, then by applying this series of Markov chains one can sample from \( \pi_n \). Typically, one wishes for \( \pi_n \) to be a distribution over good solutions to some optimization problem. Let \( \delta_i \) be the gap between the largest and second largest eigenvalues of \( M_i \). Let \( \delta = \min_i \delta_i \). The run time of this classical algorithm is proportional to \( 1/\delta \). Building upon results of Szegedy [135,85], Somma et al. have shown [84, 177] that quantum computers can sample from \( \pi_n \) with a runtime proportional to \( 1/\sqrt{\delta} \).
Algorithm: String Rewriting
Speedup: Superpolynomial
Description: String rewriting is a fairly general model of computation. String rewriting systems (sometimes called grammars) are specified by a list of rules by which certain substrings are allowed to be replaced by certain other substrings. For example, context free grammars, are equivalent to the pushdown automata. In [59], Janzing and Wocjan showed that a certain string rewriting problem is PromiseBQPcomplete. Thus quantum computers can solve it in polynomial time, but classical computers probably cannot. Given three strings s,t,t', and a set of string rewriting rules satisfying certain promises, the problem is to find a certain approximation to the difference between the number of ways of obtaining t from s and the number of ways of obtaining t' from s. Similarly, certain problems of approximating the difference in number of paths between pairs of vertices in a graph, and difference in transition probabilities between pairs of states in a random walk are also BQPcomplete [58].
Algorithm: Matrix Powers
Speedup: Superpolynomial
Description: Quantum computers have an exponential advantage in approximating matrix elements of powers of exponentially large sparse matrices. Suppose we are have an \( N \times N \) symmetric matrix A such that there are at most polylog(N) nonzero entries in each row, and given a row index, the set of nonzero entries can be efficiently computed. The task is, for any 1 < i < N, and any m polylogarithmic in N, to approximate \( (A^m)_{ii} \) the \( i^{\mathrm{th}} \) diagonal matrix element of \( A^m \). The approximation is additive to within \( b^m \epsilon \) where b is a given upper bound on A and \( \epsilon \) is of order 1/polylog(N). As shown by Janzing and Wocjan, this problem is PromiseBQPcomplete, as is the corresponding problem for offdiagonal matrix elements [60]. Thus, quantum computers can solve it in polynomial time, but classical computers probably cannot.
Acknowledgments
I thank the following people for contributing their expertise (in chronological order). Daniel Lidar
 Wim van Dam
 Geordie Rose
 YiKai Liu
 Robin Kothari
 Martin Schwarz
 Dorit Aharonov
 Alessandro Cosentino
 Andrew Childs
 Stacey Jeffery
 Lov Grover
 Eduin H Serna
References
 1

Daniel S. Abrams and Seth Lloyd
Simulation of manybody Fermi systems on a universal quantum computer.
Physical Review Letters, 79(13):25862589, 1997. arXiv:quantph/9703054.  2

Dorit Aharonov and Itai Arad
The BQPhardness of approximating the Jones polynomial.
New Journal of Physics 13:035019, 2011.
arXiv:quantph/0605181.  3

Dorit Aharonov, Itai Arad, Elad Eban, and Zeph Landau
Polynomial quantum algorithms for additive approximations of the Potts model and other points of the Tutte plane.
arXiv:quantph/0702008, 2007.  4

Dorit Aharonov, Vaughan Jones, and Zeph Landau
A polynomial quantum algorithm for approximating the Jones polynomial.
In Proceedings of the 38th ACM Symposium on Theory of Computing, 2006.
arXiv:quantph/0511096.  5

Dorit Aharonov and Amnon TaShma
Adiabatic quantum state generation and statistical zero knowledge.
In Proceedings of the 35th ACM Symposium on Theory of Computing, 2003.
arXiv:quantph/0301023.  6

A. Ambainis, H. Buhrman, P. Høyer, M. Karpinizki, and P. Kurur
Quantum matrix verification.
Unpublished Manuscript, 2002.  7

Andris Ambainis
Quantum walk algorithm for element distinctness.
SIAM Journal on Computing, 37:210239, 2007.
arXiv:quantph/0311001.  8

Andris Ambainis, Andrew M. Childs, Ben W.Reichardt, Robert Špalek, and
Shengyu Zheng
Every ANDOR formula of size N can be evaluated in time \( n^{1/2+o(1)} \) on a quantum computer.
In Proceedings of the 48th IEEE Symposium on the Foundations of Computer Science, pages 363372, 2007.
arXiv:quantph/0703015 and arXiv:0704.3628.  9

Dave Bacon, Andrew M. Childs, and Wim van Dam
From optimal measurement to efficient quantum algorithms for the hidden subgroup problem over semidirect product groups.
In Proceedings of the 46th IEEE Symposium on Foundations of Computer Science, pages 469478, 2005.
arXiv:quantph/0504083.  10

Michael BenOr and Avinatan Hassidim
Quantum search in an ordered list via adaptive learning.
arXiv:quantph/0703231, 2007.  11

Ethan Bernstein and Umesh Vazirani
Quantum complexity theory.
In Proceedings of the 25th ACM Symposium on the Theory of Computing, pages 1120, 1993.  12

D.W. Berry, G. Ahokas, R. Cleve, and B. C. Sanders
Efficient quantum algorithms for simulating sparse Hamiltonians.
Communications in Mathematical Physics, 270(2):359371, 2007.
arXiv:quantph/0508139.  13

A. Berzina, A. Dubrovsky, R. Frivalds, L. Lace, and O. Scegulnaja
Quantum query complexity for some graph problems.
In Proceedings of the 30th Conference on Current Trends in Theory and Practive of Coputer Science, pages 140150, 2004.  14

D. Boneh and R. J. Lipton
Quantum cryptoanalysis of hidden linear functions.
In Don Coppersmith, editor, CRYPTO '95, Lecture Notes in Computer Science, pages 424437. SpringerVerlag, 1995.  15

M. Boyer, G. Brassard, P. Høyer, and A. Tapp
Tight bounds on quantum searching.
Fortschritte der Physik, 46:493505, 1998.  16

G. Brassard, P. Høyer, and A. Tapp
Quantum counting.
arXiv:quantph/9805082, 1998.  17

Gilles Brassard, Peter Høyer, Michele Mosca, and Alain Tapp
Quantum amplitude amplification and estimation.
In Samuel J. Lomonaco Jr. and Howard E. Brandt, editors, Quantum Computation and Quantum Information: A Millennium Volume, volume 305 of AMS Contemporary Mathematics Series. American Mathematical Society, 2002.
arXiv:quantph/0005055.  18

Gilles Brassard, Peter Høyer, and Alain Tapp
Quantum algorithm for the collision problem.
ACM SIGACT News, 28:1419, 1997.
arXiv:quantph/9705002.  19

Harry Buhrman and Robert Špalek
Quantum verification of matrix products.
In Proceedings of the 17th ACMSIAM Symposium on Discrete Algorithms, pages 880889, 2006.
arXiv:quantph/0409035.  20

David Bulger
Quantum basin hopping with gradientbased local optimisation.
arXiv:quantph/0507193, 2005.  21

Harry Burhrman, Christoph Dürr, Mark Heiligman, Peter Høyer,
Frédéric Magniez, Miklos Santha, and Ronald de Wolf
Quantum algorithms for element distinctness.
In Proceedings of the 16th IEEE Annual Conference on Computational Complexity, pages 131137, 2001.
arXiv:quantph/0007016.  22

Dong Pyo Chi, Jeong San Kim, and Soojoon Lee
Notes on the hidden subgroup problem on some semidirect product groups.
Phys. Lett. A 359(2):114116, 2006.
arXiv:quantph/0604172.  23

A. M. Childs, L. J. Schulman, and U. V. Vazirani
Quantum algorithms for hidden nonlinear structures.
In Proceedings of the 48th IEEE Symposium on Foundations of Computer Science, pages 395404, 2007.
arXiv:0705.2784.  24

Andrew Childs and Troy Lee
Optimal quantum adversary lower bounds for ordered search.
Proceedings of ICALP 2008
arXiv:0708.3396.  25

Andrew M. Childs
Quantum information processing in continuous time.
PhD thesis, MIT, 2004.  26

Andrew M. Childs, Richard Cleve, Enrico Deotto, Edward Farhi, Sam Gutmann, and
Daniel A. Spielman
Exponential algorithmic speedup by quantum walk.
In Proceedings of the 35th ACM Symposium on Theory of Computing, pages 5968, 2003.
arXiv:quantph/0209131.  27

Andrew M. Childs, Richard Cleve, Stephen P. Jordan, and David Yeung
Discretequery quantum algorithm for NAND trees.
Theory of Computing, 5:119123, 2009.
arXiv:quantph/0702160.  28

Andrew M. Childs and Wim van Dam
Quantum algorithm for a generalized hidden shift problem.
In Proceedings of the 18th ACMSIAM Symposium on Discrete Algorithms, pages 12251232, 2007.
arXiv:quantph/0507190.  29

Richard Cleve, Dmitry Gavinsky, and David L. Yeung
Quantum algorithms for evaluating MINMAX trees.
In Theory of Quantum Computation, Communication, and Cryptography, pages 1115,
Springer, 2008. (LNCS Vol. 5106)
arXiv:0710.5794.  30

J. Niel de Beaudrap, Richard Cleve, and John Watrous
Sharp quantum versus classical query complexity separations.
Algorithmica, 34(4):449461, 2002.
arXiv:quantph/0011065v2.  31

Thomas Decker, Jan Draisma, and Pawel Wocjan
Quantum algorithm for identifying hidden polynomials.
Quantum Information and Computation, 9(3):215230, 2009.
arXiv:0706.1219.  32

David Deutsch
Quantum theory, the ChurchTuring principle, and the universal quantum computer.
Proceedings of the Royal Society of London Series A, 400:97117, 1985.  33

David Deutsch and Richard Jozsa
Rapid solution of problems by quantum computation.
Proceedings of the Royal Society of London Series A, 493:553558, 1992.  34

Christoph Dürr, Mark Heiligman, Peter Høyer, and Mehdi Mhalla
Quantum query complexity of some graph problems.
SIAM Journal on Computing, 35(6):13101328, 2006.
arXiv:quantph/0401091.  35

Christoph Dürr and Peter Høyer
A quantum algorithm for finding the minimum.
arXiv:quantph/9607014, 1996.  36

Christoph Dürr, Mehdi Mhalla, and Yaohui Lei
Quantum query complexity of graph connectivity.
arXiv:quantph/0303169, 2003.  37

Mark Ettinger, Peter Høyer, and Emanuel Knill
The quantum query complexity of the hidden subgroup problem is polynomial.
Information Processing Letters, 91(1):4348, 2004.
arXiv:quantph/0401083.  38

Edward Farhi, Jeffrey Goldstone, and Sam Gutmann
A quantum algorithm for the Hamiltonian NAND tree.
Theory of Computing 4:169190, 2008.
arXiv:quantph/0702144.  39

Edward Farhi, Jeffrey Goldstone, Sam Gutmann, and Michael Sipser
Invariant quantum algorithms for insertion into an ordered list.
arXiv:quantph/9901059, 1999.  40

Richard P. Feynman
Simulating physics with computers.
International Journal of Theoretical Physics, 21(6/7):467488, 1982.  41

Michael Freedman, Alexei Kitaev, and Zhenghan Wang
Simulation of topological field theories by quantum computers.
Communications in Mathematical Physics, 227:587603, 2002.  42

Michael Freedman, Michael Larsen, and Zhenghan Wang
A modular functor which is universal for quantum computation.
Comm. Math. Phys. 227(3):605622, 2002.
arXiv:quantph/0001108.  43

K. Friedl, G. Ivanyos, F. Magniez, M. Santha, and P. Sen
Hidden translation and orbit coset in quantum computing.
In Proceedings of the 35th ACM Symposium on Theory of Computing, pages 19, 2003.
arXiv:quantph/0211091.  44

D. Gavinsky
Quantum solution to the hidden subgroup problem for polynearHamiltoniangroups.
Quantum Information and Computation, 4:229235, 2004.  45

Joseph Geraci
A new connection between quantum circuits, graphs and the Ising partition function
Quantum Information Processing, 7(5):227242, 2008.
arXiv:0801.4833.  46

Joseph Geraci and Frank Van Bussel
A theorem on the quantum evaluation of weight enumerators for a certain class of cyclic Codes with a note on cyclotomic cosets.
arXiv:cs/0703129, 2007.  47

Joseph Geraci and Daniel A. Lidar
On the exact evaluation of certain instances of the Potts partition function by quantum computers.
Comm. Math. Phys. Vol. 279, pg. 735, 2008.
arXiv:quantph/0703023.  48

Lov K. Grover
Quantum mechanics helps in searching for a needle in a haystack.
Physical Review Letters, 79(2):325328, 1997.
arXiv:quantph/9605043.  49

Sean Hallgren
Polynomialtime quantum algorithms for Pell's equation and the principal ideal problem.
In Proceedings of the 34th ACM Symposium on Theory of Computing, 2002.  50

Sean Hallgren
Fast quantum algorithms for computing the unit group and class group of a number field.
In Proceedings of the 37th ACM Symposium on Theory of Computing, 2005.  51

Sean Hallgren, Alexander Russell, and Amnon TaShma
Normal subgroup reconstruction and quantum computation using group representations.
SIAM Journal on Computing, 32(4):916934, 2003.  52

Mark Heiligman
Quantum algorithms for lowest weight paths and spanning trees in complete graphs.
arXiv:quantph/0303131, 2003.  53

Yoshifumi Inui and François Le Gall
Efficient quantum algorithms for the hidden subgroup problem over a class of semidirect product groups.
Quantum Information and Computation, 7(5/6):559570, 2007.
arXiv:quantph/0412033.  54

Yuki Kelly Itakura
Quantum algorithm for commutativity testing of a matrix set.
Master's thesis, University of Waterloo, 2005.
arXiv:quantph/0509206.  55

Gábor Ivanyos, Frédéric Magniez, and Miklos Santha
Efficient quantum algorithms for some instances of the nonabelian hidden subgroup problem.
In Proceedings of the 13th ACM Symposium on Parallel Algorithms and Architectures, pages 263270, 2001.
arXiv:quantph/0102014.  56

Gábor Ivanyos, Luc Sanselme, and Miklos Santha
An efficient quantum algorithm for the hidden subgroup problem in extraspecial groups.
In Proceedings of the 24th Symposium on Theoretical Aspects of Computer Science, 2007.
arXiv:quantph/0701235.  57

Gábor Ivanyos, Luc Sanselme, and Miklos Santha
An efficient quantum algorithm for the hidden subgroup problem in nil2 groups.
In LATIN 2008: Theoretical Informatics, pg. 759771, Springer (LNCS 4957).
arXiv:0707.1260.  58

Dominik Janzing and Pawel Wocjan
BQPcomplete problems concerning mixing properties of classical random walks on sparse graphs.
arXiv:quantph/0610235, 2006.  59

Dominik Janzing and Pawel Wocjan
A promiseBQPcomplete string rewriting problem.
Quantum Information and Computation, 10(3/4):234257, 2010.
arXiv:0705.1180.  60

Dominik Janzing and Pawel Wocjan
A simple promiseBQPcomplete matrix problem.
Theory of Computing, 3:6179, 2007.
arXiv:quantph/0606229.  61

Stephen P. Jordan
Fast quantum algorithm for numerical gradient estimation.
Physical Review Letters, 95:050501, 2005.
arXiv:quantph/0405146.  62

Stephen P. Jordan
Quantum Computation Beyond the Circuit Model.
PhD thesis, Massachusetts Institute of Technology, 2008.
arXiv:0809.2307.  63

Ivan Kassal, Stephen P. Jordan, Peter J. Love, Masoud Mohseni, and Alán
AspuruGuzik
Quantum algorithms for the simulation of chemical dynamics.
Proc. Natl. Acad. Sci. Vol. 105, pg. 18681, 2008.
arXiv:0801.2986.  64

Kiran S. Kedlaya
Quantum computation of zeta functions of curves.
Computational Complexity, 15:119, 2006.
arXiv:math/0411623.  65

E. Knill and R. Laflamme
Quantum computation and quadratically signed weight enumerators.
Information Processing Letters, 79(4):173179, 2001.
arXiv:quantph/9909094.  66

Greg Kuperberg
A subexponentialtime quantum algorithm for the dihedral hidden subgroup problem.
SIAM Journal on Computing, 35(1):170188, 2005.
arXiv:quantph/0302112.  67

Daniel A. Lidar
On the quantum computational complexity of the Ising spin glass partition function and of knot invariants.
New Journal of Physics Vol. 6, pg. 167, 2004.
arXiv:quantph/0309064.  68

Daniel A. Lidar and Haobin Wang
Calculating the thermal rate constant with exponential speedup on a quantum computer.
Physical Review E, 59(2):24292438, 1999.
arXiv:quantph/9807009.  69

Chris Lomont
The hidden subgroup problem  review and open problems.
arXiv:quantph/0411037, 2004.  70

Frédéric Magniez, Miklos Santha, and Mario Szegedy
Quantum algorithms for the triangle problem.
SIAM Journal on Computing, 37(2):413424, 2007.
arXiv:quantph/0310134.  71

Carlos Magno, M. Cosme, and Renato Portugal
Quantum algorithm for the hidden subgroup problem on a class of semidirect product groups.
arXiv:quantph/0703223, 2007.  72

Cristopher Moore, Daniel Rockmore, Alexander Russell, and Leonard Schulman
The power of basis selection in Fourier sampling: the hidden subgroup problem in affine groups.
In Proceedings of the 15th ACMSIAM Symposium on Discrete Algorithms, pages 11131122, 2004.
arXiv:quantph/0211124.  73

M. Mosca
Quantum searching, counting, and amplitude amplification by eigenvector analysis.
In R. Freivalds, editor, Proceedings of International Workshop on Randomized Algorithms, pages 90100, 1998.  74

Michele Mosca
Quantum Computer Algorithms.
PhD thesis, University of Oxford, 1999.  75

Ashwin Nayak and Felix Wu
The quantum query complexity of approximating the median and related statistics.
In Proceedings of 31st ACM Symposium on the Theory of Computing, 1999.
arXiv:quantph/9804066.  76

Michael A. Nielsen and Isaac L. Chuang.
Quantum Computation and Quantum Information.
Cambridge University Press, Cambridge, UK, 2000.  77

Erich Novak
Quantum complexity of integration.
Journal of Complexity, 17:216, 2001.
arXiv:quantph/0008124.  78

Oded Regev
Quantum computation and lattice problems.
In Proceedings of the 43rd Symposium on Foundations of Computer Science, 2002.
arXiv:cs/0304005.  79

Oded Regev
A subexponential time algorithm for the dihedral hidden subgroup problem with polynomial space.
arXiv:quantph/0406151, 2004.  80

Ben Reichardt and Robert Špalek
Spanprogrambased quantum algorithm for evaluating formulas.
Proceedings of STOC 2008
arXiv:0710.2630.  81

Martin Roetteler and Thomas Beth
Polynomialtime solution to the hidden subgroup problem for a class of nonabelian groups.
arXiv:quantph/9812070, 1998.  82

Peter W. Shor
Polynomialtime algorithms for prime factorization and discrete logarithms on a quantum computer.
SIAM Journal on Computing, 26(5):14841509, 1997.
arXiv:quantph/9508027.  83

Peter W. Shor and Stephen P. Jordan
Estimating Jones polynomials is a complete problem for one clean qubit.
Quantum Information and Computation, 8(8/9):681714, 2008.
arXiv:0707.2831.  84

R. D. Somma, S. Boixo, and H. Barnum
Quantum simulated annealing.
arXiv:0712.1008, 2007.  85

M. Szegedy
Quantum speedup of Markov chain based algorithms.
In Proceedings of the 45th IEEE Symposium on Foundations of Computer Science, pg. 32, 2004.  86

Wim van Dam
Quantum algorithms for weighing matrices and quadratic residues.
Algorithmica, 34(4):413428, 2002.
arXiv:quantph/0008059.  87

Wim van Dam
Quantum computing and zeros of zeta functions.
arXiv:quantph/0405081, 2004.  88

Wim van Dam and Sean Hallgren
Efficient quantum algorithms for shifted quadratic character problems.
arXiv:quantph/0011067, 2000.  89

Wim van Dam, Sean Hallgren, and Lawrence Ip
Quantum algorithms for some hidden shift problems.
SIAM Journal on Computing, 36(3):763778, 2006.
arXiv:quanth/0211140.  90

Wim van Dam and Gadiel Seroussi
Efficient quantum algorithms for estimating Gauss sums.
arXiv:quantph/0207131, 2002.  91

John Watrous
Quantum algorithms for solvable groups.
In Proceedings of the 33rd ACM Symposium on Theory of Computing, pages 6067, 2001.
arXiv:quantph/0011023.  92

Stephen Wiesner
Simulations of manybody quantum systems by a quantum computer.
arXiv:quantph/9603028, 1996.  93

Pawel Wocjan and Jon Yard
The Jones polynomial: quantum algorithms and applications in quantum complexity theory.
Quantum Information and Computation 8(1/2):147180, 2008.
arXiv:quantph/0603069.  94

Andrew Yao
On computing the minima of quadratic forms.
In Proceedings of the 7th ACM Symposium on Theory of Computing, pages 2326, 1975.  95

Christof Zalka
Efficient simulation of quantum systems by quantum computers.
Proceedings of the Royal Society of London Series A, 454:313, 1996.
arXiv:quantph/9603026.  96

Edward Farhi, Jeffrey Goldstone, Sam Gutmann, and Michael Sipser
Quantum computation by adiabatic evolution.
arXiv:quantph/0001106, 2000.  97

Dorit Aharonov, Wim van Dam, Julia Kempe, Zeph Landau, Seth Lloyd, and
Oded Regev
Adiabatic Quantum Computation is Equivalent to Standard Quantum Computation.
SIAM Journal on Computing, 37(1):166194, 2007.
arXiv:quantph/0405098  98

Jérémie Roland and Nicolas J. Cerf
Quantum search by local adiabatic evolution.
Physical Review A, 65(4):042308, 2002.
arXiv:quantph/0107015  99

L.A. Wu, M.S. Byrd, and D. A. Lidar
PolynomialTime Simulation of Pairing Models on a Quantum Computer.
Physical Review Letters, 89(6):057904, 2002.
arXiv:quantph/0108110  100

Eli Biham, Ofer Biham, David Biron, Markus Grassl, and Daniel Lidar
Grover's quantum search algorithm for an arbitrary initial amplitude distribution.
Physical Review A, 60(4):2742, 1999.
arXiv:quantph/9807027 and arXiv:quantph/0010077  101

Andrew Childs, Shelby Kimmel, and Robin Kothari
The quantum query complexity of readmany formulas
In Proceedings of ESA 2012, pg. 337348, Springer. (LNCS 7501)
arXiv:1112.0548, 2011.  102

Alán AspuruGuzik, Anthony D. Dutoi, Peter J. Love, and Martin HeadGordon
Simulated quantum computation of molecular energies.
Science, 309(5741):17041707, 2005.
arXiv:quantph/0604193  103

A. M. Childs, A. J. Landahl, and P. A. Parrilo
Quantum algorithms for the ordered search problem via semidefinite programming.
Physical Review A, 75 032335, 2007.
arXiv:quantph/0608161  104

Aram W. Harrow, Avinatan Hassidim, and Seth Lloyd
Quantum algorithm for solving linear systems of equations.
Physical Review Letters 15(103):150502, 2009.
arXiv:0811.3171.  105

Martin Roetteler
Quantum algorithms for highly nonlinear Boolean functions.
Proceedings of SODA 2010
arXiv:0811.3208.  106

Stephen P. Jordan
Fast quantum algorithms for approximating the irreducible representations of groups.
arXiv:0811.0562, 2008.  107

Tim Byrnes and Yoshihisa Yamamoto
Simulating lattice gauge theories on a quantum computer.
Physical Review A, 73, 022328, 2006.
arXiv:quantph/0510027.  108

D. Simon
On the Power of Quantum Computation.
In Proceedings of the 35th Symposium on Foundations of Computer Science, pg. 116123, 1994.  109

John Proos and Christof Zalka
Shor's discrete logarithm quantum algorithm for elliptic curves.
Quantum Information and Computation, Vol. 3, No. 4, pg.317344, 2003.
arXiv:quantph/0301141.  110

YiKai Liu
Quantum algorithms using the curvelet transform.
Proceedings of STOC 2009, pg. 391400.
arXiv:0810.4968.  111

Wim van Dam and Igor Shparlinski
Classical and quantum algorithms for exponential congruences.
Proceedings of TQC 2008, pg. 110.
arXiv:0804.1109.  112

Itai Arad and Zeph Landau
Quantum computation and the evaluation of tensor networks.
SIAM Journal on Computing, 39(7):30893121, 2010.
arXiv:0805.0040.  113

M. Van den Nest, W. Dür, R. Raussendorf, and H. J. Briegel
Quantum algorithms for spin models and simulable gate sets for quantum computation.
Physical Review A, 80:052334, 2009.
arXiv:0805.1214.  114

Silvano Garnerone, Annalisa Marzuoli, and Mario Rasetti
Efficient quantum processing of 3manifold topological invariants.
Advances in Theoretical and Mathematical Physics, 13(6):16011652, 2009.
arXiv:quantph/0703037.  115

Louis H. Kauffman and Samuel J. Lomonaco Jr.
qdeformed spin networks, knot polynomials and anyonic topological quantum computation.
Journal of Knot Theory, Vol. 16, No. 3, pg. 267332, 2007.
arXiv:quantph/0606114.  116

Arthur Schmidt and Ulrich Vollmer
Polynomial time quantum algorithm for the computation of the unit group of a number field.
In Proceedings of the 37th Symposium on the Theory of Computing, pg. 475480, 2005.  117

Sergey Bravyi, Aram Harrow, and Avinatan Hassidim
Quantum algorithms for testing properties of distributions.
IEEE Transactions on Information Theory 57(6):39713981, 2011.
arXiv:0907.3920.  118

Pawel M. Wocjan, Stephen P. Jordan, Hamed Ahmadi, and Joseph P. Brennan
Efficient quantum processing of ideals in finite rings.
arXiv:0908.0022, 2009.  119

V. Arvind, Bireswar Das, and Partha Mukhopadhyay
The complexity of blackbox ring problems.
In Proceedings of COCCOON 2006, pg 126145.  120

V. Arvind and Partha Mukhopadhyay
Quantum query complexity of multilinear identity testing.
In Proceedings of STACS 2009, pg. 8798.  121

David Poulin and Pawel Wocjan
Sampling from the thermal quantum Gibbs state and evaluating partition functions with a quantum computer.
Physical Review Letters 103:220502, 2009.
arXiv:0905.2199  122

Pawel Wocjan, ChenFu Chiang, Anura Abeyesinghe, and Daniel Nagaj
Quantum speedup for approximating partition functions.
Physical Review A 80:022340, 2009.
arXiv:0811.0596  123

Ashley Montanaro
Quantum search with advice.
In Proceedings of the 5th conference on Theory of quantum computation, communication, and cryptography (TQC 2010)
arXiv:0908.3066  124

Laszlo Babai, Robert Beals, and Akos Seress
Polynomialtime theory of matrix groups.
In Proceedings of STOC 2009, pg. 5564.  125

Peter Shor
Algorithms for Quantum Computation: Discrete Logarithms and Factoring.
In Proceedings of FOCS 1994, pg. 124134.  126

Aaron Denney, Cristopher Moore, and Alex Russell
Finding conjugate stabilizer subgroups in PSL(2;q) and related groups.
Quantum Information and Computation 10(3):282291, 2010.
arXiv:0809.2445.  127

Kevin K. H. Cheung and Michele Mosca
Decomposing finite Abelian groups.
Quantum Information and Computation 1(2):2632, 2001.
arXiv:cs/0101004.  128

François Le Gall
An efficient quantum algorithm for some instances of the group isomorphism problem.
In Proceedings of STACS 2010.
arXiv:1001.0608.  129

Gorjan Alagic, Stephen Jordan, Robert Koenig, and Ben Reichardt
Approximating TuraevViro 3manifold invariants is universal for quantum computation.
Physical Review A 82, 040302(R), 2010.
arXiv:1003.0923  130

Martin Rötteler
Quantum algorithms to solve the hidden shift problem for quadratics and for functions of large Gowers norm.
In Proceedings of MFCS 2009, pg 663674.
arXiv:0911.4724.  131

Arthur Schmidt
Quantum Algorithms for manytoone Functions to Solve the Regulator and the Principal Ideal Problem.
arXiv:0912.4807, 2009.  132

K. Temme, T.J. Osborne, K.G. Vollbrecht, D. Poulin, and F. Verstraete
Quantum Metropolis Sampling.
Nature, Vol. 471, pg. 8790, 2011.
arXiv:0911.3635.  133

Andris Ambainis
Quantum Search Algorithms.
SIGACT News, 35 (2):2235, 2004.
arXiv:quantph/0504012  134

Nicolas J. Cerf, Lov K. Grover, and Colin P. Williams
Nested quantum search and NPhard problems.
Applicable Algebra in Engineering, Communication and Computing, 10 (45):311338, 2000.  135

Mario Szegedy
Spectra of Quantized Walks and a \( \sqrt{\delta \epsilon} \) rule.
arXiv:quantph/0401053, 2004.  136

Kazuo Iwama, Harumichi Nishimura, Rudy Raymond, and Junichi Teruyama
Quantum Counterfeit Coin Problems.
In Proceedings of 21st International Symposium on Algorithms and Computation (ISAAC2010), LNCS 6506, pp.7384, 2010.
arXiv:1009.0416  137

Barbara Terhal and John Smolin
Single quantum querying of a database.
Physical Review A 58:1822, 1998.
arXiv:quantph/9705041  138

Andris Ambainis
Variable time amplitude amplification and a faster quantum algorithm for solving systems of linear equations.
arXiv:1010.4458, 2010.  139

Frédéric Magniez and Ashwin Nayak
Quantum complexity of testing group commutativity.
In Proceedings of 32nd International Colloquium on Automata, Languages and Programming. LNCS 3580, pg. 13121324, 2005.
arXiv:quantph/0506265  140

Andrew Childs and Robin Kothari
Quantum query complexity of minorclosed graph properties.
In Proceedings of the 28th Symposium on Theoretical Aspects of Computer Science (STACS 2011), pg. 661672
arXiv:1011.1443  141

Frédéric Magniez, Ashwin Nayak, Jérémie Roland, and Miklos Santha
Search via quantum walk.
In Proceedings STOC 2007, pg. 575584.
arXiv:quantph/0608026  142

Dmitry Gavinsky, Martin Roetteler, and Jérémy Roland
Quantum algorithm for the Boolean hidden shift problem.
In Proceedings of the 17th annual international conference on Computing and combinatorics (COCOON '11), 2011.
arXiv:1103.3017  143

Mark Ettinger and Peter Høyer
On quantum algorithms for noncommutative hidden subgroups.
Advances in Applied Mathematics, Vol. 25, No. 3, pg. 239251, 2000.
arXiv:quantph/9807029  144

Andris Ambainis, Andrew Childs, and YiKai Liu
Quantum property testing for boundeddegree graphs.
In Proceedings of RANDOM '11: Lecture Notes in Computer Science 6845, pp. 365376, 2011.
arXiv:1012.3174  145

G. Ortiz, J.E. Gubernatis, E. Knill, and R. Laflamme
Quantum algorithms for Fermionic simulations.
Physical Review A 64: 022319, 2001.
arXiv:condmat/0012334  146

Ashley Montanaro
The quantum query complexity of learning multilinear polynomials.
Information Processing Letters, 112(11):438442, 2012.
arXiv:1105.3310.  147

Tad Hogg
Highly structured searches with quantum computers.
Physical Review Letters 80: 2473, 1998.  148

Markus Hunziker and David A. Meyer
Quantum algorithms for highly structured search problems.
Quantum Information Processing, Vol. 1, No. 3, pg. 321341, 2002.  149

Ben Reichardt
Span programs and quantum query complexity: The general adversary bound is nearly tight for every Boolean function.
In Proceedings of the 50th IEEE Symposium on Foundations of Computer Science (FOCS '09), pg. 544551, 2009.
arXiv:0904.2759  150

Aleksandrs Belovs
Spanprogrambased quantum algorithm for the rank problem.
arXiv:1103.0842, 2011.  151

Sebastian Dörn and Thomas Thierauf
The quantum query complexity of the determinant.
Information Processing Letters Vol. 109, No. 6, pg. 305328, 2009.  152

Aleksandrs Belovs
Span programs for functions with constantsized 1certificates.
In Proceedings of STOC 2012, pg. 7784.
arXiv:1105.4024.  153

Troy Lee, Frédéric Magniez, and Mikos Santha
A learning graph based quantum query algorithm for finding constantsize subgraphs.
Chicago Journal of Theoretical Computer Science, Vol. 2012, Article 10, 2012.
arXiv:1109.5135.  154

Aleksandrs Belovs and Troy Lee
Quantum algorithm for kdistinctness with prior knowledge on the input.
arXiv:1108.3022, 2011.  155

François Le Gall
Improved outputsensitive quantum algorithms for Boolean matrix multiplication.
In Proceedings of the 23rd Annual ACMSIAM Symposium on Discrete Algorithms (SODA '12), 2012.  156

Dominic Berry
Quantum algorithms for solving linear differential equations.
arXiv:1010.2745, 2010.  157

Virginia Vassilevska Williams and Ryan Williams
Subcubic equivalences between path, matrix, and triangle problems.
In 51st IEEE Symposium on Foundations of Computer Science (FOCS '10) pg. 645  654, 2010.  158

Ben W. Reichardt
Reflections for quantum query algorithms.
In Proceedings of the 22nd ACMSIAM Symposium on Discrete Algorithms (SODA), pg. 560569, 2011.
arXiv:1005.1601  159

Ben W. Reichardt
Spanprogrambased quantum algorithm for evaluating unbalanced formulas.
arXiv:0907.1622, 2009.  160

Ben W. Reichardt
Faster quantum algorithm for evaluating game trees.
In Proceedings of the 22nd ACMSIAM Symposium on Discrete Algorithms (SODA), pg. 546559, 2011.
arXiv:0907.1623  161

Stacey Jeffery, Robin Kothari, and Frédéric Magniez
Improving quantum query complexity of Boolean matrix multiplication using graph collision.
In Proceedings of ICALP 2012, pg. 522532.
arXiv:1112.5855.  162

Andrew M. Childs and Jason M. Eisenberg
Quantum algorithms for subset finding.
Quantum Information and Computation 5(7):593604, 2005.
arXiv:quantph/0311038.  163

Aleksandrs Belovs and Robert Špalek
Adversary lower bound for the ksum problem.
In Proceedings of ITCS 2013, pg. 323328.
arXiv:1206.6528.  164

Bohua Zhan, Shelby Kimmel, and Avinatan Hassidim
Superpolynomial quantum speedups for Boolean evaluation trees with hidden structure.
ITCS 2012: Proceedings of the 3rd Innovations in Theoretical Computer Science, ACM, pg. 249265.
arXiv:1101.0796  165

Shelby Kimmel
Quantum adversary (upper) bound.
39th International Colloquium on Automata, Languages and Programming  ICALP 2012 Volume 7391, p. 557568.
arXiv:1101.0797  166

Stephen Jordan, Keith Lee, and John Preskill
Quantum algorithms for quantum field theories.
Science, Vol. 336, pg. 11301133, 2012.
arXiv:1111.3633  167

Andris Ambainis and Ashley Montanaro
Quantum algorithms for search with wildcards and combinatorial group testing.
arXiv:1210.1148, 2012.  168

Andris Ambainis and Robert Špalek
Quantum algorithms for matching and network flows.
Proceedings of STACS 2007, pg. 172183.
arXiv:quantph/0508205  169

Nathan Wiebe, Daniel Braun, and Seth Lloyd
Quantum datafitting.
Physical Review Letters 109, 050505, 2012.
arXiv:1204.5242  170

Andrew Childs and Nathan Wiebe
Hamiltonian simulation using linear combinations of unitary operations.
Quantum Information and Computation 12, 901924, 2012.
arXiv:1202.5822  171

Stacey Jeffery, Robin Kothari, and Frédéric Magniez
Nested quantum walks with quantum data structures.
arXiv:1210.1199, 2012.  172

Aleksandrs Belovs
Learninggraphbased quantum algorithm for kdistinctness.
Proceedings of STOC 2012, pg. 7784.
arXiv:1205.1534, 2012.  173

Andrew Childs, Stacey Jeffery, Robin Kothari, and Frédéric Magniez
A timeefficient quantum walk for 3distinctness using nested updates.
arXiv:1302.7316, 2013.  174

Hari Krovi and Alexander Russell
Quantum Fourier transforms and the complexity of link invariants for quantum doubles of finite groups.
arXiv:1210.1550, 2012.  175

Troy Lee, Frédéric Magniez, and Miklos Santha
Improved quantum query algorithms for triangle finding and associativity testing.
arXiv:1210.1014, 2012.  176

Silvano Garnerone, Paolo Zanardi, and Daniel A. Lidar
Adiabatic quantum algorithm for search engine ranking.
Physical Review Letters 108:230506, 2012.  177

R. D. Somma, S. Boixo, H. Barnum, and E. Knill
Quantum simulations of classical annealing.
Physical Review Letters 101:130504, 2008.
arXiv:0804.1571.  178

Daniel J. Bernstein, Stacey Jeffery, Tanja Lange, and Alexander Meurer
Quantum algorithms for the subsetsum problem.
from cr.yp.to.  179

Boris Altshuler, Hari Krovi, and Jérémie Roland
Anderson localization casts clouds over adiabatic quantum optimization.
Proceedings of the National Academy of Sciences 107(28):1244612450, 2010.
arXiv:0912.0746.  180

Ben Reichardt
The quantum adiabatic optimization algorithm and local minima.
In Proceedings of STOC 2004, pg. 502510. [Erratum].  181

Edward Farhi, Jeffrey Goldstone, and Sam Gutmann
Quantum adiabatic evolution algorithms versus simulated annealing.
arXiv:quantph/0201031, 2002.  182

E. Farhi, J. Goldstone, D. Gosset, S. Gutmann, H. B. Meyer, and P. Shor
Quantum adiabatic algorithms, small gaps, and different paths.
Quantum Information and Computation, 11(3/4):181214, 2011.
arXiv:0909.4766.  183

Sergey Bravyi, David P. DiVincenzo, Roberto I. Oliveira, and Barbara M. Terhal
The Complexity of Stoquastic Local Hamiltonian Problems.
Quantum Information and Computation, 8(5):361385, 2008.
arXiv:quantph/0606140.  184

Rolando D. Somma and Sergio Boixo
Spectral gap amplification.
SIAM Journal on Computing, 42:593610, 2013.
arXiv:1110.2494.  185

Sabine Jansen, MaryBeth Ruskai, Ruedi Seiler
Bounds for the adiabatic approximation with applications to quantum computation.
Journal of Mathematical Physics, 48:102111, 2007.
arXiv:quantph/0603175.  186

E. Farhi, J. Goldstone, S. Gutmann, J. Lapan, A. Lundgren, and D. Preda
A Quantum Adiabatic Evolution Algorithm Applied to Random Instances of an NPComplete Problem.
Science, 292(5516):472475, 2001.
arXiv:quantph/0104129.  187

Edward Farhi, Jeffrey Goldstone, Sam Gutmann, and Daniel Nagaj
How to make the quantum adiabatic algorithm fail.
International Journal of Quantum Information, 6(3):503516, 2008.
arXiv:quantph/0512159.  188

Edward Farhi, Jeffrey Goldstone, Sam Gutmann, and Daniel Nagaj
Unstructured randomness, small gaps, and localization.
Quantum Information and Computation, 11(9/10):840854, 2011.
arXiv:1010.0009.  189

Edward Farhi, Jeffrey Goldstone, Sam Gutmann
Quantum adiabatic evolution algorithms with different paths.
arXiv:quantph/0208135, 2002.  190

Wim van Dam, Michele Mosca, and Umesh Vazirani
How powerful is adiabatic quantum computation?
In Proceedings of FOCS 2001, pg. 279287.
arXiv:quantph/0206003 [See also this.]  191

E. Farhi, D. Gosset, I. Hen, A. W. Sandvik, P. Shor, A. P. Young, and F. Zamponi
The performance of the quantum adiabatic algorithm on random instances of two optimization problems on regular hypergraphs.
Physical Review A, 86:052334, 2012.
arXiv:1208.3757.  192

Kristen L. Pudenz and Daniel A. Lidar
Quantum adiabatic machine learning.
Quantum Information Processing, 12:2027, 2013.
arXiv:1109.0325.  193

Frank Gaitan and Lane Clark
Ramsey numbers and adiabatic quantum computing.
Physical Review Letters, 108:010501, 2012.
arXiv:1103.1345.  194

Frank Gaitan and Lane Clark
Graph isomorphism and adiabatic quantum computing.
arXiv:1304.5773, 2013.  195

Hartmut Neven, Vasil S. Denchev, Geordie Rose, and William G. Macready
Training a binary classifier with the quantum adiabatic algorithm.
arXiv:0811.0416, 2008.  196

Robert Beals
Quantum computation of Fourier transforms over symmetric groups.
In Proceedings of STOC 1997, pg. 4853.  197

Dave Bacon, Isaac L. Chuang, and Aram W. Harrow
The quantum Schur transform: I. efficient qudit circuits.
In Proceedings of SODA 2007, pg. 12351244.
arXiv:quantph/0601001.  198

S. Morita, H. Nishimori
Mathematical foundation of quantum annealing.
Journal of Methematical Physics, 49(12):125210, 2008.  199

A. B. Finnila, M. A. Gomez, C. Sebenik, C. Stenson, J. D. Doll
Quantum annealing: a new method for minimizing multidimensional functions.
Chemical Physics Letters, 219:343348, 1994.  200

D. Gavinsky and T. Ito
A quantum query algorithm for the graph collision problem.
arXiv:1204.1527, 2012.  201

Andris Ambainis, Kaspars Balodis, Jānis Iraids, Raitis Ozols, and
Juris Smotrovs
Parameterized quantum query complexity of graph collision.
arXiv:1305.1021, 2013.  202

Kevin C. Zatloukal
Classical and quantum algorithms for testing equivalence of group extensions.
arXiv:1305.1327, 2013.  203

Andrew Childs and Gábor Ivanyos
Quantum computation of discrete logarithms in semigroups.
arXiv:1310.6238, 2013.  204

Matan Banin and Boaz Tsaban
A reduction of semigroup DLP to classic DLP.
arXiv:1310.7903, 2013.  205

D. W. Berry, R. Cleve, and R. D. Somma
Exponential improvement in precision for Hamiltonianevolution simulation.
arXiv:1308.5424, 2013.  206

François Le Gall and Harumichi Nishimura
Quantum algorithms for matrix products over semirings.
arXiv:1310.3898, 2013.  207

Nolan Wallach
A quantum polylog algorithm for nonnormal maximal cyclic hidden subgroups in the affine group of a finite field.
arXiv:1308.1415, 2013.  208

Lov Grover
Fixedpoint quantum search.
Phys. Rev. Lett. 95(15):150501, 2005.
arXiv:quantph/0503205  209

Tathagat Tulsi, Lov Grover, and Apoorva Patel
A new algorithm for fixed point quantum search.
Quantum Information and Computation 6(6):483494, 2005.
arXiv:quantph/0505007  210

Guoming Wang
Quantum algorithms for approximating the effective resistances of electrical networks.
arXiv:1311.1851  211

Dominic W. Berry, Andrew M. Childs, Richard Cleve, Robin Kothari, and Rolando D. Somma
Exponential improvement in precision for simulating sparse Hamiltonians
arXiv:1312.1414  212

Thomas Decker, Peter Høyer, Gabor Ivanyos, and Miklos Santha
Polynomial time quantum algorithms for certain bivariate hidden polynomial problems
arXiv:1305.1543  213

Kirsten Eisenträger, Sean Hallgren, Alexei Kitaev, and Fang Song
A quantum algorithm for computing the unit group of an arbitrary degree number field
STOC, 2014  214

Seth Lloyd, Masoud Mohseni, and Patrick Robentrost
Quantum algorithms for supervised and unsupervised machine learning
arXiv:1307.0411