What Is Quantum Computing?

Quantum computing is a form of computing based on quantum physics. Where classical computers rely on bits (zeros or ones) to make calculations, quantum computers use quantum bits (qubits) that leverage quantum mechanics to exist in a “superposition”: a combination of zero and one, with some probability for each. A qubit could, for example, have an 80 percent chance of being zero, and a 20 percent chance of being one. Or a 60 percent chance of being zero, and a 40 percent chance of being one. And so forth.

The idea of quantum computing was first introduced by physicist Paul Benioff in the 1980s. A little later, theoretical physicist Richard Feynman and mathematician Yuri Manin were the first to suggest that quantum computers could solve problems that are out of reach for classical computers. Indeed, in the 1990s, mathematician Peter Shor developed an algorithm that a quantum computer could use to break public-key cryptography: “Shor’s algorithm” — if quantum computers ever got strong enough.

In October 2019, after decades of research, Google officially claimed that it had reached “quantum supremacy.” This essentially means that a quantum computer solved a problem that a classical computer could not have solved. Or, to be more specific, it solved a problem in 200 seconds that would have taken even the strongest classical supercomputer 10,000 years to solve.

While this was a big breakthrough, quantum computers still seem to be a long way off from running Shor’s algorithm. For one thing, current quantum computers are not nearly strong enough for this, and it’s unclear how easy or hard it is to scale the technology up. Furthermore, to actually be useful, quantum computers depend on a technical solution called “error correction,” and this is still a challenge as well.

Predicting future development of this technology is hard, but quantum computers that can run Shor’s algorithm are likely years or even decades away — perhaps they will never even be possible at all.

Is Quantum Supremacy a Threat to Bitcoin?

If quantum computers get to the point where they can run Shor’s algorithm and break public-key cryptography, Bitcoin could indeed be subject to attack. Specifically, a number of coins could be subject to theft.

Some argue that the theft would be somewhat limited, however. While all coins are secured by public-key cryptography (currently, the ECDSA algorithm), most coins are also secured by the SHA256 hashing algorithm. Only if both of these algorithms are broken could all coins be stolen outright, but it does not currently seem as if SHA256 (or any other hashing algorithm) can be broken by quantum computers.

That said, a very large amount of coins is only secured by public-key cryptography. Current estimates suggest that around 5 million bitcoin would be subject to theft if public-key cryptography were broken. These are some of the situations in which bitcoin may be at risk:

• Bitcoin that were sent directly to a public key instead of a Bitcoin address and that haven’t been moved since. This includes many of the coins that were mined in the first two years of Bitcoin’s existence. (Many of these coins are often attributed to Satoshi Nakamoto, but it’s not clear that this is accurate.)
• Bitcoin that are held in reused addresses. Once bitcoin has been spent from an address, the public key of that address has been revealed, and if any more bitcoin are sitting in the same address, the funds could be stolen. This is one reason that address reuse is discouraged (though the main reason for this is to maintain privacy).
• Bitcoin held in wallets that share their public keys (typically, the extended public key) with a server, so the server can inform the wallet when coins are received.
• Bitcoin held in an address from which the forkcoin-equivalent (like BCH or BSV) has been spent.
• Bitcoin that are held in slightly more complex smart contracts, as all parties in such a contract typically know all of the relevant public keys.

In fact, even when bitcoin is protected with both a public key and a hash, it could be a challenge to spend such bitcoin safely in a “quantum world.” When a user tries to spend their bitcoin and transmit the transaction over the Bitcoin network, the attacker would have a window of opportunity to try and steal the funds. At that point, the attacker could try to break the public-key encryption before the transaction confirms and then resend the bitcoin to one of his own addresses.

Suffice it to say, if quantum computers suddenly became much stronger than anyone had anticipated, Bitcoin would have a problem.

It should be noted that if quantum computers that can run Shor’s algorithm suddenly appear, Bitcoin is unlikely to be the first or main target. Public-key encryption protects pretty much all other digital information in the world, including military intelligence, bank data and the rest of the existing financial infrastructure, communication networks and more.

Can Bitcoin Be Upgraded to Become Quantum Resistant?

Yes, the Bitcoin protocol can be upgraded to become quantum resistant.

In short, Bitcoin’s signature algorithm would have to be replaced with a quantum-resistant signature algorithm. Since activation of Segregated Witness, Bitcoin’s signature algorithm can be replaced relatively easily through a backwards-compatible, soft fork upgrade. (The current ECDSA signature algorithm might be partially replaced through a soft fork by the Schnorr signature algorithm in the near future.)

After the upgrade, users should migrate their bitcoin to new addresses in order to be protected by the quantum-resistant signature algorithm. Users that don’t migrate in time, before quantum computers can run Shor’s algorithm, would run the risk of their bitcoin being stolen in some way or another.

The Bitcoin protocol could potentially also be upgraded to block bitcoin from being spent at all, if they aren’t moved to a safe address in time. This measure would mean that the original owner would lose the bitcoin as well — but, of course, they would probably lose the bitcoin to an attacker anyway. (It’s been suggested that these bitcoin could potentially be unlocked by their rightful owners through Zero-Knowledge Proof cryptography — but this is all very speculative still.)

Given the current state of development of quantum computing, it’s expected that Bitcoin will have sufficient advanced warning that an upgrade will need to happen. Experts believe that we aren’t anywhere near that point in time yet.

Could Bitcoin Mining Be Broken?

Quantum computers might be able to mine bitcoin faster than classical computers. However, because bitcoin mining is based on hashing (not on public-key cryptography), it would probably not be broken to any meaningful extent.

Rather, the advent of quantum computing could lead to a new arms race to build the fastest mining hardware, up to the point where a new equilibrium is found. Similar evolutions of the bitcoin mining landscape have already happened when GPUs took over from CPUs and when ASICs took over from GPUs.