Why haven't more quantum algorithms been found?

Subscribe (Full Service)


	Search: The ACM Digital Library The Guide

	Feedback

Why haven't more quantum algorithms been found?

Full text

Pdf (25 KB)

Source

Journal of the ACM (JACM) archive
Volume 50 , Issue 1 (January 2003) table of contents

Pages: 87 - 90

Year of Publication: 2003

ISSN:0004-5411

Author

Peter W. Shor

AT&T Labs---Research, Florham Park, New Jersey

Publisher

ACM New York, NY, USA

Bibliometrics

Downloads (6 Weeks): 7, Downloads (12 Months): 121, Citation Count: 4

Additional Information:

abstract references cited by index terms collaborative colleagues

Tools and Actions:	Request Permissions Review this Article Save this Article to a Binder Display Formats: BibTeX EndNote ACM Ref

DOI Bookmark:	Use this link to bookmark this Article: http://doi.acm.org/10.1145/602382.602408 What is a DOI?

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.

REFERENCES

Note: OCR errors may be found in this Reference List extracted from the full text article. ACM has opted to expose the complete List rather than only correct and linked references.

	1	Charles H. Bennett , Ethan Bernstein , Gilles Brassard , Umesh Vazirani, Strengths and Weaknesses of Quantum Computing, SIAM Journal on Computing, v.26 n.5, p.1510-1523, Oct. 1997 [doi>10.1137/S0097539796300933]
	2	Stephen A. Cook, The complexity of theorem-proving procedures, Proceedings of the third annual ACM symposium on Theory of computing, p.151-158, May 03-05, 1971, Shaker Heights, Ohio, United States [doi>10.1145/800157.805047]
	3	Feynman, R. 1982. Simulating physics with computers. Internat. J. Theoret. Phys. 21, 467--488.
	4	Grover, L. K. 1997. Quantum mechanics helps in searching for a needle in a haystack. Phys. Rev. Lett. 78, 325--328.
	5	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.
	6	Sean Hallgren, Polynomial-time quantum algorithms for Pell's equation and the principal ideal problem, Proceedings of the thiry-fourth annual ACM symposium on Theory of computing, May 19-21, 2002, Montreal, Quebec, Canada [doi>10.1145/509907.510001]
	7	Karp, R. 1972. Reducibility among combinatorial problems. In Complexity of Computer Computations, R. Miller and J. Thatcher, Eds. Plenum, New York, 85--103.
	8	Kitaev, A. Yu. 1996. Quantum measurements and the Abelian stabilizer problem. ECCC Report TR96-003. Los Alamos archive, e-print quant-ph/9511026.
	9	Levin, L. 1973. Universal search problems (in Russian). Prob. Pered. Inf. 9, 3, 265--266.
	10	Peter W. Shor, Polynomial-Time Algorithms for Prime Factorization and Discrete Logarithms on a Quantum Computer, SIAM Journal on Computing, v.26 n.5, p.1484-1509, Oct. 1997 [doi>10.1137/S0097539795293172]
	11	Daniel R. Simon, On the Power of Quantum Computation, SIAM Journal on Computing, v.26 n.5, p.1474-1483, Oct. 1997 [doi>10.1137/S0097539796298637]

CITED BY 4

	Ethan Schuchman , T. N. Vijaykumar, A program transformation and architecture support for quantum uncomputation, ACM SIGOPS Operating Systems Review, v.40 n.5, December 2006
	Sean Hallgren, Polynomial-time quantum algorithms for Pell's equation and the principal ideal problem, Journal of the ACM (JACM), v.54 n.1, p.1-es, March 2007
	Peter W. Shor, Progress in Quantum Algorithms, Quantum Information Processing, v.3 n.1-5, p.5-13, October 2004
	Lian-Ao Wu , Mark S. Byrd, Self-protected quantum algorithms based on quantum state tomography, Quantum Information Processing, v.8 n.1, p.1-12, February 2009