[Cryptography] How close we are to quantum crypto:

[cherry]

People who think that quantum cryptography is near notice that there 
have been immense improvements in quantum gates, many orders of magnitude.

The universal quantum gate reversibly transforms an input quantum state 
of three qbits into output quantum state of three qbits, and we are sort 
of able to build such gates, and an array of such gates can perform any 
reversible transformation on any number of qbits.

So, they think, just build a massive array of such gates to manage a two 
fifty two bit calculation, and we can crack the very widely used 
asymmetric encryption family **25519

We can build those gates now, so what is stopping every **25519 
encryption system from falling tomorrow morning, they ask.

Not so.  Quantum gates do not add up like that.  As you attempt to 
manipulate a state with more and more bits with state delocalized and 
non locally correlated over all the bits, it becomes more and more 
fragile.  An array of three bit gates manipulating a four bit state, 
each of which is very qood at keeping the state of three bits pure, but 
not perfect, adds up to four bit transformation that is very bad at 
keeping the state of four bits pure.

If we can easily build a three bit gate, then we can easily perform 
Shor's algorithm on a three bit number.

If we can build many very good three bit gates, we can perform it on a 
four bit number.  And by extraordinary and heroic efforts, a five bit 
number.

This is related to the classical problem of building reversible logic 
circuits out of mechanical gears.  Too many gear wheels, each of which 
has very low static friction, adds up to a system with very high static 
friction, which will lock up.

If you want to solve a reversible NP problem with mechanical gear 
wheels, you could build a polynomially sized array of gear wheels, 
which, if frictionless, could only spin in a way that corresponds to a 
solution of of the NP problem to which you want a solution.  Then you 
apply torque to one of the gear wheels.

And ... guess what.  It does not spin.

With many more order of magnitude improvements in the quantum character 
of gates. which are happening and are likely to continue to happen, we 
will eventually be able to crack a six bit number, which I expect to 
happen sometime around 2030, 2060 or so.

With continued rapid progress, eventually, after many decades of 
continued rapid progress, perhaps a seven bit number.

The cure for this scaling problem is quantum error correction, which 
would have the effect that instead of exponential difficulty, we would 
merely face polynomial difficulty, albeit a polynomial of alarmingly 
high degree.

Quantum error correction is a hard problem, and I just don't see much 
work in the published literature on it.  It just gets tossed in the too 
hard basket.  What I *do* see is a pile of published papers that glibly 
transliterate classical error correction to the quantum domain.  Quantum 
error correction just cannot work like that.

It is probably easier to publish bullshit on quantum error correction in 
the peer reviewed literature than anything substantive, because all your 
peers have also published bullshit, and anything substantive will 
implicitly piss on their bullshit.   And if you need to get a paper out 
because publish or perish, there is little alternative to writing 
bullshit.  Quantum error correction is hard, and there is no real 
incentive to do real work on it.

I know what a system that relies on quantum error correction should look 
like, and I have seen theoretical work on such systems, and some 
research into what is needed to actually realize such circuits in a 
physical device, but not a whole lot of it.  It is blue sky, far over 
the horizon research, and it does not fit into the "Quantum crypto is 
coming soon" narrative, which is where all the money is.