Quantum lower bounds by quantum arguments

Subscribe (Full Service)


	Search: The ACM Digital Library The Guide

	Feedback

Quantum lower bounds by quantum arguments

Full text

Pdf (713 KB)

Source

Annual ACM Symposium on Theory of Computing archive
Proceedings of the thirty-second annual ACM symposium on Theory of computing table of contents

Portland, Oregon, United States

Pages: 636 - 643

Year of Publication: 2000

ISBN:1-58113-184-4

Author

Andris Ambainis

Computer Science Division, University of California, Berkeley, CA

Sponsor

SIGACT: ACM Special Interest Group on Algorithms and Computation Theory

Publisher

ACM New York, NY, USA

Bibliometrics

Downloads (6 Weeks): 5, Downloads (12 Months): 43, Citation Count: 8

Additional Information:

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/335305.335394 What is a DOI?

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	Andris Ambainis, A Better Lower Bound for Quantum Algorithms Searching an Ordered List, Proceedings of the 40th Annual Symposium on Foundations of Computer Science, p.352, October 17-18, 1999
	2	A. Ambainis , L. J. Schulman , A. Ta-Shma , U. Vazirani , A. Wigderson, The Quantum Communication Complexity of Sampling, Proceedings of the 39th Annual Symposium on Foundations of Computer Science, p.342, November 08-11, 1998
	3	Robert Beals , Harry Buhrman , Richard Cleve , Michele Mosca , Ronald de Wolf, Quantum Lower Bounds by Polynomials, Proceedings of the 39th Annual Symposium on Foundations of Computer Science, p.352, November 08-11, 1998
	4	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]
	5	Gilles Brassard , Peter Høyer , Alain Tapp, Quantum cryptanalysis of hash and claw-free functions, ACM SIGACT News, v.28 n.2, p.14-19, June 1997 [doi>10.1145/261342.261346]
	6	Harry Buhrman , Richard Cleve , Ronald de Wolf , Christof Zalka, Bounds for Small-Error and Zero-Error Quantum Algorithms, Proceedings of the 40th Annual Symposium on Foundations of Computer Science, p.358, October 17-18, 1999
	7	Harry Buhrman , Richard Cleve , Avi Wigderson, Quantum vs. classical communication and computation, Proceedings of the thirtieth annual ACM symposium on Theory of computing, p.63-68, May 24-26, 1998, Dallas, Texas, United States [doi>10.1145/276698.276713]
	8	H. Buhrman, R. de Wolf. Communication complexity lower bounds by polynomials, cs. CC/9910010.
	9	Lov K. Grover, A fast quantum mechanical algorithm for database search, Proceedings of the twenty-eighth annual ACM symposium on Theory of computing, p.212-219, May 22-24, 1996, Philadelphia, Pennsylvania, United States [doi>10.1145/237814.237866]
	10	L. Grover. How fast can a quantum computer search? quant-ph/9809029.
	11	A. Yu. Kitaev. Quantum measurements and the Abelian stabilizer problem, quant-ph/9511026.
	12	B. Kalyanasundaram, G. Schnitger. The probabilistic communication complexity of set intersection. Proceedings of Structures'87, pages 41-49, 1987.
	13	Ashwin Nayak , Felix Wu, The quantum query complexity of approximating the median and related statistics, Proceedings of the thirty-first annual ACM symposium on Theory of computing, p.384-393, May 01-04, 1999, Atlanta, Georgia, United States [doi>10.1145/301250.301349]
	14	Noam Nisan, CREW PRAMs and decision trees, SIAM Journal on Computing, v.20 n.6, p.999-1007, Dec. 1991 [doi>10.1137/0220062]
	15	A. A. Razborov, On the distributional complexity of disjointness, Theoretical Computer Science, v.106 n.2, p.385-390, Dec. 1992 [doi>10.1016/0304-3975(92)90260-M]
	16	Y. Shi. Lower bounds of quantum black-box complexity and degree of approximation polynomials by influence of Boolean variables, quant-ph/9904107.
	17	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]
	18	U. Vazirani. On the power of quantum computation. Philosophical Transactions of the Royal Society of London, Series A: Mathematical and Physical Sciences, 356:1759-1768, August 1998.

CITED BY 8

	Robert Beals , Harry Buhrman , Richard Cleve , Michele Mosca , Ronald de Wolf, Quantum lower bounds by polynomials, Journal of the ACM (JACM), v.48 n.4, p.778-797, July 2001
	Hartmut Klauck, Quantum time-space tradeoffs for sorting, Proceedings of the thirty-fifth annual ACM symposium on Theory of computing, June 09-11, 2003, San Diego, CA, USA
	Andrew Chi-Chih Yao, Graph entropy and quantum sorting problems, Proceedings of the thirty-sixth annual ACM symposium on Theory of computing, June 13-16, 2004, Chicago, IL, USA
	Howard Barnum , Michael Saks, A lower bound on the quantum query complexity of read-once functions, Journal of Computer and System Sciences, v.69 n.2, p.244-258, September 2004
	Yaoyun Shi, Quantum and classical tradeoffs, Theoretical Computer Science, v.344 n.2-3, p.335-345, 17 November 2005
	Scott Aaronson , Yaoyun Shi, Quantum lower bounds for the collision and the element distinctness problems, Journal of the ACM (JACM), v.51 n.4, p.595-605, July 2004
	Scott Aaronson, Quantum lower bound for the collision problem, Proceedings of the thiry-fourth annual ACM symposium on Theory of computing, May 19-21, 2002, Montreal, Quebec, Canada
	Andris Ambainis , Robert Špalek , Ronald de Wolf, A new quantum lower bound method,: with applications to direct product theorems and time-space tradeoffs, Proceedings of the thirty-eighth annual ACM symposium on Theory of computing, May 21-23, 2006, Seattle, WA, USA