up vote 12 down vote favorite
1

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

share|improve this question
  • 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 at 23:02
up vote 7 down vote

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

share|improve this answer
  • Ah, thanks for your answer, EvginyZh! And welcome to Quantum Computing! It seems you are already familiar with the network, good! If you feel like introducing yourself, feel free to drop by in Quantum Computing Chat. However, I think this answer can be improved by adding a brief summary of the exact results in the referenced paper(s)! Could you do that? Thanks. – Discrete lizard Mar 25 at 13:06
up vote 5 down vote

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.

share|improve this answer
  • 1
    Oh, and btw Gustavo, welcome to the site! I hope you will continue the quality contributions here! If you're feeling lost, take the tour or if you want to introduce yourselves or just have some friendly words, come visit the Quantum Computing Chat! – Discrete lizard Mar 26 at 7:27
  • Oh and is there a claimed complexity result in some model? – Discrete lizard Mar 26 at 15:42

Your Answer

 
discard

By clicking "Post Your Answer", you acknowledge that you have read our updated terms of service, privacy policy and cookie policy, and that your continued use of the website is subject to these policies.

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