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

Date: Tue Dec 09 1997 - 11:48:35 PST

Date: Tue Dec 09 1997 - 11:48:35 PST

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

*>
*

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

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

The search result is more solid, with tight upper and lower bounds.

And search seems to me more applicable to Tipler's goal of simulating

all past possible lives.

*>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. ... The problem as I understand
*

*>it is insufficient mass-energy within a lightspeed limited boundary to
*

*>hold an infinite number of states.
*

Exactly.

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 19:42:40 1997

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