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