The quantum query complexity of approximating the median and related statistics

Subscribe (Full Service)


	Search: The ACM Digital Library The Guide

	Feedback

The quantum query complexity of approximating the median and related statistics

Full text

Pdf (825 KB)

Source

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

Atlanta, Georgia, United States

Pages: 384 - 393

Year of Publication: 1999

ISBN:1-58113-067-8

Authors

Ashwin Nayak	Computer Science Division, UC Berkeley, Berkeley, CA
Felix Wu	Computer Science Division, UC Berkeley, Berkeley, CA

Sponsor

SIGACT: ACM Special Interest Group on Algorithms and Computation Theory

Publisher

ACM New York, NY, USA

Bibliometrics

Downloads (6 Weeks): 2, Downloads (12 Months): 27, Citation Count: 27

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/301250.301349 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	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
	2	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]
	3	M. Blum, R.W. Floyd, V. Prat~,, R.L. Rivest and R.E. Tarjan. Time bounds for selection. Journal oj' Computer and System Sciences 7, 1973, pp. 448-461.
	4	M. Boyer, G. Brassard, P. H0yer and A. Tapp. Tighf. bounds on quantum searching. Forschritte Der Physik 4/5, 1998, pp. 493-505.
	5	Gilles Brassard , Peter Høyer , Alain Tapp, Quantum Counting, Proceedings of the 25th International Colloquium on Automata, Languages and Programming, p.820-831, July 13-17, 1998
	6	G. Brassard, P. Helyer, M. Mosca and A. Tapp. Quantum amplitude amplification and estimation. Manuscript, 1998.
	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	C. D'tirr and P. H0yer. A quantum algorithm for finding the minimum. Quantum Physics e-Print archive, http://xxx, lanl. gov/abs/quant-ph/9607014, 1996.
	9	E. Farhi, J. Goldstone, S. Gutmann and M. Sipser. A limit on the speed of quantum computation in determining parity. Quantum Physics e-Print archive, http://xxx, lanl. gov/abs/quant-1~h/9802045, 1998.
	10	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]
	11	L.K. Grover. A fast quantum mechanical algorit~hm for estimating the median. Quantum Physics e- Print archive, http://xxx.lanl.gov/abs/quant-ph/ 9607024, 1996.
	12	Lov K. Grover, A framework for fast quantum mechanical algorithms, Proceedings of the thirtieth annual ACM symposium on Theory of computing, p.53-62, May 24-26, 1998, Dallas, Texas, United States [doi>10.1145/276698.276712]
	13	Marvin L. Minsky , Seymour A. Papert, Perceptrons: expanded edition, MIT Press, Cambridge, MA, 1988
	14	M. Mosca. Quantum searching, counting and amplitude amplification by eigenvector analysis. Proceedings oj~ the Workshop on Randomized Algorithms, Mathematical Foundations of Computer Science, 1998.
	15	Ramamohan Paturi, On the degree of polynomials that approximate symmetric Boolean functions (preliminary version), Proceedings of the twenty-fourth annual ACM symposium on Theory of computing, p.468-474, May 04-06, 1992, Victoria, British Columbia, Canada [doi>10.1145/129712.129758]
	16	P.P. Petrushev and V.A. Popov. Rational approximation of real functions. Cambridge University Press, 1987.
	17	T.J. Rivlin. The Chebyshev polynomials. John Wiley and Sons, 1974.
	18	U. Vazirarfi. Personal communication, 1997.

