View source for Quantum sort

{{Use American English|date=January 2019}}{{Short description|Sorting algorithms for quantum computers
}}
A '''quantum sort''' is any [[sorting algorithm]] that runs on a [[quantum computer]]. Any comparison-based quantum sorting algorithm would take at least <math>\Omega(n \log n)</math> steps,<ref>{{cite conference
 |last1=Høyer |first1=P.
 |last2=Neerbek |first2=J.
 |last3=Shi |first3=Y.
 |title=Quantum complexities of ordered searching, sorting, and element distinctness
 |series=Lecture Notes in Computer Science
 |book-title=28th International Colloquium on Automata, Languages, and Programming
 |pages=62–73
 |year=2001
 |volume=2076
 |arxiv=quant-ph/0102078
 |doi=10.1007/3-540-48224-5_29
|isbn=978-3-540-42287-7
 }}</ref> which is already achievable by classical algorithms. Thus, for this task, quantum computers are no better than classical ones, and should be disregarded when it comes to time complexity. However, in space-bounded sorts, quantum algorithms outperform their classical counterparts.<ref>{{cite conference
 |last=Klauck
 |first=Hartmut
 |title=Quantum Time-Space Tradeoffs for Sorting
 |book-title=Proceedings of the thirty-fifth annual ACM symposium on Theory of computing
 |year=2003
 |page=69
 |doi=10.1145/780542.780553
|arxiv=quant-ph/0211174
 |isbn=1581136749
 }}</ref>

==References==
<!-- this 'empty' section displays references defined elsewhere -->
{{reflist}}

{{quantum computing}}
{{sorting}}

[[Category:Sorting algorithms]]
[[Category:Quantum algorithms]]

{{Quantum-stub}}{{comp-sci-theory-stub}}