Re: Quantum computing

Eliezer S. Yudkowsky (sentience@pobox.com)
Mon, 14 Sep 1998 12:41:24 -0500

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

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.