Quantum Algorithm Zoo

This page contains a summary of known quantum algorithms offering speedup over the best known classical algorithms. I have adapted this list from the first chapter of my thesis with the hope that it will be a useful resource. For an introduction to quantum computation I recommend the book by Nielsen and Chuang and the lecture notes by Preskill. For a pedagogical (noncomprehensive) surveys of quantum algorithms I recommend this and this. If you have noticed any errors or omissions in this page please contact me at .

Terminology: If there exists a positive constant $\alpha$ such that the runtime of the best known classical algorithm and the runtime of the quantum algorithm satisfy $C = 2^{\Omega(Q^\alpha)}$ , then I call the speedup superpolynomial. Otherwise I call it polynomial. (For a review of the $O, \Omega, \Theta$ notation see this.)

Algebraic and Number Thoretic Problems
Oracular Problems
Approximation and BQP-complete problems
References

Algebraic and Number Theoretic Problems

Algorithm: Factoring
Speedup: Superpolynomial
Description: Given an n-bit integer, find the prime factorization. The quantum algorithm of Peter Shor solves this in poly(n) time [82]. The fastest known classical algorithm requires time superpolynomial in n. This 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: Discrete-log
Speedup: Superpolynomial
Description: We are given three n-bit 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]. See also Abelian hidden subgroup.

Algorithm: Pell's Equation
Speedup: Superpolynomial
Description: Given a positive nonsquare integer d, Pell's equation is

. For any such d there are infinitely many pairs of integers (x,y) solving this equation. Let

be the pair that minimizes $x+y\sqrt{d}$ . If d is an n-bit integer (i.e. $0 \leq d < 2^n$ ), then

may in general require exponentially many bits to write down. Thus it is in general impossible to find

in polynomial time. Let $R = \log(x_1+y_1 \sqrt{d})$ . $\lfloor R \rceil$ uniquely identifies

. As shown by Hallgren[49], given a n-bit number

, 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 Buchman-Williams cryptosystem. See also Abelian hidden subgroup.

Algorithm: Principal Ideal
Speedup: Superpolynomial
Description: We are given an n-bit integer d and an invertible ideal I of the ring $\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]. 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. See also Abelian hidden subgroup.

Algorithm: Class 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)$ . 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 representation $\rho^\times$ of $\mathbb{F}_q^\times$ and some representation $\rho^+$ of $\mathbb{F}_q^+$ . Let $\chi^\times$ and $\chi^+$ be the characters of these representations. The Gauss sum corresponding to $\rho^\times$ and $\rho^+$ 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 polynomial-time quantum algorithm related to Gauss sum estimation[47].

Algorithm:Solving Exponential Congruences
Speedup:Polynomial
Description: We are given $a,b,c,f,g \in \mathbb{F}_q$ . We must find $x,y \in \mathbb{F}_q$ such that

. As shown in [111], quantum computers can solve this problem in $O(q^{3/8})$ time whereas the best classical algorithm requires $O(q^{9/8})$ time (ignoring logarithmic factors in both cases). 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. Quantum circuits can efficiently implement unitary versions of all the irreducible representations of the symmetric and alternating groups, and all the irreducible representations of unitary, special unitary, and orthogonal groups with polynomial highest weight. As discussed in [106], using the Hadamard test one can thus approximate individual matrix elements of the irreducible representations of these groups to polynomial precision in polynomial time, whereas for certain hard instances, classical computers probably cannot achieve this.

Oracular Problems

Algorithm: Searching
Speedup: Polynomial
Description: We are given an oracle with N allowed inputs. For one input w ("the winner") the corresponding output is 1, and for all other inputs the corresponding output is 0. The task is to find w. On a classical computer this requires $\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], and approximate definite integrals [77]. 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.

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$ ,

if and only if

and

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(\vert G\vert)$ 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 discrete-log 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 $\log(\vert G\vert)$ , see [30].

Algorithm: Non-Abelian 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 \in G$ ,

if and only if

and

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(\vert G\vert)$ queries, whereas classically $\Omega(\vert G\vert)$ 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 non-Abelian groups[81,55,72,53,9,22,56,71,57,43,44,28]. 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 polynomial-time solution for these groups is known. However, Kuperburg[66] found a time $O(2^{C \sqrt{\log N}})$ algorithm for finding a hidden subgroup of the dihedral group

