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/