Re: Quantum computing

Michael Nielsen (mnielsen@theory.caltech.edu)
Mon, 14 Sep 1998 10:39:33 -0700 (PDT)

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.

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.

> 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/