# What is the current state of the art in Quantum sorting algorithms?

As a result from an excellent answer to my question on Quantum bogo sort, 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 eachother' 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?))

• One remarks that may clarify what sort of answer I'd like. Apparently, 'space bounded quantum algorithms' outperform the classical ones. But this rings the alarm bells and sounds like a very much under-specified conclusion: a qubit is fundamentally other than a classical bit. If we compare those, we're comparing apples with pears and in this case I wouldn't be surprised we need a bit lit quantum apples. (Hence, why I should say merely choosing a qubit encoding of your array may already be non-trivial!) An answer addressing this potential issue is more likely to get accepted! – Discrete lizard Mar 23 '18 at 23:02

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}".