How it works
The whole competition comes down to one small operation, built out of the simplest logic steps a quantum computer can run: what those steps are, which ones are expensive and why, how an ordinary computer can run all of it today, and where almost all of the cost turns out to hide. No background needed beyond the threat primer.
The one operation
Shor's attack spends nearly all its time on one thing: adding two points on the secp256k1 curve. That step is a fixed recipe combining two points into a third, repeated thousands of times. So the size of the whole attack is the size of that one step, multiplied out.
That is why the competition ignores the rest of the attack and scores only this operation. A leaner step means a leaner copy everywhere it repeats, and a smaller machine to run the attack. The whole project is shaving cost off this one step.
What does “adding two points” mean, then? secp256k1 is an elliptic curve, the smooth shape one short equation draws: y² = x³ + 7. “Adding” two points on it is a geometry rule, draw a straight line through them and reflect where that line next crosses the curve.
Interactivey² = x³ + 7
P
(-1.00, 2.45)
Q
(2.00, 3.87)
P + Q
(-0.77, -2.56)
on the curve: y² = 6.53 and x³ + 7 = 6.53equal ✓
Draw the straight line through P and Q (orange). It hits the curve at exactly one more point, then reflect that point down across the x-axis (dashed) to get P+Q. That reflection is the whole rule, and it is the one operation the circuit optimization is built around.
The surprising part, and the reason the scheme works: whichever two points you pick, the answer lands back on the curve. Nothing ever falls off. That property is called closure, and it turns the curve into a self-contained number system you can do arithmetic inside, which is what a cryptosystem needs.
Why it can never fail comes down to counting. Substitute the straight line into y² = x³ + 7 and what is left is a cubic in x, whose solutions are the places where the line meets the curve. Two of those solutions are known already, because P and Q sit on the line and on the curve both, and a cubic has room for exactly one more. So the third crossing has to be there. The same counting gives the third crossing's x-coordinate: x₃ = s² − x₁ − x₂, where s is the slope of the line. That formula is what the picture above computes. The closure page works through the derivation, the two cases it misses, and why none of it changes when the coordinates become 256-bit whole numbers.
This is the part I love. A line and a reflection, a rule simple enough to sketch by hand, and it is what keeps real money safe for millions of people. A small piece of geometry carrying that much weight is something I find hard to put down.
The keys come from repeating this one move, but on a single point. In the picture above, P and Q were two separate sample points, added once to show the rule. Key-making instead starts from one fixed, public point called the generator G, and adds it to itself over and over, which is the doubling step that makes this fast. Sum d copies of G and you land on a point Q = dG. The secret number d is the private key; the point Q you reach is the public key. Going forward is quick, but recovering d, the number of copies, from just G and Q is the hard problem that keeps a wallet locked. The threat primer walks through that lock in full.
The real curve lives over a finite field of about 2²⁵⁶ whole numbers, so it is actually a scatter of points, not a smooth line. The picture uses ordinary numbers to make the rule visible, but the finite-field version the attack runs on follows the same rule.
The strange rule
A quantum computer has a rule an ordinary one does not: every operation must be reversible. Given the output you have to be able to recover the input. Think of a recipe you could run backward to get your exact ingredients out of the finished dish.
Ordinary logic breaks that rule constantly. An AND gate answers “are both inputs on?” with one yes or no, and a “no” does not tell you which input was off. Information was thrown away, so the step cannot be undone.
A quantum circuit is not allowed to do that, so all of the arithmetic has to be rebuilt out of reversible steps, and any scratch work has to be wiped clean at the end. Those scratch qubits are called ancilla, and the competition does not accept any circuit that leaves them dirty. This is why so much of the work is bookkeeping: not just computing the answer, but undoing everything else you touched to get it.
The parts
A circuit is qubits (the wires) and gates (the steps). Most gates are cheap. One is not, and it does the real work: the Toffoli gate. It flips a bit only when two other bits are both on, the reversible way to do an AND, and every piece of arithmetic is built from it.
The Toffoli dominates the score because of what it costs to run. On a real error-corrected machine, a Toffoli cannot be run directly. It has to be fed a specially prepared, expensive resource called a magic state, and manufacturing those magic states is one of the most costly things such a machine does. Simple gates are close to free by comparison. So the competition counts Toffoli gates as its stand-in for how hard the whole circuit is to run.
The obvious question
The circuit needs about 1,267 reliable qubits, each of which takes on the order of a thousand of today's noisy physical ones to build, and the largest commercial machine today holds about 1,600 physical ones in total. A machine that could run this circuit does not exist. Every run in this project, and every entry on the leaderboard, happened on an ordinary computer.
That works because of what the gates do. Each one flips a bit, or flips a bit when certain other bits are on. Start from a definite input, a string of zeros and ones, and every bit stays a definite zero or one through every gate, so an ordinary computer can follow along, one flip at a time. The benchmark does exactly that. It runs the circuit on 9,024 definite inputs and checks every answer, which takes about twenty seconds per run on my laptop. The cost is just as checkable, because the score is a count: add up the Toffoli gates and note the widest the circuit ever gets.
What no ordinary computer can do is what the circuit is for. Shor's attack would run it on a superposition, an enormous number of inputs at once, and following all of those together is where an ordinary computer falls hopelessly behind and a quantum one does not. The benchmark never needs that step, because checking the arithmetic only takes one input at a time.
So the competition designs and prices a machine part that nothing can run yet, the way an engine part can be machined and measured before the engine exists. Whether the arithmetic is right and what it costs are checkable today. The attack is not.
The score
A submission is graded on one number: average Toffoli count times peak qubit width. Lower wins.
~911,000
Toffoli gates
the expensive operations, counted per run
1,267
qubits
how wide a machine the circuit needs
The Toffoli count says how much expensive work the circuit does, and the qubit count says how big a machine it needs. Multiplied, they give one number for the difficulty of the attack, so a smaller product means a leaner, sooner threat. The last time I measured the challenge circuit, on August 23, those numbers were about 911,000 and 1,267, or roughly 1.15 billion. They move whenever somebody lands an improvement, which happened six times that day. The construction that was replaced that morning measured about 1.3 million and 1,154, or roughly 1.49 billion.
The bottleneck
Adding two points on the curve is a sequence of arithmetic on enormous 256-bit numbers, all done in clock arithmetic (every result wraps around a fixed prime). Adding, subtracting, and multiplying those numbers is manageable. Dividing them is not.
Division in clock arithmetic has a name: modular inversion, finding the number that undoes a multiplication. It is far more work than the other operations, and a single point addition needs two of them. When I profiled where the Toffoli gates go, those two divisions were about 95 percent of the budget. Both constructions the challenge has shipped do them with a binary GCD engine, an old algorithm for greatest common divisors run in reversible form. So the competition, stripped all the way down, is one question: can anyone divide, reversibly, for fewer Toffoli gates?
The floor
Two facts seemed to pin the cost in place. First, this kind of point addition requires those two divisions; there is no version that skips them. Second, when I went through the published methods for reversible division, none used fewer Toffoli gates than the one already in the circuit. Every other lever I could reach was blocked too. So I concluded the cost bottomed out at roughly two divisions' worth, and called that a floor.
The first fact still holds and the literature survey still holds. The conclusion I built on top of them does not. Over the next three weeks the leaderboard improved 25 times without anyone replacing the division engine. “No cheaper division exists in the published literature” and “this circuit cannot be improved” are different claims, and I ran them together.
What every improvement actually costs is a different quantity. The test cases are generated from the circuit itself, so every edit re-rolls the test, and the real cost of an improvement is the search you have to run afterward. The main project page measures that cost.
Quick reference
Where this leads
With the vocabulary in hand, the project notes on the main page read as a running log: reproducing the circuit, profiling it, calling it finished, being proven wrong, and finding what actually limits it.
Now the notes make sense
Keep reading