From: Robin Hanson <hanson@econ.berkeley.edu>

Date: Thu Aug 27 1998 - 14:49:55 PDT

Date: Thu Aug 27 1998 - 14:49:55 PDT

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

*
This archive was generated by hypermail 2.1.8
: Tue Mar 07 2006 - 14:45:30 PST
*