From: Michael Nielsen (mnielsen@theory.caltech.edu)
Date: Mon Sep 14 1998 - 13:39:41 MDT
On Mon, 14 Sep 1998, Eliezer S. Yudkowsky wrote:
> Eliezer S. Yudkowsky wrote:
> >
> > Michael Nielsen wrote:
> > >
> > > On Sat, 12 Sep 1998, Eliezer S. Yudkowsky wrote:
> > > >
> > > > But quantum computing, at least in theory, should allow handling of
> > > > exponential search problems.
> > >
> > > What do you mean by that?
> >
> > Check out: http://www.qubit.org
>
> - Whoop! Apparently Michael Nielsen has Web pages about quantum computing.
> Which wasn't quite clear from his question - please tell me things like that.
What you wrote was slightly ambiguous. I was asking for clarification,
not a simplified explanation of quantum computing. Sorry for the
confusion.
> Still, a creative operating system should be able to ignore this "scratch"
> memory, pick up whatever result was left in the qubits, and figure out which
> branch indicated success. Supposing that arbitrarily large probability
> amplitudes for the qubits are possible, the probability amplitude could
> increase exponentially with the success of a given branch. Otherwise, the
> measurement might only be able to cut the search space by half, necessitating
> repeated searches to read off the identity of the successful eigenstate/thread.
If what you say is possible, then it would be possible to search
exponentially large search spaces in a polynomial number of operations.
One implication of the Bennett et al result is that this is not possible
within any known, physically realistic, model of computation.
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