On Thu, Jul 22, 2010 at 11:14 AM, Henry Baker <hbaker1@pipeline.com> wrote:
Postselection is a vital part of the nascent science of quantum computing. In traditional computing, if a user needs to determine which set of variables in an equation leads to the answer being true, the computer must try every combination until it hits upon one that works. In quantum computing, due to the weird parallel behaviour of subatomic particles, it seems to be possible to simplify the procedure by running all possible variations simultaneously, and selecting only the combinations that make the answer true.
This paragraph is somewhat misleading. The postselection Lloyd talks about is only available when you have closed timelike curves; this is not something your average NMR or ion-trap or optical quantum computer can do. 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. -- Mike Stay - metaweta@gmail.com http://www.cs.auckland.ac.nz/~mike http://reperiendi.wordpress.com