Quantum sort
A quantum sort is any sorting algorithm that runs on a quantum computer. Any comparison-based quantum sorting algorithm would take at least 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].
References
- ^ 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.
{{cite conference}}: Unknown parameter|booktitle=ignored (|book-title=suggested) (help)CS1 maint: multiple names: authors list (link) 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.
{{cite conference}}: Unknown parameter|booktitle=ignored (|book-title=suggested) (help)
See also
- Bogosort, a sorting algorithm with a joke quantum implementation