Michael Nielsen wrote:
>
> Unfortunately, a no-go theorem of Bennett, Bernstein, Brassard and
> Vazirani shows that this is not possible in general. Generally, their
> lower bound shows that a quantum computer needs to access the list
> ~sqrt(2^n) times. Better than the classical result by a quadratic factor,
> but not an exponential improvement.
How is "quantum computer" being defined in this instance? Can this quantum computer simulate physical reality in polynomial time?
Let's say that we send a a photon through a single half-silvered mirror and then recombine the path, then send the twin ghost-photons down a series of 32 levels of half-silvered mirrors, sending the superimposed pair to 4 billion destinations. One of these destinations contains a half-silvered-mirror setup that synchronizes the two phases, and all the others contain a half-silvered-mirror setup that causes the two eigenstates to cancel out. At measurement, the photon appears in the unique destination. It seems to me that this physical search will cover 2^n physical targets in O(n) time.
--
sentience@pobox.com Eliezer S. Yudkowsky
http://pobox.com/~sentience/AI_design.temp.html
http://pobox.com/~sentience/sing_analysis.html
Disclaimer: Unless otherwise specified, I'm not telling you
everything I think I know.