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

Date: Tue Dec 09 1997 - 10:35:42 PST

Date: Tue Dec 09 1997 - 10:35:42 PST

At 09:45 AM 12/8/97 -0800, you wrote:

*>Tipler rejects earlier arguments that open universes will allow infinite
*

*>computations (I think Freeman Dyson had suggested this). While Dyson
*

*>showed that you can theoretically continue calculating forever, Tipler
*

*>says that the number of states your computer can fall into is finite. ...
*

*>What I was wondering is whether the new ideas in quantum computing
*

*>could provide a way around this. Quantum computers can be thought of as
*

*>spanning multiple parallel universes, in the many worlds interpretation.
*

*>In a sense, these multiple universes work together to produce a useful
*

*>result in each component universe which could not have been done within
*

*>that amount of time using just that universe's resources. With n quantum
*

*>bits you can perform two to the n calculations (although combining the
*

*>results can not typically be done with perfect efficiency).
*

I don't think this is the right intuition about quantum computing. Take

the example of searching for one item matching certain criteria out of N.

A classical computer with log2(N) bits takes about N steps do do this,

and a quantum computer with log2(N) qbits takes about sqrt(N) steps.

These are strict lower bounds. The 2^n intuition, however, would suggest

the quantum computer could do it in constant time. I think a better

intutition is that a quantum computer gives you access to N^2 "classical

universes", really N^2 relative phases between each classical system.

N^2 is more states than N, but I don't think its enough to get by the

finite local state problem in an open universe.

Anders mentions reversible computing, but I think that even more obviously

doesn't help you avoid the finite local state problem.

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 Tue Dec 9 18:29:45 1997

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