quantum chip built

bear bear at sonic.net
Tue Jan 17 13:31:33 EST 2006

On Sat, 14 Jan 2006, Michael Cordover wrote:

> In order to factor a 1024
> bit modulus you'd need a 1024 bit QC.  Perhaps if there were some sudden
> breakthrough it'd be a danger in a decade - but this is the same as the
> risk of a sudden classical breakthrough: low.

This is not necessarily so.  In order to factor a 1024-bit
modulus using Shor's algorithm, you would indeed need a 1024-
qbit machine.  But we haven't seen what fruit may be borne by
algorithm research and hybrid machinery; it seems plausible
that a hybrid machine may be able to use, say, 16 qbits to
divide the work factor of factoring large numbers in general
by approx. 65536.

In general, I think that until QC is a mature field, cryptographers
and cryptologists ought to assume that some QC or hybrid algorithm
or machinery that may be discovered "any minute now" can
simultaneously exploit the strengths of both QC and classical
computation.  And that means, in general, that I'd want to *add*
the number of bits factorable by Shor's algorithm in the foreseeable
future to the number of bits factorable by classical brute-force

In fact, maybe we ought to be worried about synergistic effects
and multiplying the figures together, although I can't imagine
where such effects would come from.  Let us say simply that Quantum
Computing is far from mature, and at this moment we are only
beginning to understand it.  I remember all the mechanical engineers
who proved that no heavier-than-air flying machine could exist
back in the 19th century, back when knowledge of mechanics and
materials was less precise than now...  And these guys knew what
there was to know about it.  I'm chary of people "proving" that
no n-bit factoring machine can be built just because the way they
already know to build one (Shor's algorithm, which requires n qbits)
won't work.  Given that our knowledge of QC is nascent, our
ignorance of QC's practical limits is likely staggering, and
caution is to be advised.


The Cryptography Mailing List
Unsubscribe by sending "unsubscribe cryptography" to majordomo at metzdowd.com

More information about the cryptography mailing list