. Regev subsequently improved this algorithm so that it uses not only subexponential time but also polynomial space[79].

Algorithm: Bernstein-Vazirani
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: Deutsch-Josza
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

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 well-defined quantum algorithm achieving a speedup over classical computation. A single-query quantum algorithm for arbitrary n was developed by Deutsch and Josza in [33]. Although probabilistically easy to solve with O(1) queries, the Deutsch-Josza problem has exponential worst case deterministic query complexity classically.

Algorithm: NAND Tree
Speedup: Polynomial
Description: A NAND gate takes two bits of input and produces one bit of output. By connecting together NAND gates, one can thus form a binary tree of depth n which has

bits of input and produces one bit of output. The NAND tree problem is to evaluate the output of such a tree by making queries to an oracle which stores the values of the

bits and provides any specified one of them upon request. Farhi et al. used a continuous time quantum walk model to show that a quantum computer can solve this problem using $O(2^{0.5n})$ time whereas a classical computer requires $\Omega(2^{0.753n})$ time[38]. It was soon shown that this result carries over into the conventional model of circuits and queries[27]. The algorithm was subsequently generalized for NAND trees of varying fanin and noniform depth[8], and to trees involving larger gate sets[80], and MIN-MAX trees [29].

Algorithm: Gradients
Speedup: Polynomial
Description: 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[20]. 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.

Algorithm: Hidden Shift
Speedup: Superpolynomial
Description: We are given oracle access to some function f(x) on a domain of size 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(\mathrm{polylog}(N))$ is known for these problems. Furthermore, the quantum algorithm for the shifted Legendre symbol problem breaks certain classical cryptosystems[89]. Exponential quantum speedup for hidden shift problems based on nonlinear Boolean functions are obtained in [105].

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. As shown in [104], a quantum computer can in O(polylog 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 constructible). For certain functions, such as f(x)=1/x, this procedure can be extended to non-Hermitian and even non-square A.

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{ln(2)}{\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
Speedup: Polynomial
Description: A common way to specify a graph is by an oracle, which given a pair of vertices, reveals whether they are connected by an edge. This is called the adjacency matrix model. It generalizes straightforwardly for weighted and directed graphs. 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. For many of these problems, the quantum complexity is also known for the case where the oracle provides an array of neighbors rather than entries of the adjacency matrix[34]. See also triangle finding.

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 depth-n 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
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]. Buhrman et al. subsequently showed that a quantum computer can also find a collision in an arbitrary function on domain of size N, provided that one exists, using $O(N^{3/4} \log N)$ queries[21], whereas the classical query complexity is $\Theta(N \log N)$ . The decision version of collision finding is called element distinctness, and also has $\Theta(N \log N)$ classical query complexity. Ambainis subsequently improved upon[18], achieving a quantum query complexity of $O(N^{2/3})$ for element distinctness, which is optimal, and extending to the case of k-fold collisions[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). A quantum computer can find claws using $O(N^{3/4} \log N)$ queries[21]. One can also define collision finding on a graph: a value is associated with each vertex, and a collision only counts if the vertices share an edge. This can be solved using $O(N^{2/3})$ quantum queries[70].

Algorithm: Triangle Finding
Speedup: Polynomial
Description: Suppose we are given oracle access to a graph with N nodes. When queried with a pair of nodes, the oracle reveals whether an edge connects them. The task is to find a triangle (i.e. a clique of size three) if one exists. As shown by Buhrman et al. [21], a quantum computer can accomplish this using $O(N^{3/2})$ queries, whereas $\Omega(N^2)$ classical queries are required. Magniez et al. subsequently improved on this, finding a triangle with $O(N^{13/10})$ quantum queries[70]. More generally, a quantum computer can find an arbitrary subgraph of k vertices in $\Omega(N^{2-2/k})$ time, up to logarithmic factors[70].

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\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

