量子計算相關(guān)論文下載Quantum Algorithms Catalog

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: Factoring Speedup: Superpolynomial Description: Given an nbit integer, find the prime factorization. The quantum algorithm of Peter Shor solves this in time 82,125. The fastest known classical algorithm for integer factorization is the general number field sieve, which is believed to run in time . The best rigorously proven upper bound on the classical complexity of factoring is 252. Shors factoring algorithm breaks RSA publickey encryption and the closely related quantum algorithms for discrete logarithms break the DSA and ECDSA digital signature schemes and the DiffieHellman keyexchange protocol. There are proposed classical publickey cryptosystems not believed to be broken by quantum algorithms, cf. 248. At the core of Shors factoring algorithm is order finding, which can be reduced to the Abelian hidden subgroup problem, which is solved using the quantum Fourier transform. A number of other problems are known to reduce to integer factorization including the membership problem for matrix groups over fields of odd order 253, and certain diophantine problems relevant to the synthesis of quantum circuits 254. Algorithm: Discretelog Speedup: Superpolynomial Description: We are given three nbit numbers a, b, and N, with the promise that 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: Pells Equation Speedup: Superpolynomial Description: Given a positive nonsquare integer d, Pells equation is . For any such d there are infinitely many pairs of integers (x,y) solving this equation. Let be the pair that minimizes . If d is an nbit integer (i.e. ), may in general require exponentially many bits to write down. Thus it is in general impossible to find in polynomial time. Let . uniquely identifies . As shown by Hallgren 49, given a nbit number d, a quantum computer can find 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 . I is a principal ideal if there exists such that . may be exponentially large in d. Therefore cannot in general even be written down in polynomial time. However, uniquely identifies . The task is to determine whether I is principal and if so find 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 Pells 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 is said to be of degree d if the lowest degree polynomial of which is a root has degree d. The set of elements of which are roots of monic polynomials in forms a ring, called the ring of integers of . The set of units (invertible elements) of the ring form a group denoted . As shown by Hallgren 50, and independently by Schmidt and Vollmer 116, for any of fixed degree, a quantum computer can find in polynomial time a set of generators for given a description of . No polynomial time classical algorithm for this problem is known. Hallgren and collaborators subsequently discovered how to achieve polynomial scaling in the degree 213. 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 is said to be of degree d if the lowest degree polynomial of which is a root has degree d. The set of elements of which are roots of monic polynomials in forms a ring, called the ring of integers of . 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 . No polynomial time classical algorithm for this problem is Navigation Algebraic & Number Theoretic Oracular Approximation and Simulation Acknowledgments References Other Surveys For overviews of quantum algorithms I recommend: Nielsen and Chuang Childs Preskill Mosca Childs and van Dam van Dam and Sasaki Bacon and van Dam Loceff Terminology If there exists a positive constant such that the runtime of the best known classical algorithm and the runtime of the quantum algorithm satisfy then I call the speedup superpolynomial. Otherwise I call it polynomial. For a review of the notations see the Wikipedia article. About Author: Stephen Jordan Applied and Computational Mathematics Division, NIST Last updated: July 31, 2015 Date created: April 22, 2011 See also: ITL Quantum Information ()O n3 2 ()O n1/3 O()2n/3+o(1) b =mod Nas d= 1x2y2 (,)x1y1 x + yd0 d 2n(,)x1y1 (,)x1y1 R = log(+)x1y1dR(,)x1y1 R Z d Q()dI = Z d log log Q() OQ()Zx Q()O O Q()O Q() OQ() ZxQ() C(n) Q(n) C = 2( )Q O,.O known. See also Abelian hidden subgroup. Algorithm: Gauss Sums Speedup: Superpolynomial Description: Let be a finite field. The elements other than zero of form a group under multiplication, and the elements of form an (Abelian but not necessarily cyclic) group under addition. We can choose some character of and some character of . The corresponding Gauss sum is the inner product of these characters: 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 . We must find such that . As shown in 111, quantum computers can solve this problem in time whereas the best classical algorithm requires 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 groups 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 . 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 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 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 . Ambainis et al. discovered a quantum algorithm for this problem with runtime 6. Subsequently, Buhrman and palek improved upon this, obtaining a quantum algorithm for this problem with runtime 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 , 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 NP complete, 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 . In 178, a quantum algorithm is given that solves this problem in time , up to polynomial factors. This quantum algorithm works by applying a variant of Ambainiss quantum walk algorithm for elementdistinctness 7to speed up a sophisticated classical algorithm for this problem due to HowgraveGraham and Joux. The fastest known classical algorithm for subsetsum runs in time , up to polynomial factors. Algorithm: Decoding Speedup: Various Description: Classical error correcting codes allow the detection and correction of bitflips by storing data reduntantly. Maximumlikelihood decoding for arbitrary linear codes is NPcomplete in the worst case, but for structured codes or bounded error efficient decoding algorithms are known. Quantum algorithms have been formulated to speed up the decoding of convolutional codes 238 and simplex codes 239. Oracular Algorithms 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 queries. The quantum algorithm of Lov Grover achieves this FqFqF q FqF+ q F q +F+ q (x)(x)x0Fq+ a,b,c,f,g Fqx,y Fqa+ b= cfxgy ()O q3/8 ()O q9/8 Sn An n n O()n2 O()n2.373 O()n7/4 O()n5/3 ,x1xn 2n 20.241n 20.291n (N) O() using queries 48, which is optimal 216. 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, 255, 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 Grovers 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. For further examples of application of Grover search and amplitude amplification see 261, 262 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 , 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 queries, whereas classically 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 Simons algorithm 108, which was the inspiration for Shors 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 Pells 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 , 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 , 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 queries, whereas classically 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, Kuperberg 66 found a time 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. A further improvement in the asymptotic scaling of the required number of qubits is obtained in 218. Algorithm: BernsteinVazirani Speedup: Polynomial Directly, Superpolynomial Recursively Description: We are given an oracle whose input is n bits and whose output is one bit. Given input , the output is , where h is the hidden string of n bits, and 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 recursive versions of this problem, called recursive Fourier sampling, such that quantum computers require exponentially fewer queries than classical computers 11. See 256, 257 for related work on the ubiquity of quantum speedups from generic quantum circuits and 258 for related work on a quantum query speedup for detecting correlations between the an oracle function and the Fourier transform of another. 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 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 related, more recent, pedagogical example is given in 259.) 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 Reichardts spanprogram formalism, it is now known 158 that the quantum query complexity of any formula of O(1) fanin on N variables is . This result culminates from a long line of work 27,8,80,159,160, which O()N , Gg1g2f() = f()g1g2g1 g2 O(log|G|)(|G|) log(|G|) ,g1g2f() = f()g1g2g1g2 O(log(|G|)(|G|) )2O( )logN DN x 0,1nx h 2n ()N n started with the discovery by Farhi et al. 38 that NAND trees on variables can be evaluated on quantum computers in time using a continuoustime quantum walk, whereas classical computers require 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