publication . Preprint . 2000

Quantum lower bound for sorting

Shi, Yaoyun;
Open Access English
  • Published: 21 Sep 2000
We prove that \Omega(n log(n)) comparisons are necessary for any quantum algorithm that sorts n numbers with high success probability and uses only comparisons. If no error is allowed, at least 0.110nlog_2(n) - 0.067n + O(1) comparisons must be made. The previous known lower bound is \Omega(n).
free text keywords: Quantum Physics
Related Organizations
Funded by
NSF| Complexity Studies in Communications and Quantum Computations
  • Funder: National Science Foundation (NSF)
  • Project Code: 9820855
  • Funding stream: Directorate for Computer & Information Science & Engineering | Division of Computing and Communication Foundations
Download from

[3] A. Ambainis. Quantum lower bounds by quantum arguments. In Proceedings of the Thirty-second Annual ACM Symposium on the Theory of Computing, pages 636-643, Portland, Oregon, May 2000. [OpenAIRE]

[4] R. Beals, H. Buhrman, R. Cleve, M. Mosca, and R. de Wolf. Quantum lower bounds by polynomials. In 39th Annual Symposium on Foundations of Computer Science, pages 352-361, Los Alamitos, CA, November 1998. IEEE.

[5] Paul Beame. A general sequential time-space tradeoff for finding unique elements. SIAM J. Comput., 20(2):270-277, 1991.

[6] Charles H. Bennett, Ethan Bernstein, Gilles Brassard, and Umesh Vazirani. Strengths and weaknesses of quantum computing. SIAM Journal on Computing, 26(5):1510- 1523, October 1997.

[7] Allan Borodin, Michael J. Fischer, David G. Kirkpatrick, Nancy A. Lynch, and Martin Tompa. A time-space tradeoff for sorting on nonoblivious machines. J. Comput. System Sci., 22(3):351-364, 1981. Special issue dedicated to Michael Machtey.

[8] M. Boyer, G. Brassard, P. Høyer, and A. Tap. Tight bounds on quantum searching. Fortschritte der Physik, 46(4-5), 1998. [OpenAIRE]

[9] Harry Buhrman, Christoph Durr, Mark Heiligman, Peter Høyer, Frederic Magniez, Miklos Santha, and Ronald de Wolf. Quantum algorithm for element distinctness. Preliminary version: quant-ph/0007016, 2000.

[10] M.-D. Choi. Tricks or treats with the Hilbert matrix. Amer. Math. Monthly, 90(5):301-312, 1983.

[11] Christoph Durr and Perter Høyer. A quantum algorithm for finding the minimum. Preliminary version: quant-ph/9607014, 1996. [OpenAIRE]

[12] Edward Farhi, Jeffrey Goldstone, Sam Gutmann, and Michael Sipser. Invariant quantum algorithms for insertion into an ordered list. Preliminary version: quantph/9901059, 1999. [OpenAIRE]

[13] Dima Grigoriev, Marek Karpinski, Friedhelm Meyer auf der Heide, and Roman Smolensky. A lower bound for randomized algebraic decision trees. In ACM [1], pages 612-619.

[14] Lov K. Grover. A fast quantum mechanical algorithm for database search. In ACM [1], pages 212-219.

[15] P. Høyer and J. Neerbek. Bounds on quantum ordered searching. Preliminary version: quant-ph/0009032, 2000. [OpenAIRE]

[16] Peter W. Shor. Polynomial-time algorithms for prime factorization and discrete logarithms on a quantum computer. SIAM Journal on Computing, 26(5):1484-1509, October 1997.

[17] Andrew Yao. Personal communication, 2000.

Powered by OpenAIRE Open Research Graph
Any information missing or wrong?Report an Issue