Re: poly: Infinite calculations in an open universe?

Robin Hanson, <hanson@econ.berkeley.edu>, writes, regarding
the possibility that quantum computing would enable infinite computations
in an open universe:

> 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.

This is true for searching, however other special algorithms
have better improvements. Shor's algorithm for factoring takes
time quadratic in the length of the input, while the best known
conventional algorithms take time exponential in that length. [Ref:
http://chemphys.weizmann.ac.il/~schmuel/comp/comp.html ]. So in this
case the quantum computer gives an exponential speedup.

Granted, this is a special case, and it is not yet known how much quantum
computing will help for other algorithms. It may well be that the
square-factor speedup for searching is more typical for what we will see
in general. No doubt more results will be coming to light before long.

One concern I have is that even if quantum computers provided exponential
speedup, the real issue with the Dyson cold universe is not a matter
of computing speed. Dyson showed that there is enough time and energy
to do an infinite number of computations. The problem as I understand
it is insufficient mass-energy within a lightspeed limited boundary to
hold an infinite number of states. Essentially you need an unbounded
amount of matter/energy to be available, otherwise you get a Poincare
recurrence and you are thrown into an infinite loop.

I don't think quantum computers help much with data storage. With N
qubits you can have 2^N states, but you can hold 2^N different values
with N regular bits too. The difference with the qubits is that you can
hold all the values at once, but it's not clear that that is a useful
form of storage.

The greater efficiency of quantum computers may reduce data storage needs
somewhat via standard computer science time/memory tradeoffs. But I
don't see how they would drastically improve effective storage capacity.

Hal
Received on Tue Dec 9 19:34:36 1997