lemming's Journal: Extension of quantum bogosort

Zif and I were talking today, and quantum bogosort came up. It's a sorting algorithm that runs in O(N) time, given two assumptions:

1. The many-worlds interpretation of quantum mechanics is correct.
2. You have a reliable means of destroying the entire universe, probably something stronger than a ballistic heffalump (first post is useless).

Now, suppose this--what if you put off destroying the universe for a little bit? Sure, I'm asking you to swallow a very large (and nihilistic) grain of salt, but stay with me here... What if we put a little procrastination into the mix?

Well, if we don't mind having 2^N-1 universes being cursed to puzzle over incorrect computational results until they come to the grim realization of their impending doom, then we can generalize this algorithm to solve any problem in at most O(M) time up front (where M is the size of a possible answer), and O(f(N,M)) time at some point later, where f(N,M) is the time cost to verify an answer of size M to a problem of size N.

I can picture it now. A professor, hard at work in front of his new and shiny quantum computer suddenly leaps from his seat. Screaming, he runs from the office.

A student, hoping for an extension on his homework, is nearly knocked over as the professor tears away. He can see plainly on the still-lit computer screen, "2 + 2 = 3."

"Well, I guess I won't be needing that extension."

Re:Qubits?

[tepid451]

I "read" it in a very weak sense of the word---in the kind of way where I forgot everything I read very quickly thereafter. OK, I'll eat crow and read it again. The joke's much funnier if the plural has to go...