queries.

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 non-Abelian groups (see non-Abelian 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].

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 $\delta$ (e.g., when the level sets of f are spherical shells of thickness $\delta$ ); the classical lower bound holds independent of $\delta$ . The 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 $\mathrm{polylog}(\vert G\vert)$ queries even if G is Abelian. For Abelian groups, quantum computers can solve these problems using $\mathrm{polylog}(\vert G\vert)$ queries by reduction to the Abelian hidden subgroup problem, as shown by Mosca[74]. Furthermore, as shown by Watrous[91], these problem can be solved in $\mathrm{polylog}(\vert G\vert)$ 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].

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 $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 with |R| rather than log |R|.

Approximation and BQP-complete Problems

Algorithm: Quantum Simulation
Speedup: 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]. In addition, some work has been done to show that quantum computers can in polynomial time simulate relativistic quantum field theory, in particular lattice gauge theories[107]. 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 generic local Hamiltonians is QMA-complete and therefore probably not in BQP, efficient quantum algorithms have been developed to approximate ground states for certain chemically important Hamiltonians[102].

Algorithm: Jones Polynomial
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 BQP-complete 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 BQP-hard. (See also partition functions.) 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 DQC1-complete. As suggested in [115] and proven in [114], the Witten-Reshitikhin-Turaev invariant of three-manifolds is expressible in terms of the colored Jones polynomial of framed links, which can be efficiently approximated on a quantum computer.

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. A quantum algorithm for approximating partition functions of classical Ising models is given in[101]. 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]. A BQP-completeness 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 Optimization
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 as a polynomial in 1/g, where g is the minimum eigenvalue gap between the ground state and the first excited state. Adiabatic quantum computation was first proposed by Farhi et al. as a method for solving NP-complete combinatorial optimization problems[96]. Despite much effort, the scaling of the eigenvalue gap, and hence the asymptotic runtime of this class of adiabatic quantum algorithms remains unknown. It is known however, that adiabatic quantum computation is equally powerful as the standard quantum circuit model. That is, each can simulate the other with polynomial overhead[97]. Furthermore, adiabatic quantum computers can perform a process somewhat analogous to Grover search in $O(\sqrt{N})$ time[98]. See also quantum simulation, as some quantum simulation algorithms use adiabatic state preparation.

