Dit kom ik net tegen op Wikipedia:
Ik weet niet of ik hier om moet lachen of huilenQuantum bogosort
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 2N (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.[2] 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 — since it has to be executed at most once.) Arguably, creating 2N universes is also very memory-intensive.