Open-Source Internship opportunity by OpenGenus for programmers. Apply now.
Quantum Bogo Sort a quantum sorting algorithm which can sort any list in Θ(1), using the "many worlds" interpretation of quantum mechanics.
The Many-Worlds Interpretation (MWI) of quantum mechanics holds that there are many worlds which exist in parallel at the same space and time as our own. The existence of the other worlds makes it possible to remove randomness and action at a distance from quantum theory and thus from all physics.
It works as follows:
- Step 1: Quantumly randomise the list, 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: If the list is not sorted, destroy the universe. (This operation is left as an exercise to the reader.)
- Step 3: All remaining universes contain lists which are sorted.
Complexity
- Worst case time complexity:
Θ(N) - Average case time complexity:
Θ(1) - Best case time complexity:
Θ(1) - Space complexity:
Θ(1)
In the average case, the universe is destroyed.
As described above, is not a stable sort. A stable version might be produced as follows:
- Step 1: Configure the quantum randomiser to produce random code, rather than shuffle lists. Instruct it to generate some code.
- Step 2: If the resulting code is not a stable QuantumBogoSort, destroy the universe.
- Step 3: All remaining universes now have a stable QuantumBogoSort algorithm.
