Sorting in O(n) time:

1. Apply a quantum permutation to your list.

2. Check if it's sorted.

3. If not, destroy the universe.

Related (amazing) paper by Scott Aaronson: "NP-complete Problems and Physical Reality" (http://arxiv.org/abs/quant-ph/0502072). He proposes "anthropic computing" as a way of solving NP-complete problems in polynomial time: guess an answer, then kill yourself if the answer is wrong.

It would be very eerie if suddenly all the guesses started being right.

I am worried that someone will actually try this sometime and it will turn out not to work, either because MWI is wrong or because the destruction of the universe was incomplete — for example, collapsing the false vacuum would merely change the state of the things in the universe, not destroy the universe per se.

Fortunately, we don't have any currently promising avenues for nucleating a true vacuum or anything like that, so this algorithm is purely theoretical.

For now.

That made me think of Greg Egan's Quarantine:

https://en.wikipedia.org/wiki/Quarantine_%28Greg_Egan_novel%...

Best-case runtime = 1. Worst-case = infinity.

I think the joke is that in all cases but the best-case, you won't be around to observe it, this becomes practical once you can create a universe for every permutation and destroy all but the universe which notifies you that it's the best-case.

In all good text books this is left as an exercise for the reader.

In a really good text book, this is left as an exercise that the reader won't do.

No, checking whether a list is sorted is O(n) ;).

Bogosort is O(n) in the best case and O(inf) in the worst case).

Optimize out the check, so it will be O(1) in some cases. ;)

The convergence of this method depends on the underlying distribution for your random process. It could be O(never).

As Scott Aaronson points out, the easy solution to this is that you add a slight quantum chance that the algorithm will yield "Reject". As long as that chance is non-zero, but greatly smaller than the probability of any particular successful permutation, you will survive in the universe that says "Reject".

This sounds like a joke but this is exactly the proof that sorting is in NP.

What is a quantum permutation?