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
 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.
 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.
 Paul Beame. A general sequential time-space tradeoff for finding unique elements. SIAM J. Comput., 20(2):270-277, 1991.
 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.
 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.
 M. Boyer, G. Brassard, P. Høyer, and A. Tap. Tight bounds on quantum searching. Fortschritte der Physik, 46(4-5), 1998.
 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.
 M.-D. Choi. Tricks or treats with the Hilbert matrix. Amer. Math. Monthly, 90(5):301-312, 1983.
 Christoph Durr and Perter Høyer. A quantum algorithm for finding the minimum. Preliminary version: quant-ph/9607014, 1996.
 Edward Farhi, Jeffrey Goldstone, Sam Gutmann, and Michael Sipser. Invariant quantum algorithms for insertion into an ordered list. Preliminary version: quantph/9901059, 1999.