Quantum sort

From Wikipedia, the free encyclopedia
Jump to: navigation, search

A quantum sort is any sorting algorithm that runs on a quantum computer. Any comparison-based quantum sorting algorithm would take at least \Omega(n \log n) steps,[1] which is already achievable by classical algorithms. Thus, for this task, quantum computers are no better than classical ones. Do note, that in space-bounded sorts, quantum algorithms outperform their classical counterparts.[2]


  1. ^ P. Høyer, J. Neerbek, Y. Shi (2001). "28th International Colloquium on Automata, Languages, and Programming". pp. 62–73.  |chapter= ignored (help) Also in quant-ph/0102078
  2. ^ Klauck, Hartmut (2003). "Proceedings of the thirty-fifth annual ACM symposium on Theory of computing".  |chapter= ignored (help)

See also[edit]

  • Bogosort, a sorting algorithm with a joke quantum implementation