Quantum sort
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 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
- ^ 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.
- ^ 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.
- v
- t
- e
Quantum information science
- DiVincenzo's criteria
- NISQ era
- Quantum computing
- Quantum information
- Quantum programming
- Quantum simulation
- Qubit
- Quantum processors
- cloud-based
- Bell's
- Eastin–Knill
- Gleason's
- Gottesman–Knill
- Holevo's
- No-broadcasting
- No-cloning
- No-communication
- No-deleting
- No-hiding
- No-teleportation
- PBR
- Quantum speed limit
- Threshold
- Solovay–Kitaev
- Purification
communication
Quantum cryptography |
---|
complexity theory
processor benchmarks
- Quantum supremacy
- Quantum volume
- Randomized benchmarking
- Relaxation times
- T1
- T2
computing models
error correction
implementations
Quantum optics | |
---|---|
Ultracold atoms | |
Spin-based | |
Superconducting |
programming
Quantum information science
Quantum mechanics topics
![]() | This quantum mechanics-related article is a stub. You can help Wikipedia by expanding it. |
- v
- t
- e
P ≟ NP | This theoretical computer science–related article is a stub. You can help Wikipedia by expanding it. |
- v
- t
- e