View Single Post
Old 07-15-2017, 03:01 AM
Francis Vaughan is offline
Join Date: Sep 2009
Location: Adelaide, Australia
Posts: 4,981
Quantum computing gets held up as the great destroyer of crypto. However, as noted earlier, there is are no extant physical realisations of even the most trivial building blocks from which a quantum computer capable of performing the needed factorisations are built. The attack on crypto is based upon factorisation using Shore's algorithm, which is in turn built atop the Quantum Fourier Transform. The existence proofs of the idea are built on quantum systems that cannot scale. The only existing quantum computer is the D-Wave, and some would suggest it isn't actually a real quantum computer. (From the little playing about I have done with one I have an open mind on this, but would hesitate to claim it is one.) It cannot perform Shore's algorithm, and it isn't even clear it can really outrun a conventional computer. Its ability to solve a version of simulated annealing is interesting, but casting problems in a form it can usefully attack is non-trivial. My main cynicism about large scale factorisation ever being possible is the intrinsic noise in the system. For a successful factorisation every qbit needs to resolve to the right value. Repetition of the factorisation operation can help resolve things, but the entropy is not going to be small, and as the number of bits increases you will be fighting exponential growth in the number of repetitions needed. Which is just what you don't want. Just as increasing the number of bits eventually defeats the largest scale conventional attacks, it will IMHO defeat quantum attacks.