Re: Quantum computing

Eliezer S. Yudkowsky (
Mon, 14 Sep 1998 13:30:40 -0500

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.

--         Eliezer S. Yudkowsky

Disclaimer:  Unless otherwise specified, I'm not telling you
everything I think I know.