4 ms·

Quantum Bogosort[0] sorts in O(N) time, but the destroy_universe() step is only safe if the Many Worlds interpretation of Quantum Mechanics is correct. [0] htt

by KMag 6y ago

Quantum Bogosort[0] sorts in O(N) time, but the destroy_universe() step is only safe if the Many Worlds interpretation of Quantum Mechanics is correct. [0] https://en.wikipedia.org/wiki/Bogosort#Quantum_bogosort https://en.wikipedia.org/wiki/Bogosort#Quantum_bogosort

steerablesafe 6y ago
Also you you need "real" (in the quantum sense) random generator for the shuffling. If you use a PRNG then you risk destroying all the universes.
- taneq 6y ago
  You could always just use a pseudorandom number generator and rely on bit errors to generate the different potential sort orders. ;)
  - steerablesafe 6y ago
    If you add bit errors to the picture then the check after shuffle spuriously passing has a significant, potentially much higher probability than a bit error introducing new, previously impossible random shuffling and producing a sorted sequence. So in a significant portion (maybe most) of the non-destroyed universes quantum bogosort returns an unsorted sequence due to bit errors.
    - taneq 6y ago
      Repeat the check an arbitrary number of times then? We have infinite universes, remember. :)
YokoZar 6y ago
If you're using a cloud host that doesn't charge you anything for instances with a very low runtime, you can implement quantum bogosort for free - just have every unsorted instance self-destruct promptly.
- FroshKiller 6y ago
  For any given input, there is no advantage to running more than one instance in the same universe.
  - bluGill 6y ago
    This is creating many universes though.
bluGill 6y ago
You can trivially parallelize this algorithm to be O(1): for each permutation you create universes to check all finite lengths of the list in parallel and destroy the universes that check either less elements than are in the list or that run off the end of the list. I'm not sure if this can extend to infinite size lists. Sorting infinite lists in finite time makes my head hurt.

by KMag 6y ago

steerablesafe 6y ago

Also you you need "real" (in the quantum sense) random generator for the shuffling. If you use a PRNG then you risk destroying all the universes.

taneq 6y ago
You could always just use a pseudorandom number generator and rely on bit errors to generate the different potential sort orders. ;)
- steerablesafe 6y ago
  If you add bit errors to the picture then the check after shuffle spuriously passing has a significant, potentially much higher probability than a bit error introducing new, previously impossible random shuffling and producing a sorted sequence. So in a significant portion (maybe most) of the non-destroyed universes quantum bogosort returns an unsorted sequence due to bit errors.
  - taneq 6y ago
    Repeat the check an arbitrary number of times then? We have infinite universes, remember. :)

YokoZar 6y ago

If you're using a cloud host that doesn't charge you anything for instances with a very low runtime, you can implement quantum bogosort for free - just have every unsorted instance self-destruct promptly.

FroshKiller 6y ago
For any given input, there is no advantage to running more than one instance in the same universe.
- bluGill 6y ago
  This is creating many universes though.

bluGill 6y ago

You can trivially parallelize this algorithm to be O(1): for each permutation you create universes to check all finite lengths of the list in parallel and destroy the universes that check either less elements than are in the list or that run off the end of the list. I'm not sure if this can extend to infinite size lists. Sorting infinite lists in finite time makes my head hurt.