Â¥Ö÷

Why Haven't More Quantum Algorithms Been Found? (zz) ¡¾ ÒÔÏÂÎÄ×ÖתÔØ×Ô Ð¡°ÙºÏBBS Algorithm ÌÖÂÛÇø ¡¿ ¡¾ Ô­ÎÄÓÉ starfish@lilybbs Ëù·¢±í ¡¿ Why Haven't More Quantum Algorithms Been Found? PETER W. SHOR AT&T Labs---Research, Florham Park, New Jersey Abstract. I examine the question of why so few classes of quantum algorithms have been discovered.  I give two possible explanations for this, and some thoughts about what lines of research might lead to the discovery of more quantum algorithms. My discovery of the quantum factoring algorithm in 1994 caused great excitement among theoretical computer scientists. Quantum computers provided a completely new paradigm for the theory of computation, and this was the first time it had been shown that quantum computation could efficiently solve a problem that had already been established as important in this field. Many people expected a succession of other interesting algorithms to follow. The reality has been disappointing, especially compared with the progress of the rest of the field of quantum information processing. Experimental physicists have been proposing and exploring possible physical implementations of quantum computers at a pace far beyond what anybody but the most optimistic researchers originally expected. Quantum cryptography is coming of age, with several theoretical proofs of its security recently discovered, and with commercial quantum cryptography systems expected in the next year or so. The fields of quantum information theory and quantum complexity have been expanding dramatically, with a number of new interesting and important theoretical results. Meanwhile, the development of algorithms has lagged behind, with barely any significant new algorithms having been discovered in the last five years. So far, all the quantum algorithms known to offer substantial speedup over classical algorithms for the same problems fall into one of three classes. The first class uses the Fourier transform to find periodicity. This class contains the factoring and discrete logarithm algorithms [Shor 1997], Simon's algorithm [Simon 1997] (the first member of this class to be discovered), and Hallgren's algorithms for Pell's equation and certain other number theory problems [Hallgren 2002]. There is, in fact a different way of looking at the factoring algorithm that, although it yields basically the same algorithm, puts it into a setting that emphasizes spectral methods rather than periodicity [Kitaev 1996], but this approach has not yet yielded any new algorithms. The second class contains Grover's search algorithm, which can perform an exhaustive search of N items in \sqrt{N} time [Grover 1997], and a number of extensions of this algorithm (see Grover and Sengupta [2002]). These extensions all have the general flavor of giving a square root improvement in the speed of optimization or search problems. The third class consists of algorithms for simulating or solving problems in quantum physics. This class contains Feynman's original idea [Feynman 1982] of using quantum computers to speed up simulations of quantum physics. While not many theoretical papers have yet been written on this class of algorithms, it is clear that if quantum computers are ever developed, this class will be extremely useful in practice. Feynman came up with his idea of using quantum computers to simulate quantum physics in 1982, Simon's algorithm and the factoring algorithm were developed in 1993 and 1994, and Grover came up with his original search algorithm in 1995. Since then, there have been further theoretical developments within each of these classes of algorithms, but no new classes of quantum algorithms have been discovered. As the discoverer of the quantum factoring algorithm, one of the questions I am often asked is why there are so few quantum algorithms known that offer speedup over classical algorithms. The answer I usually give is that I don't know, but that I can think of two possible reasons that this might be the case. The first possible reason is that quantum computers operate in a manner so different from classical computers that our techniques for designing algorithms and our intuitions for understanding the process of computation no longer work. The second reason is that there really might be relatively few problems for which quantum computers can offer a substantial speedup over classical computers, and we may have already discovered many or all of the important techniques for constructing quantum algorithms. This article contains an expansion of these thoughts. Both of these explanations address the question of why we haven't seen more speedups from quantum algorithms, and I believe both of these explanations are likely to be true to a greater or lesser extent. It is certainly true that quan tum computers are very difficult to reason about using classical intuition. Physi cists have spent decades developing their intuitions about quantum phenomena, and many of the techniques they use came decades after the original develop ment of quantum mechanics. Computer scientists, on the other hand, have been thinking about quantum mechanics for barely a decade. Any quantum algorithm offering a speedup over classical computation must use interference; this phe nomenon is unknown in classical computer science, and most theoretical com puter scientists are not used to reasoning about it. Thus, it seems quite likely that several new and significant quantum algorithmic techniques have yet to be discovered. On the other hand, much of the research into new quantum computer algorithms has been spent looking for superpolynomial speedups. While these do not occur in Grover's algorithm and its extensions, they can occur in the classes of quantum algorithms that use periodicity finding and that simulate quantum physics.  Superpolynomial speedups cannot arise from problems that have polynomialtime classical algorithms, so researchers have been concentrating on problems that are not in the classical computational class P. The first class of problems not in P that come to mind are the NPcomplete ones. A quantum algorithm solving NPcomplete problems in polynomial time would be a momentous discovery, but I believe that the most likely scenario is that this is not possible. It has been proved that there is an oracle, relative to which NPcomplete problems cannot be solved in polynomial time [Bennett et al. 1997], and while there are fewer reasons supporting the belief that quantum computers cannot solve NPcomplete problems than there are supporting the nearly universal belief that classical computers cannot solve them, many researchers are still pessimistic that quantum computers can solve NPcomplete problems. If weassume that NPcompleteproblems are not solvable efficiently on a quantum computer, then in order to achieve a superpolynomial speedup, we must look within the class of problems which are neither NPhard nor in P. There are only a relatively small number of wellstudied problems that are suspected to be in this class. No general theory is known for these problems, and relatively few of them are known to be reducible to each other, so they all must be considered individually. It may be that many of these problems do not indeed have polynomialtime algorithms on quantum computers. People have to date concentrated their efforts on those problems that appear to have structure related to periodicity, thus providing a possible means of attack. These include the problems of graph isomorphism and that of approximating short vectors in a lattice. Neither of these problems has yet yielded to a quan tum attack. Part of the expectations for the discovery of many quantum speedups may be due to analogies with the history of classical computation. After the identification of NPcompleteness [Cook 1971, Karp 1972, Levin 1973], there followed a plethora of papers classifying problems either as polynomial time (giving efficient algorithms) or as NPhard. This may have raised our expectations too high, as the success of this classification effort has now left relatively few wellstudied problems that are not known to be in one of these two classes. By searching for superpolynomial speed-ups, we may also be attempting too difficult a task. By contrast with researchers in quantum computing, researchers in classical algorithms spend their time not only trying to put more problems into the class P, but also trying to discover faster algorithms for problems that are already known to be in P. By trying to discover new ways of solving problems already known to be in P, researchers have often been able to find new and fruitful techniques, which then can be used to help solve other problems, sometimes including ways of efficiently solving problems not known to be in P. One research area that might be worth exploring is to try to find faster quantum algorithms for problems already known to be classically solvable in polynomial time. This approach is limited to providing polynomial factor speedups.  While this is certainly less exciting than finding superpolynomial speedups, and is also less likely to yield practical results---since quantum computers are likely to be slower than classical computers---it could nevertheless yield new techniques for designing quantum algorithms. At this point, my belief is that any new techniques have the potential to be of great value in further exploration of quantum algorithms, and, if this avenue can help discover such new techniques, it should be pursued. REFERENCES BENNETT, C. H., BERNSTEIN, E., BRASSARD, G., AND VAZIRANI, U. V. 1997. Strengths and weaknesses of quantum computing. SIAM J. Comput. 26, 1510--1523. COOK, S. 1971. The complexity of theorem proving procedures. In Proceedings of the 3rd Annual ACM Symposium on Theory of Computing. ACM, New York, 151--158. FEYNMAN, R. 1982. Simulating physics with computers. Internat. J. Theoret. Phys. 21, 467-- 488. GROVER, L. K. 1997. Quantum mechanics helps in searching for a needle in a haystack. Phys. Rev. Lett. 78, 325--328. GROVER,L .K.,AND SENGUPTA, A. M. 2002. From coupled pendulums to quantum search. In Mathe matics of Quantum Computation, R. K. Brylinski and G. Chen, Eds. Chapman & Hall/CRC, Boca Raton, FL, 119--134. HALLGREN, S. 2002. Polynomialtime quantum algorithms for Pell's equation and the principal ideal problem. In Proceedings of the 34th Annual ACM Symposium on Theory of Computing. ACM, NewYork, 653--658. KARP, R. 1972. Reducibility among combinatorial problems. In Complexity of Computer Computations, R. Miller and J. Thatcher, Eds. Plenum, New York, 85--103. KITAEV,A .YU. 1996. Quantum measurements and the Abelian stabilizer problem. ECCC Report TR96003. Los Alamos archive, eprint quantph/9511026. LEVIN, L. 1973. Universal search problems (in Russian). Prob. Pered. Inf. 9, 3, 265--266. SHOR, P. W. 1997. Polynomialtime algorithms for prime factorization and discrete logarithms on a quantum computer. SIAM J. Comput. 26, 1484--1509. SIMON, D. R. 1997. On the power of quantum computation. SIAM J. Comput. 26, 1474--1483.    Êղؠ  ·ÖÏí   ¶¥(0)

----------------------------------------------
Three passions, simple but overwhelmingly strong, 
have governed my life: the longing for love, the
search for knowledge, and unbearable pity for the
suffering of mankind.
                            - Bertrand Russell