Peter W. Shor
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.
- Bennett, C. H., Bernstein, E., Brassard, G., and Vazirani, U. V. 1997. Strengths and weaknesses of quantum computing. SIAM J. Comput. 26, 1510--1523. Google Scholar
Digital Library
- 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. Google Scholar
- Feynman, R. 1982. Simulating physics with computers. Internat. J. Theoret. Phys. 21, 467--488.Google ScholarCross Ref
- Grover, L. K. 1997. Quantum mechanics helps in searching for a needle in a haystack. Phys. Rev. Lett. 78, 325--328.Google ScholarCross Ref
- Grover, L. K., and Sengupta, A. M. 2002. From coupled pendulums to quantum search. In Mathematics of Quantum Computation, R. K. Brylinski and G. Chen, Eds. Chapman & Hall/CRC, Boca Raton, FL, 119--134.Google Scholar
- Hallgren, S. 2002. Polynomial-time quantum algorithms for Pell's equation and the principal ideal problem. In Proceedings of the 34th Annual ACM Symposium on Theory of Computing. ACM, New York, 653--658. Google Scholar
- Karp, R. 1972. Reducibility among combinatorial problems. In Complexity of Computer Computations, R. Miller and J. Thatcher, Eds. Plenum, New York, 85--103.Google Scholar
- Kitaev, A. Yu. 1996. Quantum measurements and the Abelian stabilizer problem. ECCC Report TR96-003. Los Alamos archive, e-print quant-ph/9511026.Google Scholar
- Levin, L. 1973. Universal search problems (in Russian). Prob. Pered. Inf. 9, 3, 265--266.Google Scholar
- Shor, P. W. 1997. Polynomial-time algorithms for prime factorization and discrete logarithms on a quantum computer. SIAM J. Comput. 26, 1484--1509. Google ScholarDigital Library
- Simon, D. R. 1997. On the power of quantum computation. SIAM J. Comput. 26, 1474--1483. Google ScholarDigital Library
Index Terms
- Why haven't more quantum algorithms been found?
Recommendations
Quantum correlation swapping
Quantum correlations (QCs), including quantum entanglement and those different, are important quantum resources and have attracted much attention recently. Quantum entanglement swapping as a kernel technique has already been applied to quantum repeaters ...
Photonic scheme of quantum phase estimation for quantum algorithms via quantum dots
AbstractVarious quantum algorithms depend on quantum phase estimation (QPE) as basic blocks or main subroutines to leverage superposition and entanglement during quantum computations. The QPE algorithm estimates the unknown phase of an eigenvalue ...
Schmidt Decomposition for Quantum Entanglement in Quantum Algorithms
We study quantum entanglement by Schmidt decomposition for some typical quantum algorithms. In the Shor's exponentially fast algorithm the quantum entanglement holds almost maximal, which is a major factor that a classical computer is not adequate to ...
Comments