The Quantum Issue: What Quantum Computing Could Mean for Bitcoin

What is quantum computing? How does a quantum computer differ from a classical computer, and what relevance could the technology have for Bitcoin?

These are questions that new Bitcoiners inevitably encounter as they consider Bitcoin’s exposure to what could become an existential threat if a viable quantum computer is developed. The ability to own bitcoin rests on a foundational assumption: without directly obtaining a copy of a private key, no one other than the person who possesses that key can sign a transaction spending the coins it secures. Quantum computing calls that assumption into question.

Quantum computers are not simply “computers, but faster.” They operate in a fundamentally different way from classical computers and are therefore much more efficient at certain specific types of computation. This article does not attempt to explain quantum computing in exhaustive technical detail. Instead, it provides an intuitive explanation of how classical and quantum computers differ, particularly in how they handle large cryptographic key spaces.

Classical computers

Everything stored in a classical computer is represented as a series of 1s and 0s. Each bit is precisely either a 1 or a 0, with no ambiguity. Data is stored as 1s and 0s, and when that data is manipulated or modified, the operations are performed bit by bit and step by step.

A classical computer therefore modifies discrete, unambiguous pieces of data in a linear sequence. It cannot skip ahead or take a shortcut in the sequence of steps required by a computation. It must perform those steps one after another, even if more efficient mathematical methods can reduce the total work involved.

When a private key is generated on a computer, the device obtains a random value. That value could come from dice entered by a user, general user input, or randomness generated by the device’s hardware. The computer stores the value in memory as 1s and 0s. It then multiplies the private-key value by the elliptic curve’s generator point to produce a public key.

At its most basic level, this process consists of algorithmic instructions that specify which bits to use, how to modify them, and which physical circuits should process them. The resulting value is then placed back into memory after being modified bit by bit. Additional steps are required to arrive at a valid address, but those steps follow the same general pattern of sequential instructions that modify 1s and 0s in memory.

What would happen if someone tried to use a classical computer to guess another person’s private key?

There are 2^256 possible private keys. That is 115,792,089,237,316,195,423,570,985,008,687,907,853,269,984,665,640,564,039,457,584,007,913,129,639,936 possible keys.

A computer would have to test those private keys one after another, or test however many it could process in parallel, while following the same step-by-step instructions used to generate public keys. The more keys tested simultaneously, the more computing power would be required. There would be no shortcut around that cost.

Using less computing power would require more time. Reducing the time would require more computing power. With classical computing, the task is effectively impossible: the required computational cost exceeds the capabilities of every computer on Earth, while the time required is so great that every star in the universe would die before all possible keys were tested.

To achieve the objective, an alternative to checking keys sequentially or in parallel is necessary. That is where quantum computing becomes relevant.

Quantum computers

Quantum computers do not work with discrete states in the same way as classical computers. Their basic unit of information is the qubit, the quantum equivalent of a bit. Unlike a classical bit, which is either a 1 or a 0, a qubit exists in a superposition in which it can be both a 1 and a 0 simultaneously. It settles into one of those discrete states when it is observed.

Superposition is one of the key building blocks that enables quantum computers to calculate differently. Another is entanglement. Qubits are not necessarily stored in isolation. The physical atoms representing them can become entangled, meaning that when entangled atoms are observed and collapse into a single state, the entangled atoms collapse into the same state, regardless of how far apart they are.

The distinction can be understood intuitively by comparing algorithms. On a classical computer, an algorithm is a set of instructions that takes a specific arrangement of bits and modifies it step by step until it produces a final arrangement of bits. The algorithm transforms one discrete state into another through a sequence of operations.

Qubits do not store discrete states until observation causes them to collapse into one. Instead, they store probabilities. For a set of entangled qubits of a given size—2^256 in the hypothetical case considered here—each possible state has a particular probability of being the state into which the system collapses.

Quantum algorithms are therefore not simply step-by-step instructions for operating on fixed, discrete states. They provide instructions for operating on entangled qubits in a way that changes the probabilities of different outcomes. Constructive interference increases the probability of a correct outcome, while destructive interference reduces the probability of incorrect outcomes. This is not the same as the noise or interference that makes it difficult for physical quantum computers to operate accurately; it is a separate concept.

A classical computer would have to check individual private keys one by one to find the key corresponding to a specific public key. A quantum computer could instead run the appropriate algorithm a limited number of times and arrive at the correct answer. It would not do so by literally “checking all the possibilities at once.” Rather, it would modify the probabilities of the outcomes into which the superposition can collapse.

This is why a quantum computer could undermine the assumptions behind elliptic curve cryptography in a way that a classical computer cannot. It is also why quantum computers are useful only for certain types of computation, including problems involving a very large space of possible answers.

Don’t panic

The fundamental difference between classical and quantum computation means that, if a viable quantum computer were produced and functioned correctly, the underlying assumption securing individual Bitcoin holdings would be broken. Those funds would be insecure.

This would be a serious risk if such a device were manufactured and worked as required. However, Bitcoin is not entirely unprepared. The problem and the potential exposure are understood, and numerous possible solutions addressing different aspects of the issue are coming together.

Breathe and relax. The rest of this issue examines the broader problem in detail.

This piece is featured in the latest print edition of Bitcoin Magazine, The Quantum Issue. It is being shared online as an early look at the ideas explored throughout the full issue.

The article first appeared on Bitcoin Magazine and was written by Shinobi.