On Thu, Jul 22, 2010 at 1:36 PM, Tom Rokicki <rokicki@gmail.com> wrote:
The layman's approach to solving NP-complete problems by postselection is to assert that the "many worlds" interpretation of quantum mechanics is true, bounce N photons off a semisilvered mirror, use the N-bit pattern detected on the other side as the input, and kill yourself if it doesn't work. In 2^{-N} of the worlds, you solve the problem and continue living.
So quantum computing only works if every user agrees to participate in what is essentially Russian roulette?
Heh! No serious quantum algorithm stops at the "superposition of all answers" stage; there's always a postprocessing step, which is usually a quantum Fourier transform. Once the postprocessing step is done, the quantum state is nearly classical, with the amplitude almost entirely centered on a single outcome. Note that the postprocessing step is unitary, unlike postselection, which is a projection. For example, Shor's algorithm is for factoring large numbers. Assume n = pq, where p and q are prime, since that's the form used in cryptography. You pick some a coprime to n and compute a^x mod n for a bazillion x's at once. Then you do a quantum Fourier transform, which puts the amplitude on small multiples of phi(n) = (p-1)(q-1). When you measure the state, you get one of those and can solve for p and q. In Grover's algorithm, you start with an equal superposition of all possible inputs and then negate the phase of the right answer. Since there are exponentially many inputs, this change in phase doesn't move the state very far from where it started. Grover's amplification step lines up the state so the next time you negate the phase of the right answer, it will move the state as far as possible from where it started. If you do this pi/4 * 2^{N/2} times, it will be pointing at the right answer. In Lloyd's postselection setup, he uses the closed timelike curves' consistency condition to "kill" all the other worlds where the input is wrong. There's no experimental evidence yet to say that such a process actually exists. You can stack this paper next to his NP-complete solver that uses nonlinear QM (for which there's no evidence either). -- Mike Stay - metaweta@gmail.com http://www.cs.auckland.ac.nz/~mike http://reperiendi.wordpress.com