On Mon, 14 Sep 1998, Eliezer S. Yudkowsky wrote:
> 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?
They used the "quantum Turing machine model", essentially a refined version of Deutsch's original model. This is the most powerful model of quantum computation known. It is equivalent to several other popular models.
> Can this quantum
> computer simulate physical reality in polynomial time?
Heh. That's a complicated question. Put it this way, no physical phenomenon is known which can't be simulated efficiently on this quantum computer. If such a phenomenon were found it would be very important.
> 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.
Your algorithm has an exponential space overhead right here (the 4 billion "destinations"), which takes it out of the quantum analogue of P.
Michael Nielsen
http://www.theory.caltech.edu/~mnielsen/