Quantum sort
From Wikipedia, the free encyclopedia
Template:DMCATemplate:Short description 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, and should be disregarded when it comes to time complexity. However, in space-bounded sorts, quantum algorithms outperform their classical counterparts.[2]
References
Page Template:Reflist/styles.css has no content.
- ^ Page Module:Citation/CS1/styles.css has no content.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. Lecture Notes in Computer Science. Vol. 2076. pp. 62–73. arXiv:quant-ph/0102078. doi:10.1007/3-540-48224-5_29. ISBN 978-3-540-42287-7.
- ^ Page Module:Citation/CS1/styles.css has no content.Klauck, Hartmut (2003). "Quantum Time-Space Tradeoffs for Sorting". Proceedings of the thirty-fifth annual ACM symposium on Theory of computing. p. 69. arXiv:quant-ph/0211174. doi:10.1145/780542.780553. ISBN 1581136749.
Lua error in package.lua at line 80: module 'Module:Navbox/configuration' not found. Lua error in package.lua at line 80: module 'Module:Navbox/configuration' not found.
