Commercializing fundamental technology is hard, but commercializing quantum computers is up there with Henry Ford, the Wright brothers and Elon Musk in persevering with ideas that were initially mocked.
“Heavier-than-air flying machines are impossible.”
–Lord Kelvin, 1895.
“Quantum computers are pure science fiction ”
–Leonard Mevchin 2005
Quantum computers are real and at 10M USD a pop it looks like they will soon be viable commercially on a large scale also. Is there anyone out there who thinks that, based on historical precedent and the acceleration of technological progress that we won’t have desktop quantum computers in our lifetimes?
“I think there is a world market for maybe five computers.”
–Thomas Watson, chairman of IBM, 1943.
“Your mobile phone has more computing power than all of NASA in 1969. NASA launched a man to the moon. We launch a bird into pigs”
– George Bray
The one thing we can be sure of is that one of the first targets will be the RSA algorithm as it based on integer factorization, something that can be easily parallelized and perfectly suited for a quantum computer. Despite all the lofty talk about protein folding and complex radar systems there is no doubt that cracking RSA will be a key target.
Here’s the good news: KSI is future proof against quantum computing as it is based on hash function cryptography The so-called Grover’s search algorithm reduces pre-image finding from O(2^n) to O(2^(n/2)), i.e. inverting a hash function with a quantum computer is as hard as finding collisions with ordinary computers.
The so-called Brassard-Hoyer-Tapp algorithm was for a long time believed to reduce collision-finding from O(2^(n/2)) to O(2^(n/3)). As KSI security proofs are based on collision-resistance, this would roughly mean that we would have to use 1.5 times bigger hash functions in the case a quantum computer is built.
However, Daniel J. Bernstein showed that when implemented in practice, the Brassard-Hoyer-Tapp algorithm will not give any advantage over traditional Birthday-paradox based collision search algorithms on ordinary computers.
To our knowledge, there are no methods known how to search for collisions with quantum computers faster than it can be done with ordinary computers. So, our security proofs still work and we do not have to increase the output size of the hash function, even if you have a quad core quantum computer on your iPhone.
“Lockheed Martin pays reported $10-million for D-Wave System’s quantum computer”
–Vancouver Sun April 2013