Quantum lower bound for sorting

Preprint English OPEN
Shi, Yaoyun;
  • Subject: Quantum Physics

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 ... View more
  • References (15)
    15 references, page 1 of 2

    [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.

    [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.

    [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.

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

  • Related Organizations (4)
  • Metrics
Share - Bookmark