Re: limit speed of computation - Digital vs. Quantum

From: Kent Paul Dolan (xanthian_at_well.com)
Date: 10/13/04 

Date: Wed, 13 Oct 2004 20:45:04 +0000 (UTC)

"valentin tihomirov" <spam@abelectron.com> wrote:

> IMO, the issue consers[???] the QM much stronger
> as it is clear which of the 2^N integers are
> factors of a number in a classical device but
> ob[t]aining the answer(s) f[ro]m 2^N universes of
> QC is an issue, IMHO.

Umm, if I understand correctly, that's not how QCs
work at all. You run the device, and with some
high probability of correctness depending on the
redundancy of its design, it returns the single
"right" answer. There is no need to get in your
parallel universe exploration vehicle and go kiting
out to _retrieve_ the answer, you just want to have
chosen to live your life in one of the vast majority
of universes where the answer that appears is the
correct one.

In the case of integer factoring, that answer is
a certificate checkable in polynomial time. If it
proves to be the wrong answer when checked, just set
up your problem on the QC and run it again.

If your QC is appropriately scaled with redundancy
appropriate to the size of the problem, the "run,
check, repeat" loop will return a correct answer in
all but a vanishingly small set of runs, too small
to be expected for even one to occur in human
history, and will find that answer very quickly
compared to normal computation [which in the real
world has similar "only probablistically correct"
problems due to alpha particle emitting decays
destroying data bit by bit, versus parity correction
hardware restoring data word by word, in endless
battles].

So you end up with QC being something like
quicksort, which has spectacularly lousy worst case
behavior, but is still the overwhelmingly popular
tool of choice for the normal case: you just don't
know in advance that your problem is "the normal
case", and make a conscious decision to live with
occasional disappointments as a tradeoff for the
average behavior's benefits.

I can, of course, be completely incorrect in this
understanding; I am but an egg, even if an
ususually arrogant egg.

xanthian. 

-- 
Posted via Mailgate.ORG Server - http://www.Mailgate.ORG