アルゴリズム – Will quantum computers speed up sorting?

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.


  1. 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 .
Scroll to Top