poly: Quantum Computing AI

Science, 7Aug98, p792-4, had a nice summary of the state of
quantum computing. Apparently there are two prototypical
computations, search and counting, and all computations can
be thought of as a combination of these. Quantum computing
speeds up search from N to sqrt(N) cycles, but doesn't speed
up counting at all.

A big obvious question is how smart and fast can AIs based
on quantum computing be, which raises the question of the
relative importance of search vs. counting in AI computation.

Now on first glance AI seems to be based almost entirely on
search. That's the standard metahpor, with things that aid
search themselves get better via meta-level search. What if
things turn out to be this nice, with AI being all search?

Imagine that an instruction cycle is three nanoseconds, that
you could describe a similated world for an agent to interact
with, and that you have a decent general learning approach, so
that a classical machine would eventually get smart after N
years in that simulated world. (And that AI is all search.)

N years is N*10^16 cycles, so a quantum computer with the same
instruction cycle time would get smart after sqrt(N)*10^8 cycles,
or sqrt(N)*10^-8 years. That means that if the classical computer
took 10^16 = 10,000 trillion years, the quantum computer takes
one year! And if the classical computer took a million
years, the quantum one would take about five minutes.

But what if the program can't do it from start to finish without
outside contact? What if it needs data from the real world,
such as feedback from people? Imagine that the classical
computer that would take N years would need feedback every
M hours (= M*10^12 cycles). Then the quantum computer would
need feedback every sqrt(M)*10-6 hours, and would take a total
of (N/sqrt(M))*10^-6 years.

For example, if a classical computer could get smart in a million
years with feedback every hour, then the quantum computer would
take one year total, but require feedback every three milliseconds.
But if the classical computer would require feedback every third
of a second (= 10^8 cycles), then the quantum computer would take
a century, and require feedback every 30 microseconds.

The bottom line is that if big quantum computers can be built,
how long it takes to make a really smart machine seems to depend
mostly on an ability to design the right virtual environment
inside the machine, and on making outside interactions as
infrequent and fast as possible.

Robin Hanson
hanson@econ.berkeley.edu http://hanson.berkeley.edu/
RWJF Health Policy Scholar, Sch. of Public Health 510-643-1884
140 Warren Hall, UC Berkeley, CA 94720-7360 FAX: 510-643-8614
Received on Thu Aug 27 21:38:58 1998