Neohapsis is currently accepting applications for employment. For more information, please visit our website www.neohapsis.com or email hr@neohapsis.com
Crypto Archives: Re: Universal Quantum Computers

Re: Universal Quantum Computers

Subject: Re: Universal Quantum Computers
From: Mike Rosing (eresrchmendota.terracom.net)
Date: Wed Dec 01 1999 - 17:42:26 CST

On Wed, 1 Dec 1999, Bill Stewart wrote:

> Mike - I don't know if you'd know this, or if not,
> I'd appreciate pointers to people who would -

Check out the Los Alamos papers:

> Are quantum computers limited by the Heisenberg Uncertainty Principle?

Yes :-)

> If so, then their maximum precision is about Planck's Constant,
> which is about 140 bits (as opposed to the current precision of ~3 bits :-)

Whoa!! What's the maximum precision of Plank's constant have to do
with anything? Just because we can only measure it that well, doesn't
mean it has any less than infinite number of bits to fully describe it.

> This means that we may have to add a few more bits to our key lengths,
> and cracking too-short keys becomes immensely faster,
> but it doesn't fundamentally change the usefulness of public-key crypto,
> either factoring-based systems like RSA or discrete-log like DH.
> (I don't know if it means that primes need to be 140 bits longer,
> or if they need to be factoring-equivalent-workload-to-140-bits,
> which is probably about 1000-4000 more bits, but either way it doesn't matter,
> because it's just a small multiplier to the workload.)

The uncertainty principle relates to the coherency problem. It has
nothing to do with the number of qubits you can work on. Of course,
the more qubits, the worse the coherency is. But at present people
are thinking in terms of individual qubits and gates. In the future,
we'll have all the qubits in one "gate". If we can get 1000 qubits
in one gate, they all interact and we can set up the gate to solve
a 1000 bit RSA (or ECDLP) problem in one "clock". I'm putting this
stuff in quotes because they are conceptual, not presently realizable.

> The technical meaning of being limited by Heisenberg is that
> you have one device that can handle a waveform with
> 2**N superpositioned states and collapse it into the correct N bits.
> If you've got two devices in parallel, then probably they can do
> 2*2**N states, i.e. N+1 bit answers, which is no problem.
> But if there's a way to get them to do 2**N * 2**N,
> i.e. 2**2N states and 2N bits of answer,
> without violating Heisenberg's for large N, then you have results
> that violate the little I remember of college quantum,
> and they _can_ affect the use of public-key crypto.

Right. At the ECC '99 conference there was a talk by a professor who
specializes in QC's. He said all PK's would fall if a QC could work.
He also seemed to think that the number of qubits would grow at a
rate of about 1 per year for the next 50 years. 50 qubits won't
crack anything, so for all practical purposes QC's won't be a threat
for any PK systems in the next 100 years.

I don't think that's correct, but the following is pure conjecture.
Once we get gate sizes in the 10 angstrom level, we'll be doing
quantum mechanics across the entire structure of a set of gates.
We're now at the 100 nm == 1000 angstrom level. Since gates go
as area, it takes 3 years by Moore's law to halve the linear dimension.
So in 7*3 = 21 years we'll be down to the 10 angstrom level. I think
we'll learn a lot about quantum effects at that point, and to keep
Moore's law on track we'll start developing quantum computers.
At the 1 angstrom level, we'll have to increase the number of bits
per atom, and that's when quantum computers will be fully operational.
That's only 30 years from now (give or take 3).

So I might live to see it, which would be really cool!

Patience, persistence, truth,
Dr. mike

This archive was generated by hypermail 2b27 : Wed Dec 01 1999 - 19:56:47 CST