[Cryptography] quantum computers & crypto

[cherry]

On 10/26/21 7:52 PM, Peter Gutmann wrote:
> 15 was factored with Shor's algorithm twenty years ago, 21 was factored just
> under a decade ago.  Drawing a line through these two data points (yeah, I
> know, but it's all we've got), we can see that 1,024-bit RSA will be
> vulnerable to Shor's algorithm some time around 4,000 AD.  However this
> ignores two problems:
> 
> The first is that, like FTL travel, things get much, much harder as you scale
> up.  So the line likely isn't straight, and may in fact never reach 1,024
> bits.

If you are straightforwardly using regular gates, each additional qbit 
is exponentially more difficult, with a large exponent.  The cost and 
difficulty of an quantum computer is something like `exp(a*N)` where N 
is the number of bits.  The way things have been going, it looks like 
each additional bit is something like ten to a thousand times more 
difficult than the last.  Could be worse than that.

This can be addressed by quantum error correction, which drops the 
difficulty of increasing the the number of qbits down to merely 
polynomial rather than exponential.

Quantum error correction, however, is not just a matter of implementing 
ordinary error correction in ordinary gates.

What you want is that the forbidden states are strongly coupled to the 
heat sink, and the permitted states are completely uncoupled from the 
heat sink.  Implementing this as a physical reality is at present just a 
gleam in the eyes of researchers.  They have some ideas of how it could 
be done, but no one has actually proposed a physical device.

We have lots of nice mathematics about quantum error correction, it is 
easy to produce publishable papers about it, but no idea how to embody 
it physically.  Any paper that proposed a physically realizable 
implementation would be talking about temperature, heat flow, and 
coupling between degrees of freedom.  It would look like a 
thermodynamics of bulk materials paper, not a quantum computing paper.