Quantum computing

Eliezer S. Yudkowsky (sentience@pobox.com)
Mon, 14 Sep 1998 10:50:33 -0500

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
Disclaimer:  Unless otherwise specified, I'm not telling you
everything I think I know.