costela.net

Sometimes Wikipedia shows it even has a somewhat humorous side. My finding it funny may be a product of late night learning sessions and semi-random clicking-sprees, but still, worthy of a chuckle for those with the right (wrong?) inclinations.

Quantum computing could be used to effectively implement a bogosort algorithm 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 2^N (where N is the number of random bits) universes and one of these will be such that this single shuffle had produced the list in sorted order. The list is then tested for sortedness (requiring n-1 comparisons); should it be out of order, the computer destroys the universe – implementation of this step being left as an exercise for 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 while this algorithm is O(n) in time, permuting the list requires O(n log n) bits of quantum randomness. It also assumes that destroying the universe is O(1) in operation.

Found here.