Re: poly: Infinite calculations in an open universe?

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