From: Eliezer S. Yudkowsky (sentience@pobox.com)
Date: Mon Sep 14 1998 - 09:50:33 MDT
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.
This archive was generated by hypermail 2.1.5 : Fri Nov 01 2002 - 14:49:34 MST