From: Hal Finney <hal@rain.org>

Date: Tue Dec 09 1997 - 11:27:02 PST

Date: Tue Dec 09 1997 - 11:27:02 PST

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

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