From: Michael Nielsen (mnielsen@theory.caltech.edu)
Date: Mon Sep 14 1998 - 13:32:02 MDT
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/
This archive was generated by hypermail 2.1.5 : Fri Nov 01 2002 - 14:49:34 MST