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