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. However, in space-bounded sorts, quantum algorithms outperform their classical counterparts.[2]
References
- Høyer, P.; Neerbek, J.; Shi, Y. (2001). "Quantum complexities of ordered searching, sorting, and element distinctness". 28th International Colloquium on Automata, Languages, and Programming. pp. 62–73. arXiv:quant-ph/0102078. doi:10.1007/3-540-48224-5_29.
- Klauck, Hartmut (2003). "Quantum Time-Space Tradeoffs for Sorting". Proceedings of the thirty-fifth annual ACM symposium on Theory of computing. arXiv:quant-ph/0211174. doi:10.1145/780542.780553.
| General |  | ||||||||
|---|---|---|---|---|---|---|---|---|---|
| Theorems | |||||||||
| Quantum communication | |||||||||
| Quantum algorithms | |||||||||
| Quantum complexity theory | |||||||||
| Quantum computing models | |||||||||
| Quantum error correction | |||||||||
| Physical implementations |
| ||||||||
| Software | |||||||||
| |||||||||
This article is issued from Wikipedia. The text is licensed under Creative Commons - Attribution - Sharealike. Additional terms may apply for the media files.