A more efficient implementation of Shor's algorithm

Shor's algorithm is the main practical example of an algorithm that runs more quickly on a quantum computer than a classical computer — at least in theory. Shor's algorithm allows large numbers to be factored into their component prime factors quickly. In reality, existing quantum computers do not have nearly enough memory to factor interesting numbers using Shor's algorithm, despite decades of research. A new paper provides a major step in that direction, however. While still impractical on today's quantum computers, the recent discovery cuts the amount of memory needed to attack 256-bit elliptic-curve cryptography by a factor of 20. More interesting, however, is that the researchers chose to publish a zero-knowledge proof demonstrating that they know a quantum circuit that shows these improvements, rather than publishing the actual knowledge of how to do it.

Quantum background

Quantum computers store their information in qubits, each of which essentially stores a two dimensional vector with length one — a superposition. Quantum logic gates can do operations such as rotating a qubit or reflecting it around some other vector. Together, these operations can be chained together to create a quantum circuit that performs a useful operation in the same way that logic gates in a classical computer are combined into a circuit. The exact result that is measured at the end of a quantum circuit, however, can be quite sensitive to noise from the environment. This is the major practical challenge in building a quantum computer: isolating it from the environment sufficiently well that the information stored in its qubits doesn't degrade to the point of uselessness. The difficulty of this isolation goes up with the size and complexity of the quantum circuit, and with the number of qubits.

One technique that is used to reduce the precise tolerances required inside a quantum computer is error correction. A quantum error-correction scheme works a bit like ECC memory: it emulates a single "logical" qubit using a group of less-precise "physical" qubits, in the same way that ECC memory produces more reliable memory storage by combining multiple potentially noisy memory cells. The nine researchers behind the new paper — who come from Google, the University of California Berkeley, the Ethereum Foundation, and Stanford University — have produced a quantum circuit for factoring 256-bit elliptic-curve signatures using fewer than 1,200 logical qubits and 90 million quantum gates. Depending on architecture, this corresponds to around 500,000 physical qubits. IBM's Condor quantum computer, among the largest publicly known quantum computers, has 1,121 physical qubits, meaning that engineers will need to give quantum computers around 500 times more memory before an attack using the new technique becomes practical. They'll also need to increase the number of gates, but that is believed to be less of a limiting factor.

