Quantum computer algorithms have the ability to factor in large numbers. Once large quantum computers become available, standard public key cryptographic protocols will be easy to break. This includes elliptic curve crypto, elliptic curve point pairings, and factoring RSA.
One way I like to look at quantum computer technology is to compare transistors to qubits. Transistors can be on or off. Qubits can be in a superposition of on and off at the same time. In both cases, you can’t build a computer until you have enough transistors or qubits to create a gate. It is the combination of gates that allows computation to happen.
The classic example of a transistor gate is the NAND gate. The output is high unless both inputs are low. All other gates can be created using a combination of NAND gates and fixed voltages (high or low). An example of a NAND gate built from CMOS transistors is shown here:
Transistors M1 and M2 are N-type, and transistors M3 and M4 are P-type. When both inputs A and B are high, output Y is low. In all other cases, output Y is high.
Modern computers have tens of billions of transistors which boils down to billions of gates. This makes them powerful and gives us the ability to communicate and invent in ways never before possible in human history.
Unfortunately, the term “gate” used with quantum qubits has two meanings. The meaning I have in the first figure is that several qubits can perform an operation with some number of inputs and an output. I would like to describe the Toffoli gate, which uses three qubits. Two are inputs and one is an output.
The figure of the Toffoli gate shows two control qubits A and B with a third affected qubit C. The control qubits do not change. The output qubit is the result of A AND B exclusive or with qubit C.
In quantum mechanics, the state of an object is mathematically described using “bra” and “ket” notation to bracket wave functions. For this article, we’ll just use the ket notation with |0> being an off-state and |1> being an on-state. The combination of a single qubit will be some amplitude of each state a|0> + b|1> where |a^2 + b^2| = 1. The values a and b are complex numbers.
The construction of a Toffoli gate requires transformations of the qubits using single “gates” that only operate on one qubit. It also uses the “controlled not” gate which uses one control and one output qubit. The single gates are essentially rotations of the on and off states. Let’s look at the controlled not gate first because this is the same as an inverter in a classical logic sense.
If the control (c) bit is a 1, the output bit (t) is flipped. In a quantum computer, the control bit (c) and target bit (t) create a superposition of states. The ket notation is |ct> for the overall state of the qubits. The input state can be written as a|00> + b|01> + d|10> + e|11>. After passing through the CNOT gate the output becomes a|00> + b|01> + e|10> + d|11>. The magnitudes associated with the last two states are flipped.
The single-gate transformations include the Hadamard gate with the symbol:
For qubit input a|0> + b|1> the output from an H gate will be (a + b)/sqrt(2) |0> + (a - b)/sqrt(2) |1>. Note that the magnitude of every qubit state is always 1. None of the transforms changes that magnitude.
The phase gate has the symbol:
For qubit input a|0> + b|1> the output from an S gate will be a|0> +i b|1>. This is a bit mind-bending because only the magnitude associated with the |1> state is rotated 90 degrees.
The T gate which rotates 45 degrees has the symbol:
For qubit input a|0> + b|1> the output from a T gate will be a|0> + exp(i \pi / 4) b |1>. This is a weird operation because only the |1> state is rotated 45 degrees.
The rotation concept works really well in the complex plane. The math used to describe these gates assumes all operations take place on the complex plane. Complex conjugation is also used. The dagger symbol is used to indicate complex conjugation along with a transpose of the matrix representing an operation. I’m ignoring the matrix math here - it’s fun but not necessary to get the point across.
Implementing a Toffoli gate requires the use of many CNOT and transform gates as shown here:
The Toffoli gate is one of the simplest quantum gates used to create a quantum computation. And it’s pretty complicated. Each transform is either an operation using RF equipment or a laser to change the state of an atom, electron, or photon.
The representation of gate construction does not do justice to the complexity of building these devices in reality. As the operations proceed from left to right in the figure, noise can break the quantum states to the point where all information is lost. Almost all quantum computers today are run at temperatures below liquid Helium to reduce this noise. So in addition to being hard, it’s expensive. In fact, I can’t find an example of a constructed Toffoli gate in any experiment.
In the paper “Quantum resource estimates for computing elliptic curve discrete logarithms” (https://arxiv.org/abs/1706.06752) the authors show that approximately 10^11 Toffoli gates are needed to break 256-bit level ECDLP. That’s about 2^33 gates, which is an easier number to use when thinking about doubling time. Today’s quantum computers have yet to construct an effective Toffoli gate - but there are lots of single-gate examples of something close to it. With a doubling time of one year (which is roughly what IBM is doing with their quantum computing devices), there are at least 30 years before 256-bit ECDLP is broken completely.
An interesting aspect of the same paper is the comparison with RSA and the number of qubits required for factoring large primes. That algorithm is the same as would be used for breaking elliptic curve pairing over an extension field. This requires 10^14 or 2^42 Toffoli gates for the same level of security as a 256-bit elliptic curve. Elliptic curve pairing operations are more secure than “plain old” elliptic curve point operations, at least in terms of quantum computer breaking.
We are a long way away from quantum computers being able to break public key algorithms using classical computation. At this point, the estimates say we have at least 20 and more likely 30 years before quantum computers can actually break these algorithms. It is always possible that some amazing breakthrough will change this overnight, but the history of science says it takes a long time from discovery to application because of all the friction reality throws in our path. Keeping thousands of qubits stable enough to pass through billions of gates will be exceptionally challenging.
To learn more about elliptic curve math on classical computers check out Elliptic Curve Cryptography for Developers (http://mng.bz/D9NA). This crypto will be secure for a long time to come.