Sunday, January 7, 2018

Breaking Bitcoin With a Quantum Computer

From Fortune:
Alex Beath, a Toronto-based physicist and pension fund analyst, is skeptical about Bitcoin but sees one useful purpose for the crypto-currency: It may detect when someone creates a working quantum computer.

“The second someone creates a viable quantum computer, the NP-complete math problems at the heart of Bitcoin mining tech become instantly solvable,” Beath notes. “In other words, one answer to the question ‘what's the first thing you'd do with a quantum computer?’ is ‘mine all of the remaining Bitcoin instantly.’ Until that happens, nobody has a quantum computer.”

Beath’s off-the-cuff observation, which he made in response to a Fortune query about the security of bitcoin, is amusing. But it also underscores a serious problem: Namely, a new era of computing is fast-approaching and when it arrives, the system that gave rise to many crypto-currency fortunes will collapse.

This threat to Bitcoin and other software systems that use the same underlying encryption technique--a technique likely to crumble in the face of a quantum-based attack--is not new. Indeed, it was predicted decades ago, and Ethereum founder (and former journalist) Vitalik Buterin wrote about how to defend it in 2013.

The difference today, though, is that companies like Microsoft, Google and IBM are making rapid breakthroughs that could make quantum computing viable in less than 10 years.
Right now, engineers are stymied over how to deploy enough “qubits” (a quantum version of the binary bit system used in traditional computers that lets a unit be a 0 and 1 simultaneously) in a stable fashion.

According to CEO Louis Parks of SecureRF, which is developing quantum-resistant security systems, the number of qubits in a machine has recently soared from 16 to 50. This is far from the 4,000 to 10,000 that would likely be needed to crack Bitcoin’s cryptography but, at this point, Parks says quantum computing is now at stage akin to when the Wright brothers began showing airplanes were viable....MORE
Recently (January 3rd):

One More Reason Cryptography May Not Stand Up to Quantum Computers
Twelve weeks ago we were reading "Google Just Revealed How They’ll Build Quantum Computers":
... A quantum computer with a mere 50 qubits would outclass the most powerful supercomputers in the world today. Surpassing the limits set by conventional computing, known as achieving quantum supremacy, has been a difficult road. Now, a team of physicists at the University of California Santa Barbara (UCSB) and Google have demonstrated a proof-of-principle for a quantum computer that may mean quantum supremacy is only months away....
Two weeks after that piece in Futurism we saw this at New Scientist:

Google’s quantum computing plans threatened by IBM curveball
...IBM has come up with a way to simulate quantum computers that have 56 quantum bits, or qubits, on a non-quantum supercomputer – a task previously thought to be impossible. The feat moves the goalposts in the fight for quantum supremacy, the effort to outstrip classical computers using quantum ones.

It used to be widely accepted that a classical computer cannot simulate more than 49 qubits because of memory limitations. The memory required for simulations increases exponentially with each additional qubit.

The closest anyone had come to putting the 49-qubit limit to a test was a 45-qubit simulation at the Swiss Federal Institute of Technology in Zurich, which needed 500 terabytes of memory. IBM’s new simulation upends the assumption by simulating 56 qubits with only 4.5 terabytes....
Well, at ten weeks old that's ancient history.
From Next Big Future, December 30:

Progress to turning silicon transistors into qubits which could enable billion qubit quantum computers....

....MORE