As a result of an excellent answer to my question on quantum bogosort, I was wondering what is the current state of the art in quantum algorithms for sorting.

To be precise, sorting is here defined as the following problem:

Given an array $A$ of integers (feel free to choose your representation of $A$, but be clear about this, I think this already is non-trivial!) of size $n$, we wish to transform this array into the array $A_s$ such that the arrays 'are reshufflings of each other's and $A_s$ is sorted, i.e. $A_s[i]\leq A_s[j]$ for all $i\leq j$.

What is known about this? Are there complexity bounds or conjectures for certain models? Are there practical algorithms? Can we beat classical sorting (even the bucket or radix sort at their own game? (i.e. in the cases where they work well?))


For comparison-based sorting (and search) bounds seem to fit the ones of classical computers: $\Omega(N\log N)$ for sorting and $\Omega(\log N)$ for search, as shown by Hoyer et al. A couple of quantum sorting algorithms are listed in 'Related work' section of "Quantum sort algorithm based on entanglement qubits {00, 11}".


There is a newer result from Robert Beals, Stephen Brierley, Oliver Gray, Aram Harrow, Samuel Kutin, Noah Linden, Dan Shepherd, Mark Stather. They present on Table 2 of Efficient Distributed Quantum Computing the results for bubble sort and insertion sort, it is mainly for "network sorting" but they gave more references about sorting.

A quick and very briefly description of the paper can be: We can say that the paper show how to solve several problems such as access the quantum memory without the loss of superposition (and they give the cost for it). Also, the paper presents the problem of sorting a network doing it quantumly (one of the problems is the reversibility of operations). I like the paper because it raises several problems and the authors gave the solution for some of the problems. I think that it is hard to try to summarize, I really recommend to read.

I hope that I have helped.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.