A quantum sort is any sorting algorithm that runs on a quantum computer. Any comparison-based quantum sorting algorithm would take at least steps, which is already achievable by classical algorithms. Thus, for this task, quantum computers are no better than classical ones. However, in space-bounded sorts, quantum algorithms outperform their classical counterparts.
- P. Høyer, J. Neerbek, Y. Shi (2001). "Quantum complexities of ordered searching, sorting, and element distinctness". 28th International Colloquium on Automata, Languages, and Programming. pp. 62–73. Also in quant-ph/0102078
- Klauck, Hartmut (2003). "Quantum Time-Space Tradeoffs for Sorting". Proceedings of the thirty-fifth annual ACM symposium on Theory of computing.
- Bogosort, a sorting algorithm with a joke quantum implementation
|P ≟ NP||This theoretical computer science–related article is a stub. You can help Wikipedia by expanding it.|