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
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.
A "qubit" is a quantum bit, the basic unit which can "fork" reality by being 0 in one and 1 in the other. Thus a 32-qubit machine could compute in 4 billion separate branches simultaneously, at least in theory. Current proposed quantum-computing architectures have other constraints, which would limit them to certain simple manipulations of the qubits. It's still possible to factor large numbers, though. With quantum computing, P=NP.
State of the field:
There is a known algorithm for factoring large numbers.
A 3-qubit superposition has been created and tested.
--
sentience@pobox.com Eliezer S. Yudkowsky
http://pobox.com/~sentience/AI_design.temp.html
http://pobox.com/~sentience/sing_analysis.html
Disclaimer: Unless otherwise specified, I'm not telling you
everything I think I know.