What is the current state of the art in quantum sorting algorithms?

Question

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?))

Answer 1

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

Answer 2

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.

Answer 3

As your question suggests there is little literature on the subject. Also I wrote a blog post about an algorithm I created that can sort a list of numbers using a quantum algorithm.

You can find it here.

In this article, I propose a quantum sort algorithm that allows you to sort a list of integers coded on two qubits. I have found that there is little literature on the subject. This algorithm can be used and can be used as a basis for solving sorting problems on an unsorted list of integers.

To solve this problem we will first create a quantum circuit that allows you to measure if a figure is lower than another for this the intuition is to be based on a circuit similar to a classic circuit of comparison of magnitude at 2 qubit.

The idea of ​​my algorithm is to permute 4 digits using control qubits which will be in superimposed state.

4 Hadamard quantum gates are used to implement these permutations and take advantage of the superposition of the Qubit ‘control’ register

In other words in the circuit above we see that we start the circuit by initializing the registers $a$, $b$, $m$, $n$ with its list of unsorted numbers, here ($a = 0$, $b = 2$, $m = 3$, $n = 1$) .

The permutation circuit which is controlled by a superimposed qubit register allows the list to be permuted in quantum superposition.

Thus we obtain on the qubit q0 the quantum state $|1\rangle$ if the permuted list is sorted in a decreasing way otherwise the quantum state $|0\rangle$.

In this article you will find the implementation of the algorithm in python and in OpenQASM. If you have any further questions, please do not hesitate to contact me.