[Cryptography] information, Shannon, and quantum mechanics

[Jerry Leichter]

On Feb 25, 2015, at 10:10 AM, Stephan Neuhaus <stephan.neuhaus at zhaw.ch> wrote:
> If I remember correctly (which I might not!), you could do reversible computations with zero energy, in the limit.
Of course, "in the limit" tends to be "in the limit of arbitrary slowness" (adiabatic systems, where you let things get to equilibrium).

There are all kinds of interesting physical limits on computation found in the last couple of decades, and their interplay with computational theory is still not properly appreciated.  For example, consider the whole notion of "computable in principle".  There are problems - like the Halting Problem - that are not computable "in principle" by any (Turing) machine (which, by a hypothesis that we now accept as given without much thought - though it was the center of much debate 80 years or so ago - is equivalent to "by any meaningfully defined computation:).

At the other extreme are poly-time algorithms, which we for most purposes consider "easily" computable, though of course the constants and the exponent may be very large.

But there are problems that are computable "in (mathematical) principle" that *could not have been computed* if the entire universe were working on just that problem since the Big Bang.  Or that the entire universe could not compute in 100 years.  Or any similar bound.  These are computable "in principle" but not "in this universe".  Do we really still want to accept the "in principle" label for such things?

A while back on this list, I pointed out that if you wanted to break a K-bit key by brute force in 100 years, at the least, you needed to perform 2^K bit flips just to generate the possibilities.  "In 100 years" means your computation has to take place in a hypersphere in space-time of radius 100 light years, by 100 years time.  (This is a gross over-estimate:  If you want the answer to come back to *you*, the spatial size is limited to 50 light years.  But let's be generous.)  I had done a back-of-the-envelope estimate and came up with a QM limit for K of somewhere between 128 and 256.  I later asked a physicist I knew, and he did a more accurate estimate.  It turns out that this hypersphere could do about 2^315 bit flips - and store about 2^315 bits of information.  So AES-256 "can be broken in principle" in 100 years by brute force - but you don't need to make the keys all that much larger to eliminate that possibility.  :-)

While our ability to realize anything approaching the ultimate computer is nowhere in sight, we are already talking about real problems - like brute-force attacks on keys - that come close to those ultimate limits.  "In principle" computation should already be treated with respect....

                                                        -- Jerry