Quantum time-space tradeoffs for sorting

ABSTRACT

We investigate the complexity of sorting in the model of sequential quantum circuits. While it is known that in general a quantum algorithm based on comparisons alone cannot outperform classical sorting algorithms by more than a constant factor in time complexity, this is wrong in a space bounded setting. We observe that for all storage bounds n/log ≥ S ≥ log³n, one can devise a quantum algorithm that sorts n numbers (using comparisons only) in time T=O(n^3/2 log^3/2 n/√S). We then show the following lower bound on the time-space tradeoff for sorting n numbers from a polynomial size range in a general sorting algorithm (not necessarily based on comparisons): TS=Ω(n^3/2). Hence for small values of S the upper bound is almost tight. Classically the time-space tradeoff for sorting is TS=Θ(n²).

REFERENCES

• 1: Dorit Aharonov , Alexei Kitaev , Noam Nisan, Quantum circuits with mixed states, Proceedings of the thirtieth annual ACM symposium on Theory of computing, p.20-30, May 24-26, 1998, Dallas, Texas, United States [doi>10.1145/276698.276708]
• 2: 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 [doi>10.1145/335305.335394]
• 3: Paul Beame, A general sequential time-space tradeoff for finding unique elements, SIAM Journal on Computing, v.20 n.2, p.270-277, April 1990 [doi>10.1137/0220017]
• 4: P. Beame , M. Saks , Xiaodong Sun , E. Vee, Super-linear time-space tradeoff lower bounds for randomized computation, Proceedings of the 41st Annual Symposium on Foundations of Computer Science, p.169, November 12-14, 2000
• 5: 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]
• 6: C. H. Bennett, G. Brassard, C. Crepeau, R. Josza, A. Peres, W. Wooters. Teleporting an Unknown Quantum State via Dual Classical and Einstein-Podolsky-Rosen Channels. Phys. Rev. Lett., vol.70, pp. 1895--1899, 1993.
• 7: A. Borodin, S. Cook. A time-space tradeoff for sorting on a general sequential model of computation. SIAM Journal on Computing, vol. 11, pp. 287--297, 1982.
• 8: A. Borodin , F. Fich , F. Meyer auf der Heide , E. Upfal , A. Wigderson, A time-space tradeoff for element distinctness, SIAM Journal on Computing, v.16 n.1, p.97-99, Feb. 1987 [doi>10.1137/0216007]
• 9: Harry Buhrman , Ronald de Wolf , Christoph Dürr , Mark Heiligman , Peter Hyer , Frédéric Magniez , Miklos Santha, Quantum Algorithms for Element Distinctness, Proceedings of the 16th Annual Conference on Computational Complexity, p.131, June 18-21, 2001
• 10: 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 [doi>10.1016/S0304-3975(01)00144-X]
• 11: Thomas H. Cormen , Clifford Stein , Ronald L. Rivest , Charles E. Leiserson, Introduction to Algorithms, McGraw-Hill Higher Education, 2001
• 12: C. Dürr, P. Høyer. A quantum algorithm for finding the minimum. quant-ph/9607014, 1996.
• 13: 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]
• 14: P. Høyer, J. Neerbek, Y. Shi. Quantum complexities of ordered searching, sorting, and element distinctness. 28th International Colloquium on Automata, Languages, and Programming, pp. 62--73, 2001. Also: quant-ph/0102078.
• 15: Quantum computation and quantum information, Cambridge University Press, New York, NY, 2000
• 16: Jakob Pagter , Theis Rauhe, Optimal Time-Space Trade-Offs for Sorting, Proceedings of the 39th Annual Symposium on Foundations of Computer Science, p.264, November 08-11, 1998
• 17: S. Reisch, G. Schnitger. Three Applications of Kolmogorov-Complexity. 23rd IEEE Symposium on Foundations of Computer Science, pp. 45--52, 1982.
• 18: Yaoyun Shi, Quantum Lower Bounds for the Collision and the Element Distinctness Problems, Proceedings of the 43rd Symposium on Foundations of Computer Science, p.513-519, November 16-19, 2002
• 19: A. C. C. Yao. Near optimal time-space tradeoffs for element distinctness. 29th IEEE Symposium on Foundations of Computer Science, pp. 91--97, 1988.

INDEX TERMS

Primary Classification:
  F. Theory of Computation
  F.2 ANALYSIS OF ALGORITHMS AND PROBLEM COMPLEXITY

General Terms:
Algorithms, Theory

Keywords:
complexity theory, lower bounds, quantum algorithms, sorting