Algorithm: Zeta Functions
Speedup: Superpolynomial
Description: As shown by Kedlaya[64], quantum computers can determine the zeta function of a genus g curve over a finite field $\mathbb{F}_q$ in time polynomial in g and log(q). No polynomial time classical algorithm for this problem is known. More speculatively, van Dam has conjectured that due to a connection between the zeros of 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]. Some evidence supporting this conjecture is given in [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^{\vert c\vert} y^{n-\vert c\vert}$ , where $\vert c\vert$ 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^{\vert c\vert} y^{n-\vert c\vert}$ . 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^{\vert c\vert} y^{n-\vert c\vert}$ . 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 $\vert S(A,\mathrm{lwtr}(A),k,l)\vert \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 BQP-complete, 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 $\vert\pi_{t+1} - \pi_t\vert < \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

. Let $\delta = \min_i \delta_i$ . The run time of this classical algorithm is proportional to $1/\delta$ . Building upon results of Szegedy[85], Somma et al. have shown[84] 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 PromiseBQP-complete. 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 BQP-complete[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\th$ diagonal matrix element of

. The approximation is additive to within $b^m \epsilon$ , where b is a given upper bound on $\Vert A \Vert$ and $\epsilon$ is of order 1/polylog(N). As shown by Janzing and Wocjan, this problem is PromiseBQP-complete, as is the corresponding problem for off-diagonal matrix elements[60]. Thus, quantum computers can solve it in polynomial time, but classical computers probably cannot.

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

, whereas the best known classical algorithm for matrix multiplication runs in time $O(n^{2.376})$ . 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].

References

1: Daniel S. Abrams and Seth Lloyd.
Simulation of many-body Fermi systems on a universal quantum computer.
Physical Review Letters, 79(13):2586-2589, 1997.
arXiv:quant-ph/9703054.
2: Dorit Aharonov and Itai Arad.
The BQP-hardness of approximating the Jones polynomial.
arXiv:quant-ph/0605181, 2006.
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:quant-ph/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:quant-ph/0511096.
5: Dorit Aharonov and Amnon Ta-Shma.
Adiabatic quantum state generation and statistical zero knowledge.
In Proceedings of the 35th ACM Symposium on Theory of Computing, 2003.
arXiv:quant-ph/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:210-239, 2007.
arXiv:quant-ph/0311001.
8: Andris Ambainis, Andrew M. Childs, Ben W.Reichardt, Robert Špalek, and Shengyu Zheng.
Every AND-OR 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 363-372, 2007.
arXiv:quant-ph/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 469-478, 2005.
arXiv:quant-ph/0504083.
10: Michael Ben-Or and Avinatan Hassidim.
Quantum search in an ordered list via adaptive learning.
arXiv:quant-ph/0703231, 2007.
11: Ethan Bernstein and Umesh Vazirani.
Quantum complexity theory.
Proceedings of the 25th ACM Symposium on the Theory of Computing, pages 11-20, 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):359-371, 2007.
arXiv:quant-ph/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 140-150, 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 424-437. Springer-Verlag, 1995.
15: M. Boyer, G. Brassard, P. Høyer, and A. Tapp.
Tight bounds on quantum searching.
Fortschritte der Physik, 46:493-505, 1998.
16: G. Brassard, P. Høyer, and A. Tapp.
Quantum counting.
arXiv:quant-ph/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:quant-ph/0005055.
18: Gilles Brassard, Peter Høyer, and Alain Tapp.
Quantum algorithm for the collision problem.
ACM SIGACT News, 28:14-19, 1997.
arXiv:quant-ph/9705002.
19: Harry Buhrman and Robert Špalek.
Quantum verification of matrix products.
In Proceedings of the 17th ACM-SIAM Symposium on Discrete Algorithms, pages 880-889, 2006.
arXiv:quant-ph/0409035.
20: David Bulger.
Quantum basin hopping with gradient-based local optimisation.
arXiv:quant-ph/0507193, 2005.
21: Harry Burhrman, Christoph Dürr, Mark Heiligman, Peter Høyer, Frederic Magniez, Miklos Santha, and Ronald de Wolf.
Quantum algorithms for element distinctness.
In Proceedings of the 16th IEEE Annual Conference on Computational Complexity, pages 131-137, 2001.
arXiv:quant-ph/0007016.
22: Dong Pyo Chi, Jeong San Kim, and Soojoon Lee.
Notes on the hidden subgroup problem on some semi-direct product groups.
arXiv:quant-ph/0604172, 2006.
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 395-404, 2007.
arXiv:0705.2784.
24: Andrew Childs and Troy Lee.
Optimal quantum adversary lower bounds for ordered search.
arXiv:0708.3396, 2007.
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 59-68, 2003.
arXiv:quant-ph/0209131.
27: Andrew M. Childs, Richard Cleve, Stephen P. Jordan, and David Yeung.
Discrete-query quantum algorithm for NAND trees.
arXiv:quant-ph/0702160, 2007.
28: Andrew M. Childs and Wim van Dam.
Quantum algorithm for a generalized hidden shift problem.
In Proceedings of the 18th ACM-SIAM Symposium on Discrete Algorithms, pages 1225-1232, 2007.
arXiv:quant-ph/0507190.
29: Richard Cleve, Dmitry Gavinsky, and David L. Yeung.
Quantum algorithms for evaluating MIN-MAX trees.
arXiv:0710.5794, 2007.
30: J. Niel de Beaudrap, Richard Cleve, and John Watrous.
Sharp quantum versus classical query complexity separations.
Algorithmica, 34(4):449-461, 2002.
arXiv:quant-ph/0011065v2.
31: Thomas Decker, Jan Draisma, and Pawel Wocjan.
Quantum algorithm for identifying hidden polynomial function graphs.
arXiv:0706.1219, 2007.
32: David Deutsch.
Quantum theory, the Church-Turing principle, and the universal quantum computer.
Proceedings of the Royal Society of London Series A, 400:97-117, 1985.
33: David Deutsch and Richard Josza.
Rapid solution of problems by quantum computation.
Proceedings of the Royal Society of London Series A, 493:553-558, 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):1310-1328, 2006.
arXiv:quant-ph/0401091.
35: Christoph Dürr and Peter Høyer.
A quantum algorithm for finding the minimum.
arXiv:quant-ph/9607014, 1996.
36: Christoph Dürr, Mehdi Mhalla, and Yaohui Lei.
Quantum query complexity of graph connectivity.
arXiv:quant-ph/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):43-48, 2004.
arXiv:quant-ph/0401083.
38: Edward Farhi, Jeffrey Goldstone, and Sam Gutmann.
A quantum algorithm for the Hamiltonian NAND tree.
Theory of Computing 4:169-190, 2008.
arXiv:quant-ph/0702144.
39: Edward Farhi, Jeffrey Goldstone, Sam Gutmann, and Michael Sipser.
Invariant quantum algorithms for insertion into an ordered list.
arXiv:quant-ph/9901059, 1999.
40: Richard P. Feynman.
Simulating physics with computers.
International Journal of Theoretical Physics, 21(6/7):467-488, 1982.
41: Michael Freedman, Alexei Kitaev, and Zhenghan Wang.
Simulation of topological field theories by quantum computers.
Communications in Mathematical Physics, 227:587-603, 2002.
42: Michael Freedman, Michael Larsen, and Zhenghan Wang.
A modular functor which is universal for quantum computation.
arXiv:quant-ph/0001108, 2000.
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 1-9, 2003.
arXiv:quant-ph/0211091.
44: D. Gavinsky.
Quantum solution to the hidden subgroup problem for poly-near-Hamiltonian-groups.
Quantum Information and Computation, 4:229-235, 2004.
45: Joseph Geraci.
A BQP-complete problem related to the Ising model partition function via a new connection between quantum circuits and graphs.
arXiv:0801.4833, 2008.
46: Joseph Geraci and Frank Van Bussel.
A note on cyclotomic cosets, an algorithm for finding coset representatives and size, and a theorem on the quantum evaluation of weight enumerators for a certain class of cyclic codes.
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.
arXiv:quant-ph/0703023, 2007.
48: Lov K. Grover.
Quantum mechanics helps in searching for a needle in a haystack.
Physical Review Letters, 79(2):325-328, 1997.
arXiv:quant-ph/9605043.
49: Sean Hallgren.
Polynomial-time 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 Ta-Shma.
Normal subgroup reconstruction and quantum computation using group representations.
SIAM Journal on Computing, 32(4):916-934, 2003.
52: Mark Heiligman.
Quantum algorithms for lowest weight paths and spanning trees in complete graphs.
arXiv:quant-ph/0303131, 2003.
53: Yoshifumi Inui and Francois Le Gall.
Efficient quantum algorithms for the hidden subgroup problem over a class of semi-direct product groups.
Quantum Information and Computation, 7(5/6):559-570, 2007).
arXiv:quant-ph/0412033.
54: Yuki Kelly Itakura.
Quantum algorithm for commutativity testing of a matrix set.
Master's thesis, University of Waterloo, 2005.
arXiv:quant-ph/0509206.
55: Gábor Ivanyos, Frederic Magniez, and Miklos Santha.
Efficient quantum algorithms for some instances of the non-abelian hidden subgroup problem.
In Proceedings of the 13th ACM Symposium on Parallel Algorithms and Architectures, pages 263-270, 2001.
arXiv:quant-ph/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:quant-ph/0701235.
57: Gábor Ivanyos, Luc Sanselme, and Miklos Santha.
An efficient quantum algorithm for the hidden subgroup problem in nil-2 groups.
arXiv:0707.1260, 2007.
58: Dominik Janzing and Pawel Wocjan.
BQP-complete problems concerning mixing properties of classical random walks on sparse graphs.
arXiv:quant-ph/0610235, 2006.
59: Dominik Janzing and Pawel Wocjan.
A promiseBQP-complete string rewriting problem.
arXiv:0705.1180, 2007.
60: Dominik Janzing and Pawel Wocjan.
A simple promiseBQP-complete matrix problem.
Theory of Computing, 3:61-79, 2007.
arXiv:quant-ph/0606229.
61: Stephen P. Jordan.
Fast quantum algorithm for numerical gradient estimation.
Physical Review Letters, 95:050501, 2005.
arXiv:quant-ph/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 Aspuru-Guzik.
Quantum algorithms for the simulation of chemical dynamics.
arXiv:0801.2986, 2008.
64: Kiran S. Kedlaya.
Quantum computation of zeta functions of curves.
Computational Complexity, 15:1-19, 2006.
arXiv:math/0411623.
65: E. Knill and R. Laflamme.
Quantum computation and quadratically signed weight enumerators.
Information Processing Letters, 79(4):173-179, 2001.
arXiv:quant-ph/9909094.
66: Greg Kuperberg.
A subexponential-time quantum algorithm for the dihedral hidden subgroup problem.
arXiv:quant-ph/0302112, 2003.
67: Daniel A. Lidar.
On the quantum computational complexity of the Ising spin glass partition function and of knot invariants.
New Journal of Physics 6, 167 (2004).
arXiv:quant-ph/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):2429-2438, 1999.
arXiv:quant-ph/9807009.
69: Chris Lomont.
The hidden subgroup problem - review and open problems.
arXiv:quant-ph/0411037, 2004.
70: Frederic Magniez, Miklos Santha, and Mario Szegedy.
Quantum algorithms for the triangle problem.
SIAM Journal on Computing, 37(2):413-424, 2007.
arXiv:quant-ph/0310134.
71: Carlos Magno, M. Cosme, and Renato Portugal.
Quantum algorithm for the hidden subgroup problem on a class of semidirect product groups.
arXiv:quant-ph/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 ACM-SIAM Symposium on Discrete Algorithms, pages 1113-1122, 2004.
arXiv:quant-ph/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 90-100, 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:quant-ph/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:2-16, 2001.
arXiv:quant-ph/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:quant-ph/0406151, 2004.
80: Ben Reichardt and Robert Špalek.
Span-program-based quantum algorithm for evaluating formulas.
arXiv:0710.2630, 2007.
81: Martin Roetteler and Thomas Beth.
Polynomial-time solution to the hidden subgroup problem for a class of non-abelian groups.
arXiv:quant-ph/9812070, 1998.
82: Peter W. Shor.
Polynomial-time algorithms for prime factorization and discrete logarithms on a quantum computer.
SIAM Journal on Computing, 26(5):1484-1509, 2005.
arXiv:quant-ph/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):681-714, 2008.
arXiv:0707.2831.
84: R. D. Somma, S. Boixo, and H. Barnum.
Quantum simulated annealing.
arXiv:0712.1008, 2007.
85: M. Szegedy.
Quantum speed-up of Markov chain based algorithms.
In Proceedings of the 45th IEEE Symposium on Foundations of Computer Science, page 32, 2004.
(see also arXiv:quant-ph/0401053).
86: Wim van Dam.
Quantum algorithms for weighing matrices and quadratic residues.
Algorithmica, 34(4):413-428, 2002.
arXiv:quant-ph/0008059.
87: Wim van Dam.
Quantum computing and zeros of zeta functions.
arXiv:quant-ph/0405081, 2004.
88: Wim van Dam and Sean Hallgren.
Efficient quantum algorithms for shifted quadratic character problems.
arXiv:quant-ph/0011067, 2000.
89: Wim van Dam, Sean Hallgren, and Lawrence Ip.
Quantum algorithms for some hidden shift problems.
SIAM Journal on Computing, 36(3):763-778, 2006.
arXiv:quant-h/0211140.
90: Wim van Dam and Gadiel Seroussi.
Efficient quantum algorithms for estimating Gauss sums.
arXiv:quant-ph/0207131, 2002.
91: John Watrous.
Quantum algorithms for solvable groups.
In Proceedings of the 33rd ACM Symposium on Theory of Computing, pages 60-67, 2001.
arXiv:quant-ph/0011023.
92: Stephen Wiesner.
Simulations of many-body quantum systems by a quantum computer.
arXiv:quant-ph/9603028, 1996.
93: Pawel Wocjan and Jon Yard.
The Jones polynomial: quantum algorithms and applications in quantum complexity theory.
arXiv:quant-ph/0603069, 2006.
94: Andrew Yao.
On computing the minima of quadratic forms.
In Proceedings of the 7th ACM Symposium on Theory of Computing, pages 23-26, 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:quant-ph/9603026.
96: Edward Farhi, Jeffrey Goldstone, Sam Gutmann, and Michael Sipser.
Quantum computation by adiabatic evolution.
arXiv:quant-ph/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):166-194, 2007.
arXiv:quant-ph/0405098
98: Jeremie Roland and Nicolas J. Serf
Quantum search by local adiabatic evolution.
Physical Review A, 65(4):042308, 2002.
arXiv:quant-ph/0107015
99: L.-A. Wu, M.S. Byrd, and D. A. Lidar
Polynomial-Time Simulation of Pairing Models on a Quantum Computer.
Physical Review Letters, 89(6):057904, 2002.
arXiv:quant-ph/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:quant-ph/9807027 and arXiv:quant-ph/0010077
101: Daniel A. Lidar and Ofer Biham
Simulating Ising spin glasses on a quantum computer.
Physical Review E, 56(3):3661, 1997.
arXiv:quant-ph/9611038
102: Alan Aspuru-Guzik, Anthony D. Dutoi, Peter J. Love, and Martin Head-Gordon
Simulated Quantum Computation of Molecular Energies.
Science, 309(5741):1704-1707, 2005. arXiv:quant-ph/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:quant-ph/0608161
104: Aram W. Harrow, Avinatan Hassidim, and Seth Lloyd
Quantum algorithm for solving linear systems of equations.
arXiv:0811.3171, 2008.
105: Martin Roetteler
Quantum algorithms for highly non-linear Boolean functions.
arXiv:0811.3208, 2008.
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:quant-ph/0510027.
108: D. Simon
On the Power of Quantum Computation.
In Proceedings of the 35th Symposium on Foundations of Computer Science, pg. 116-123, 1994.
109: John Proos and Christof Zalka
Shor's discrete logarithm quantum algorithm for elliptic curves.
Quantum Information and Computation 3 (No. 4) (2003) pp.317-344
arXiv:quant-ph/0301141.
110: Yi-Kai Liu
Quantum algorithms using the curvelet transform.
arXiv:0810.4968, 2008.
111: Wim van Dam and Igor Shparlinski
Classical and quantum algorithms for exponential congruences.
arXiv:0804.1109, 2008.
112: Itai Arad and Zeph Landau
Quantum computation and the evaluation of tensor networks.
arXiv:0805.0040, 2008.
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.
arXiv:0805.1214, 2008.
114: Silvano Garnerone, Annalisa Marzuoli, and Mario Rasetti
Efficient quantum processing of 3-manifold topological invariants.
arXiv:quant-ph/0703037, 2007.
115: Louis H. Kauffman and Samuel J. Lomonaco Jr.
q-deformed spin networks, knot polynomials and anyonic topological quantum computation.
Journal of Knot Theory, Vol. 16, No. 3, pg. 267-332. (2007)
arXiv:quant-ph/0606114.
116: Arthur Schmidt and Ulrich Vollmer
Polynomial time quantum algorithm for the computation of the unit group of a number field.
Proceedings of the 37th Symposium on the Theory of Computing, pg. 475-480, 2005.
117: Sergey Bravyi, Aram Harrow, and Avinatan Hassidim
Quantum algorithms for testing properties of distributions.
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
119: V. Arvind, Bireswar Das, and Partha Mukhopadhyay
The complexity of black-box ring problems
Proceedings of COCCOON 2006, pg 126-145.
120: V. Arvind and Partha Mukhopadhyay
Quantum query complexity of multilinear identity testing
Proceedings of STACS 2009, pg. 87-98.
121: David Poulin and Pawel Wocjan
Thermalizing quantum systems and evaluating partition functions with a quantum computer
arXiv:0905.2199
122: Pawel Wocjan, Chen-Fu Chiang, Anura Abeyesinghe, and Daniel Nagaj
Quantum speed-up for approximating partition functions
arXiv:0811.0596
123: Ashley Montanaro
Quantum search with advice
arXiv:0908.3066
124: Laszlo Babai, Robert Beals, and Akos Seress
Polynomial-time theory of matrix groups
Proceedings of STOC 2009, pg. 55-64.

Last updated September 2009.
Back to Stephen Jordan's homepage.