Question: Question:
Can a quantum algorithm be asymptotically faster than a sequential classical algorithm when sorting into a randomly accessible array?
Answer: Answer:
When limited to comparative sorting, the time complexity of the quantum algorithm for an array of length n is Ω (n log n) [1] , so it is asymptotically the same as in the classical algorithm.
I don't know much about "what if it's not a comparative sort?" Or "what if I impose other restrictions?" According to the English Wikipedia "Quantum sort" , quanta may be more advantageous when space is limited.
- 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 .