Bogosort - Wikipedia, the free encyclopedia
Quantum Bogosort
An in-joke among some computer scientists is that quantum computing could be used to effectively implement a bogosort with a time complexity of O(n). It uses true quantum randomness to randomly permute the list. By the many-worlds interpretation of quantum physics, the quantum randomization spawns an infinite array of universes and some of these will be such that the single shuffle had produced the list in sorted order because the total number of distinct orderings, though large, is not infinite. The list is then tested for sortedness (requiring n-1 comparisons); should it be out of order, the computer triggers its "destroy universe" operation (typically accompanied by a dry observation that implementing this operation is left as an exercise to the reader). The only observers will then be in the surviving universes and will see that the randomization worked the first time and that the list is in sorted order.
Note, however, that even here there is no free lunch – while this algorithm is O(n) in time, permuting the list requires that we consume O(n log n) bits of quantum randomness. (It also assumes that destroying the universe is O(1) in operation - since it has to be executed at most n-1 times.)
This sort of made my day. I laughed out loud when I read this while eating my bagel.
My guess is that destruction of the world isn't O(1) or even doable in polynomial time ... ;)
