Quantum sort
From Wikipedia, the free encyclopedia
 |
This article is an orphan, as few or no other articles link to it. Please introduce links to this page from related articles; suggestions may be available. (February 2009) |
A quantum sort is any sorting algorithm that runs on a quantum computer. Any comparison-based quantum sorting algorithm would take at least Ω(nlog 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]
[edit] 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. http://www.springerlink.com/content/25gl9elr5rxr3q6a/. 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. http://portal.acm.org/citation.cfm?id=780553.
[edit] See also
- 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. |
