9
$\begingroup$

Recently, I've read about 'quantum bogosort' on some wiki. The basic idea is, that like bogosort, we just shuffle our array and hope it gets sorted 'by accident' and retry on failure.

The difference is that now, we have 'magic quantum', so we can simply try all permutations at once in 'parallel universes' and 'destroy all bad universes' where the sort is bad.

Now, obviously, this doesn't work. Quantum is physics, not magic. The main problems are

  1. 'Parallel universes' is merely an interpretation of quantum effects, not something that quantum computing exploits. I mean, we could use hard numbers here, interpretation will only confuse matters here, I think.

  2. 'Destroying all bad universes' is a bit like qubit error correction, a very hard problem in quantum computing.

  3. Bogo sort remains stupid. If we can speed-up sorting via quantum, why not base it on a good sorting algorithm? (But we need randomness, my neighbour protests! Yes, but can't you think of a better classical algorithm that relies on randomness?)

While this algorithm is mostly a joke, it could be an 'educational joke', like the 'classical' bogosort as the difference between best case, worst case and average case complexity for randomized algorithms is easy and very clear here. (for the record, best case is $\Theta(n)$, we are very lucky but still must check that our answer is correct by scanning the array, expected time is simply awful (IIRC, proportional to the number of permutations, so $O(n!)$) and worst case is we never finish)

So, what can we learn from 'quantum bogosort'? In particular, are there real quantum algorithms that are similar or is this a theoretical or practical impossibility? Furthermore, has there been research into 'quantum sorting algorithms'? If not, why?

$\endgroup$
8
$\begingroup$

DISCLAIMER: The quantum-bogosort is a joke-algorithm

Let me just state the algorithm in brief:

  • Step 1: Using a quantum randomization algorithm, randomize the list/array, such that there is no way of knowing what order the list is in until it is observed. This will divide the universe into $O(N!)$ universes; however, the division has no cost, as it happens constantly anyway.

  • Step 2: Check if the list is sorted. If not, destroy the universe (neglecting the actual physical possibility).

Now, all remaining universes contain lists/arrays which are sorted.

Worst Case Complexity: $O(N)$

(we only consider those universes which can observe that the list is sorted)

Average/Best Case Complexity: $O(1)$

One of the major problems with this algorithm is the huge possibility magnification of errors as Nick Johnson mentions here:

This algorithm has a much bigger problem, however. Assume that one in 10 billion times you will mistakenly conclude a list is sorted when it's not. There are 20! ways to sort a 20 element list. After the sort, the remaining universes will be the one in which the list was sorted correctly, and the 2.4 million universes in which the algorithm mistakenly concluded the list was sorted correctly. So what you have here is an algorithm for massively magnifying the error rate of a piece of machinery.


'Parallel universes' is a highly simplified interpretation of quantum effects, not something that Quantum Computing exploits.

Not really sure what you mean by "highly simplified interpretation of quantum effects". The sources (this and this) I found on the internet regarding the quantum bogosort do not explicitly mention that they're using the alternative interpretation of QM i.e. the Everett's interpretation which you might be thinking about. In fact I'm not even sure how to glue together the Everett's interpretation and quantum-bogosort (using post-selection, as some people commented). Anyhow, just as a note: in mainstream cosmology, it is widely believed that more than one universe exists and there are even classifications for them, called the Max Tegmark's four levels and Brian Greene's nine types and Cyclic theories. Read the Wiki article on Multiverse for more details.

'Destroying all bad universes' is a bit like qubit error correction, a very hard problem in Quantum Computing.

Sure, it is in fact much harder, and we don't expect to destroy universes literally. The quantum bogosort is just a theoretical concept, with no practical applications (which I know of).

Bogo sort remains stupid. If we can speed-up sorting via quantum, why not base it on a good sorting algorithm? (But we need randomness, my neighbour protests! Yes, but can't you think of a better classical algorithm that relies on randomness?)

Yes, it does remain stupid. It does seem to have started out as an "educational joke" as you said. I did try to find the origin of this sort, or relevant academic papers, but couldn't find any. However, even the classical bogosort is stupid in the sense that is widely held as one of the most inefficient sorting algorithms. Still it has been researched on, purely out of educational interest.

In particular, are there real quantum algorithms that are similar or is this a theoretical or practical impossibility?

None that I know of. Such algorithms are indeed theoretical possibilities, but definitely not practical (at least, not yet).

Furthermore, has there been research into 'quantum sorting algorithms'? If not, why?

There indeed has been research into "quantum sorting". But the problem with such sorting algorithms is any comparison-based quantum sorting algorithm would take at least $\Omega (N\log N)$ steps, which is already achievable by classical algorithms. Thus, for this task, quantum computers are no better than classical ones. However, in space-bounded sorts, quantum algorithms outperform their classical counterparts. This and this are two relevant papers.

$\endgroup$
  • $\begingroup$ Comments are not for extended discussion; this conversation has been moved to chat. $\endgroup$ – Sanchayan Dutta May 15 at 14:53

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.