Preparing for that mythical quantum computer

SciAm and Nature magazine have today's crypto scare story:

Cryptographers Brace for Quantum Revolution
Encryption fix begins in preparation for arrival of futuristic computers

It is an inevitability that cryptographers dread: the arrival of powerful quantum computers that can break the security of the Internet. Although these devices are thought to be a decade or more away, researchers are adamant that preparations must begin now.

No, it is not inevitable. Those devices are centuries away, if ever. So what researchers are adamant?

But on the day that the first large quantum computer comes online, some widespread and crucial encryption methods will be rendered obsolete. Quantum computers exploit laws that govern subatomic particles, so they could easily defeat existing encryption methods.

“I’m genuinely worried we’re not going to be ready in time,” says Michele Mosca, co-founder of the Institute for Quantum Computing (IQC) at the University of Waterloo in Canada and chief executive of evolutionQ, a cyber-security consulting company.

Oh, someone at the Institute for Quantum Computing is worried. He is so worried that he is doing fundraising to get everyone else worried.

At the time, it was not clear whether such a machine would ever be built, says Mosca, because researchers assumed that it would need to operate flawlessly. But a theoretical discovery in 1996 showed that up to a limit, a quantum computer with some flaws could be just as effective as a perfect one.

He is talking about error-correcting qubits, when no one can make scalable qubits anyway.

Published experiments with small quantum devices are starting to approach this faultiness threshold, notes Mosca. And because secretive organizations such as the NSA are keenly interested in the technology, it is widely assumed that these published results do not represent the cutting edge of research. “We have to assume there’s going to be people that are a few years ahead of what’s available in the public literature,” says Mosca. “You can’t wait for the headlines in The New York Times to have your plan in place.”

This is one situation where the NY Times stories are way ahead of the research. By centuries.

Researchers believe that it takes existing computers a long time to factorize big numbers, partly because no one has yet discovered how to do it quickly. But quantum computers could factorize a large number exponentially faster than any conventional computer, and this nullifies RSA’s reliance on factoring being difficult.

Aaronson likes to point out that it is not really exponential faster.

This is like saying that we need to build more nuclear bomb ICBMs because Russia might be building a missile defense. Or that we must pass laws about time travel, just in can someone builds a time-travel machine. Someday books will be written about how all these smart people and money chased an impossibility.