GoKawiilReady to give LWN a try? With a subscription to LWN, you can stay current with what is happening in the Linux and free-software community and take advantage of subscriber-only site features. We are pleased to offer you a free trial subscription, no credit card required, so that you can see for yourself. Please, join us!
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.
38 quantum gates to do it. This requires a circuit that is roughly eight orders of magnitude larger than modern quantum computers can handle. Other recent research has shown how to break 256-bit elliptic-curve cryptography using only 1,098 logical qubits, but that paper used 2quantum gates to do it. This requires a circuit that is roughly eight orders of magnitude larger than modern quantum computers can handle.
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.
... continue reading