Eliezer S. Yudkowsky, <sentience@pobox.com>, writes:
> 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.
Note though that a reduction from n to sqrt(n) does not cross the boundary between polynomial and super-polynomial complexity. If search problems have exponential growth trees, a quantum computer can look twice as far down the tree, roughly speaking. But the QC still faces an exponentially growing problem.
Hal