CITED BY 27

	Stefan Heinrich, Quantum integration in Sobolev classes, Journal of Complexity, v.19 n.1, p.19-42, February 2003
	Ziv Bar-Yossef , Ravi Kumar , D. Sivakumar, Sampling algorithms: lower bounds and applications, Proceedings of the thirty-third annual ACM symposium on Theory of computing, p.266-275, July 2001, Hersonissos, Greece
	Stefan Heinrich , Erich Novak, On a problem in quantum summation, Journal of Complexity, v.19 n.1, p.1-18, February 2003
	Harry Buhrman , Ronald de Wolf, Complexity measures and decision tree complexity: a survey, Theoretical Computer Science, v.288 n.1, p.21-43, 9 October 2002
	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
	Andris Ambainis, Quantum lower bounds by quantum arguments, Journal of Computer and System Sciences, v.64 n.4, p.750-767, June 2002
	Arvid J. Bessen, The power of various real-valued quantum queries, Journal of Complexity, v.20 n.5, p.699-712, October 2004
	Andris Ambainis, Quantum lower bounds by quantum arguments, Proceedings of the thirty-second annual ACM symposium on Theory of computing, p.636-643, May 21-23, 2000, Portland, Oregon, United States
	S. Heinrich, Quantum summation with an application to integration, Journal of Complexity, v.18 n.1, p.1-50, March 2002
	Stefan Heinrich, Quantum approximation I. Embeddings of finite-dimensional Lp spaces, Journal of Complexity, v.20 n.1, p.5-26, February 2004
	A. Ambainis, Quantum search algorithms, ACM SIGACT News, v.35 n.2, June 2004
	Marek Kwas , Henryk Woźniakowski, Sharp error bounds on quantum Boolean summation in various settings, Journal of Complexity, v.20 n.5, p.669-698, October 2004
	Bolesław Kacewicz, Randomized and quantum algorithms yield a speed-up for initial-value problems, Journal of Complexity, v.20 n.6, p.821-834, December 2004
	A. Papageorgiou, Average case quantum lower bounds for computing the Boolean mean, Journal of Complexity, v.20 n.5, p.713-731, October 2004
	Stefan Heinrich, From Monte Carlo to quantum computation, Mathematics and Computers in Simulation, v.62 n.3-6, p.219-230, 3 March 2003
	Bolesław Kacewicz, Improved bounds on the randomized and quantum complexity of initial-value problems, Journal of Complexity, v.21 n.5, p.740-756, October 2005
	Andris Ambainis, Polynomial degree vs. quantum query complexity, Journal of Computer and System Sciences, v.72 n.2, p.220-238, March 2006
	Arvid J. Bessen, A lower bound for the Sturm-Liouville eigenvalue problem on a quantum computer, Journal of Complexity, v.22 n.5, p.660-675, October 2006
	Shengyu Zhang, On the power of Ambainis lower bounds, Theoretical Computer Science, v.339 n.2, p.241-256, 12 June 2005
	Esma Aïmeur , Gilles Brassard , Sébastien Gambs, Quantum clustering algorithms, Proceedings of the 24th international conference on Machine learning, p.1-8, June 20-24, 2007, Corvalis, Oregon
	A. Papageorgiou , H. Woźniakowski, The Sturm-Liouville Eigenvalue Problem and NP-Complete Problems in the Quantum Setting with Queries, Quantum Information Processing, v.6 n.2, p.101-120, April 2007
	A. Papageorgiou, On the complexity of the multivariate Sturm--Liouville eigenvalue problem, Journal of Complexity, v.23 n.4-6, p.802-827, August, 2007
	H. Woźniakowski, The Quantum Setting with Randomized Queries for Continuous Problems, Quantum Information Processing, v.5 n.2, p.83-130, April 2006
	Maciej Goćwin, On the Complexity of Searching for a Maximum of a Function on a Quantum Computer, Quantum Information Processing, v.5 n.1, p.31-41, February 2006
	A. Papageorgiou , H. Woźniakowski, Classical and Quantum Complexity of the Sturm--Liouville Eigenvalue Problem, Quantum Information Processing, v.4 n.2, p.87-127, June 2005
	Stefan Heinrich, Quantum lower bounds by entropy numbers, Journal of Complexity, v.23 n.4-6, p.793-801, August, 2007
	Mark W. Coffey , Zachary Prezkuta, A Quantum Algorithm for Finding the Modal Value, Quantum Information Processing, v.7 n.1, p.51-54, February 2008