8
$\begingroup$

Recently, I've read about 'Quantum bogo sort' on some wiki. The basic idea is, that like bogo sort, 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' bogo-sort 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 bogo sort'? 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$
7
$\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$ 'Destroying all bad universes' sounds very much like postselection to me $\endgroup$ – Mithrandir24601 Mar 23 '18 at 9:11
  • $\begingroup$ @Mithrandir24601 Could you elaborate? $\endgroup$ – Sanchayan Dutta Mar 23 '18 at 9:15
  • $\begingroup$ Essentially, here, postselection means that you make a measurement and ignore all values that didn't give a specific outcome - you have an ancilla qubit, with a non-zero probability of being measured to be in state 1 and you condition the outcome on this result occurring (the point is that you ignore the time that it takes for the measurement outcome to be '1') $\endgroup$ – Mithrandir24601 Mar 23 '18 at 9:24
  • $\begingroup$ @Mithrandir24601 Okay, but how is that related to detecting whether in a certain universe, a list is sorted or not? Are you saying that detection is like making a measurement on a qubit, first and then detecting its state? $\endgroup$ – Sanchayan Dutta Mar 23 '18 at 9:27
  • 2
    $\begingroup$ @Blue it being an interpretation means that it should be possible to equivalently describe the same things using "mainstream terminology", so I don't see how it would be useful to use many-world terminology to describe an algorithm in this context. Wouldn't it be better to maybe answer the question by explaining how the language in which the algorithm is formulated in the OP can be translated into standard notions, and then go on from there? $\endgroup$ – glS Mar 23 '18 at 18:31

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.