5 ms·
This reminded me of: QuantumBogoSort a quantum sorting algorithm which can sort any list in O(1), using the "many worlds" interpretation of quantum mechanics.
by thret 6y ago
This reminded me of: QuantumBogoSort a quantum sorting algorithm which can sort any list in O(1), using the "many worlds" interpretation of quantum mechanics.
It works as follows:
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.
2. If the list is not sorted, destroy the universe. (This operation is left as an exercise to the reader.)
3. All remaining universes contain lists which are sorted.
- http://wiki.c2.com/?QuantumBogoSort http://wiki.c2.com/?QuantumBogoSort
- mckirk 6y agoAs a fall-back (in case the universe-destroying resources are busy), you could also sort the list classically if the quantum randomization didn't do it. There'd still be that one lucky-bastard-universe that gets all the sorting done in O(1)... As a side note though, please never do this. Our simulators would pull the plug really quickly if we deliberately caused state explosions like that.
- karl-j 6y agoSo let’s say I’ve got step 2. figured out with vacuum decay or similar, how do I check if the list is sorted in O(1) to determine if I destroy the universe or not? And given that the list being sorted is a one in n! chance, often enormously less likely than than hardware malfunction, wouldn’t the algorithm mostly produce malfunctions rather than sorted lists? (Genuinely curious if I’ve got the right understanding of the CS and potential physics.)
- WJW 6y agoChecking if a list is sorted is O(N) if you do it in a single thread since you'd have to check all the elements. If you can do it with a prefix sum or something, it should be possible to do it in O(log N) over many cores. Btw, the quantum bogosort also assumes that destroying the universe is O(1), which seems unlikely. Clearly, when sorting a bigger list there is more information in the universe (ie the list). Since information and energy seem to have some equivalence in quantum dynamics, is does not seem unreasonable that destroying a universe with more information in it would take longer and so destroying the universe cannot be O(1).
- michaelmior 6y ago> Clearly, when sorting a bigger list there is more information in the universe (ie the list). I don't think this is necessarily true. You could argue that the list is simply a bigger fraction of the information in the universe.
- bmm6o 6y agoDoes it matter how long destroying the universe takes, since that's in the unsorted branch? The universe with the sorted list continues immediately, the cleanup is handled elsewhere.
- deleted 6y ago[deleted]
- arethuza 6y agoWon't any quantum "destroy the universe" operation result in one destroyed universe and one that isn't?
- tomrod 6y agoEh. You have to assess whether the list is sorted before you destroy the universe, thus increasing the total algorithm runtime complexity.