On Mon, 14 Sep 1998, 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.
>
> Below the macroscopic level, before state-vector reduction, the wavefunction
> is uncollapsed. So you can compute in multiple branches of reality, then
> collapse to find the answer. A physical implementation of the BBW (Branch
> Both Ways) instruction.
I'm still not quite sure what you mean by "exponential search problems". I presume you mean searching through a search space of 2^n possibilities with a number of operations polynomial in n.
> With quantum computing, P=NP.
This is not known to be true. It would be if factoring were NP-complete, however despite considerable effort, this has never been proved.
Michael Nielsen
http://www.theory.caltech.edu/~mnielsen/