From: Eliezer S. Yudkowsky (sentience@pobox.com)
Date: Mon Sep 14 1998 - 11:41:24 MDT
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.
> >
> > What do you mean by that?
>
> Check out: http://www.qubit.org
- Whoop! Apparently Michael Nielsen has Web pages about quantum computing.
Which wasn't quite clear from his question - please tell me things like that.
Anyway, let me expand on that a bit - and feel free to correct me if I go off
the track...
Ordinary QCL (http://tph.tuwien.ac.at/~oemer/qc/qcl/) assumes that a series of
unitary operations is being applied to an entire qubit in all eigenstates.
It's _not_ possible to branch (within the code) on the value of a qubit, which
would turn each eigenstate into an isolated thread.
Suppose RAM can be maintained in superposition - not necessarily manipulated
by NMR pulses, but having different values in each eigenstate without this
passing the Penrosian 1-graviton threshold or whatever triggers state-vector
reduction. It then seems to me that within the code, "if" statements should
be able to read off whether a qubit is a 1 or 0 within a given branch,
particularly in the NMR version where a qubit represents more than one
particle.
At the physical level, after all, eigenstates are separate branches of
reality, evolving linearly (without interaction) and without any fundamental
distinction between whether or not something is a qubit. So as far as I can
tell, the only theoretical boundary to one-thread-per-eigenstate computation
is that measurement would turn RAM and the program counter into a hopeless mess.
Still, a creative operating system should be able to ignore this "scratch"
memory, pick up whatever result was left in the qubits, and figure out which
branch indicated success. Supposing that arbitrarily large probability
amplitudes for the qubits are possible, the probability amplitude could
increase exponentially with the success of a given branch. Otherwise, the
measurement might only be able to cut the search space by half, necessitating
repeated searches to read off the identity of the successful eigenstate/thread.
Given one-thread-per-eigenstate superposed computing, exponential search
simply requires a number of qubits equal to (log2(breadth))*depth for a direct
equivalence between branching on a choice and branching into a new physical eigenstate.
--
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