From: Hal Finney (hal@rain.org)
Date: Sun Feb 02 1997 - 18:38:46 MST
From: Eliezer Yudkowsky <sentience@pobox.com>
> Ah. Then given 64 qb, you could search every 1000 consecutive digits of
> pi for hidden messages for the first sixteen billion billion digits of
> pi, in (of course) the same time it would take to search any 1000
> digits.
I need to learn more about how quantum computers would work, but I don't
think it is quite this easy.
I understand that there have been some algorithms proposed which speed
up search operations on a quantum computer. The main reference which
I have seen mentioned is Grover, "A fast quantum mechanical algorithm for
database search", Proceedings of STOC96. I haven't read this paper,
but I've seen it summarized as follows:
You want to search a database of N items for one of S items which
satisfies some criterion. Normal search would require about N/S checks.
(For example, there are 100 items, and 4 of them are good; you'll
have to check about 25 items before finding a good one.) Grover's
quantum algorithm does it with the square root of this many checks.
(Your computer would only have to check about 5 items using quantum
parallelism in this example.)
This is a considerable speedup but is not fully parallelized in
the naive sense. We might think of a quantum computer as one which
simultaneously checks every possibility. In that latter case it should
take just one fully-parallel check. We don't get that, but we do get
a speedup.
It's not clear a priori that the problem of searching for patterns in that
huge chunk of pi matches Grover's formulation, but even if it does then
it would take 2^32 checks (compared to 2^64 on a conventional computer)
or four billion times longer than is stated above. That's still a lot
faster than doing it without quantum parallelism, of course, but it's
not as dramatic as what was described.
Also, I think you will need a lot more than a single 64 qubit register
to execute the calculation. This register, as I understand the proposal,
is an index which specifies which block of 1000 digits in pi's expansion
to test. But the test itself is undoubtedly a complicated mathematical
program. I would expect that considerably more storage space will be
needed to represent all the intermediate values needed for the algorithm.
So, while quantum computers will be remarkable things if they can be
built, we should try to keep a sense of realism in terms of what they
will be able to do. They don't give us full access to the Everett
multiplex. Tricky algorithms can give us some speedups, but there are
many limitations at present.
Hal
This archive was generated by hypermail 2.1.5 : Fri Nov 01 2002 - 14:44:07 MST