[Readers who are not interested in the details of how the researcher's proved that they had such a breakthrough may wish to skip to the conclusion.]

Zero-knowledge proofs

It isn't possible to say the exact number of logical or physical qubits needed, however, because the researchers have not published their actual improved quantum circuit. Citing concerns that bad actors could use the research to attack digital security, including the security of the Bitcoin blockchain, they instead chose to publish a machine-verifiable proof that they know a particular circuit that lives up to their claims. This is not new territory for mathematics; 16th century mathematicians would keep their breakthroughs secret and challenge each other to "duels" where they proved that they knew an analytical solution to a complex equation by quickly solving difficult instances of the problem.

It is new in the modern era of mathematics, however. This is the first quantum-computing paper to use this style of zero-knowledge proof. The way the proof works is quite interesting. The researchers wrote a simulator for quantum circuits (available from their published reproduction data) that reads in a quantum circuit, generates thousands of random inputs, simulates the behavior of the circuit on those inputs, and checks it against a reference implementation. Ordinarily, this would not suffice to prove that the circuit was correct — what if it was correct for 99% of inputs, but incorrect for the remaining 1%? In this case, however, that doesn't matter. Shor's algorithm is, by design, robust to occasional small errors in its intermediate computations; therefore, it doesn't matter whether the quantum circuit being simulated is right in every case, only that it is right in a sufficiently high number of cases. The researchers target a circuit that is accurate in 99% of cases. As long as the researchers cannot cherry-pick the "random" inputs, running enough random trials shows that it is correct enough.

In order to ensure the inputs are really random, the researchers use a pseudorandom-number generator seeded from the hash of the description of the circuit being tested. As long as the hash function in question (SHA-256 in this case) and the pseudorandom-number generator are both secure, this ensures that the researchers couldn't have manipulated the randomly chosen test inputs.

So, in theory, running this program and feeding it the unreleased quantum circuit would prove that the circuit was good enough for use inside Shor's algorithm. But how can the researchers prove that they did run the experiment correctly if nobody else has access to the input to the program? The solution is SP1, a "zero-knowledge virtual machine" that allows users to produce cryptographically secure proofs (STARKs, or "scalable transparent arguments of knowledge") that they ran a program and that it produced a given output, without revealing what the input to the program was. SP1 works by emulating a RISC-V chip that produces a trace of the CPU's execution as it goes, and then proving that the trace must correspond to a valid execution of the corresponding RISC-V program regardless of what the input values were.

SP1's CPU trace lists, for every register and memory location, what its value was at each time step. Taking the inverse fast Fourier transform of each list produces a "trace polynomial" for each register. The trace polynomials are a representation of how the register changes over time; by combining these polynomials in the right way, SP1 produces "constraint polynomials". These polynomials represent whether the rules of the emulated RISC-V CPU were violated. They include constraints such as "the output of the arithmetic logic unit must be A + B when the mode is set to addition" or "the next program counter must be one more than the previous, unless there was a jump instruction". Each constraint polynomial is constructed such that it must be zero at every time step. At this point, if the person constructing the zero-knowledge proof could show that property held, they would have demonstrated that they executed the program correctly.

To show this, the person constructing the proof can divide the combined constraint polynomials by a (fixed) polynomial that equals zero at each time step. If they were telling the truth, the result is still a polynomial. If they were lying about any of the time steps, the division results in a rational function that can eventually be distinguished from a proper polynomial. Imagine a heavily simplified example where the constraint polynomial is just "x - 1" and the fixed polynomial is also "x - 1". Dividing one by the other gives a linear function (a kind of polynomial) with a hole at the point x = 1. On the other hand, if the constraint polynomial had been "x + 1", then the result of the division wouldn't be a polynomial: it would have an asymptote at x = 1. Since those functions have different shapes, it's easier to construct a protocol that reliably distinguishes them.

In order to prove that the result of the division is a polynomial, the prover splits the function into even (symmetrical about the y-axis) and odd (symmetrical about the origin) parts, multiplies the odd part by a randomly chosen constant, squares the inputs to both parts, and adds them back together — an operation known as folding. If the input to this folding was indeed a polynomial, this produces a polynomial with a smaller finite domain; if the input to this operation was a rational function, however, the resulting function is still a rational function with high probability. Eventually, the domain shrinks down to a single point and the function becomes a constant function.

To demonstrate that they are performing the folding correctly, the prover picks random points and writes down what the function evaluates to there. Importantly, the hashes of these points are incorporated in later steps of the proof, ensuring that the prover cannot go back and modify them afterward. Later, someone interested in verifying the proof can challenge them for some of these randomly chosen points and check how they relate to one another before and after folding, making it difficult for the prover to get away with folding the function incorrectly. By repeatedly folding the function, the prover can eventually produce a single number that is shared as part of the proof. As long as the random numbers were indeed chosen randomly, it is probabilistically difficult for the prover to create a matching chain of folds that ends at the publicly shared constant without having a valid polynomial to start with.

Obtaining properly random numbers is the same problem that the researchers faced above, and is solved in the same way: the random numbers are generated according to a hash of the publicly-known portion of the proof (including the machine-code of the RISC-V program, and the hashes of the random numbers used at previous steps of the proof). This lets the verifier take the input, the list of commitments, and the final output, and check that each of the folding steps was performed correctly. If each of the folding steps were performed correctly and the results match, the verifier learns that the RISC-V program was emulated correctly, without learning details about the actual register values.

There is one problem, however: for a program that executes millions of RISC-V instructions, the generated trace and the resulting proof can be quite large — too large for people to verify quickly on their own computers. So, the researchers perform one more transformation of the data to compress the proof into a minimal form that is more efficiently checkable.

STARK to SNARK

There is a different kind of zero-knowledge proof called a succinct non-interactive argument of knowledge (SNARK) that is less flexible than STARKs. Instead of being able to handle arbitrary computations, it only handles computations that can be expressed in a limited domain. In this case, the researchers used a SNARK system called Groth16, which only handles computations that can be expressed as a set of constraints on values in an abstract circuit made from classical logic gates where each constraint involves at most one multiplication operation. It also requires a completely random (not pseudorandom, as above) number to be securely agreed upon, used to create a kind of public key, and then completely forgotten. In exchange for this loss of flexibility, SNARKs produce much shorter, simpler proofs. In particular, the size of a SNARK proof is constant, regardless of what it is proving.

As it turns out, however, the process of validating a STARK proof can be expressed as a circuit diagram that Groth16 can handle. Unlike running the RISC-V simulator program (which runs for a variable number of time steps depending on the input), the process of validating a STARK can be formulated to take a constant amount of time, letting it be represented as a fixed circuit. The researchers took a verifier that could check the large existing proof, and compiled it to a set of Groth16 constraints. Evaluating this system of constraints produces values for each intermediate wire in the circuit (the analog of the CPU trace in a more complicated STARK proof). These intermediate values are converted to polynomials in much the same way as the trace polynomials inside a STARK. These polynomials are again combined into a single function such that if all of the constraints were satisfied, the function remains a polynomial — but if any were violated, it becomes a rational function instead.

The method by which the verifier checks that the resulting function is a polynomial is fairly different, however. The prover uses the publicly known key referenced above to calculate three values, each of which is a different way of combining information from the trace of the circuit with elements of the public key referenced above. The public key consists of precomputed numbers that can be used to evaluate a polynomial at a specific random location that nobody knows. The public key is structured such that the numbers can't be used to derive what the unknown location was (without being able to efficiently factor large numbers). The verifier can then check the relationship between the public key and the three generated numbers to show that the prover's function, minus a polynomial, evaluated at that unknown random location, equals zero. According to the Schwartz-Zippel lemma, this is incredibly unlikely to happen by chance unless the prover's function was a polynomial to begin with.

The security of that construction hinges heavily on the random location being truly unknown — an adversary who did know it could just evaluate the function directly at that location in order to fake a SNARK proof. In this case, the researchers used the key generated by a secure multi-party computation done by Aztec Labs as part of setting up their Ethereum-based cryptocurrency. That computation was a joint venture in late 2019 between 176 different people: each one generated a random number and added it to a communal pool of randomness that was used to calculate the necessary public key using a distributed algorithm. As long as at least one of those people was diligent enough to properly erase their random number after the process was conducted, the random location used to construct and validate these Groth16 SNARKs is unrecoverable.

The result of all of this complexity is a 1.7MB proof file that (in conjunction with the source code of their simulator) shows that the researchers behind this paper did actually produce a usable quantum circuit meeting their stated claims. Of course, I had to try this out for myself. Downloading and compiling their source code was straightforward, and verifying the proof took just under 14 minutes of CPU time on my laptop. The code for the simulator, prover, and verifier comes to just under 1,500 lines of Rust — but there are over 2,800 external libraries used in support of that code, so auditing the code remains somewhat daunting. The correctness of the verifier code is not something that can be guaranteed cryptographically; it relies on the normal process of publishing the artifacts and letting interested people point out any problems.

In summary: assuming that the publicly published source code the researchers shared is correct, and that at least one person out of a list of 176 cryptography enthusiasts in 2019 was honest, then it is almost certainly the case that the verifier in the paper's reproduction data was fed a valid STARK transcript. In turn, that means that it was almost certainly the case that their simulator, when fed some input known only to the researchers, validated that the input was a quantum circuit that provides a substantial speedup over prior work on Shor's algorithm. Here "almost certainly" means that it is not theoretically impossible that they could have created a forgery by random chance — but doing so would be as difficult as breaking many other well-trusted cryptographic systems by chance. Winning the lottery 10⁶⁸ times in a row would be more likely.

Now what?

I am personally delighted by this kind of careful, complicated cryptographic construction, but it does raise some concerns for the future of open mathematics. If the paper's authors had chosen to release their circuit, they would certainly have been recognized for the important progress they made in the science of quantum computing. Other researchers would have gone on to build on their work, and the entire scientific community would be richer for it.

As it is, the researchers haven't really published a breakthrough. Instead, they have published a cryptographic proof that they have a breakthrough, but they aren't going to share it. It's certainly exciting to know that more efficient quantum circuits for Shor's algorithm exist — but do the researchers deserve the same level of praise for finding it, when the rest of the scientific community won't be able to learn from and build on their work?

Worse, it's impossible to say how their work combines with other advances in the field. Another paper, published the same week, introduced an exciting technique for reducing the number of physical qubits required to simulate a logical qubit in some circumstances — albeit in a slightly convoluted way that increases the number of required quantum gates. Does that work apply to the unknown quantum circuit? If so, it could reduce the number of required physical qubits to attack 256-bit elliptic-curve cryptography to around 25,000 — still 25 times larger than any existing quantum computers, but much smaller than the best estimates from a year ago. It's impossible to say for sure whether the potential reduction in physical qubits applies, since the details of the new quantum circuit are unknown.

Practical quantum computers always seem to be years away. This paper probably doesn't change that, but it does make it much harder to tell exactly how many years away they may be. Perhaps the best we can do is continue working to adopt post-quantum cryptography, and hope that when practical quantum computers become available we get an actual explanation of how they work, and not just a cryptographic proof that they do.