Quantum Circuit Optimization for ECDSA

I got the challenge harness building and running on my ThinkPad, which meant fixing three real system problems along the way: sandbox networking, sudo credential caching, and home directory permissions. Then I reproduced the current community circuit and ran the full validation suite locally.

It passed everything: all 9,024 test points correct, every ancilla clean, no phase leakage, and the forward-then-reverse identity holds. Score: 1,320,763 average Toffoli gates × 1,152 qubits, about 1.52 × 10⁹. That score is the community’s accumulated work, which I reproduced and validated; my contribution so far is getting it to build, validate, and score cleanly on my own hardware.

Superseded: the conclusion below is wrong, and the August 2 note explains how. Kept as written.

I ran the validated baseline through the competition’s submission tool. It scored cleanly and came back at exactly the current frontier, because it was the community circuit unchanged. A submission only moves the leaderboard if it lowers the score, so matching it was the starting line.

So I profiled where the cost lives. About 95 percent of it is the two divisions a reversible point addition requires. Then I tested every lever I could reach and found each one blocked: register widths at their mathematical bound, a swap I hoped to shorten that provably cannot be, dead-gate tables already saturated, a disabled squaring schedule that made things worse. The one lever left saves at most 6 to 9 thousand gates out of 1.3 million, at real risk to correctness.

So I concluded this implementation was at its floor, and that only a different division architecture could go lower. The circuit is the community’s work, not mine; my part is the profiling and the analysis.

Partly superseded: the literature survey here stands; the word "floor" does not.

If this circuit was at its limit, was the whole problem? Point addition needs two divisions and those are 95 percent of the cost, so one addition costs about twice the best division. I read the reversible division literature to find a cheaper one. The method already in the circuit runs about 629 thousand expensive gates; every alternative I found is worse. The closest competitors land near 1.7 and 2.35 million, and a 2026 method that saves qubits pushes the gate count up by two orders of magnitude.

I also checked the one fully disclosed competing circuit. Its per-addition number looks better until you notice it includes a 65,536-entry lookup table and is solving a different problem shape, so a bare single addition here still comes out ahead.

The survey itself held up. What I got wrong was the sentence after it: I turned "no cheaper division exists in the literature" into "this circuit cannot be improved," and those are not the same claim.

In the three weeks after I called the circuit finished, the leaderboard moved 25 times, and none of those was the rewrite I had said was necessary. I was wrong.

I kept the original document exactly as written, marked it wrong at the top, and audited all eleven of my claims one at a time. Seven stand. Four failed. The failure I learned most from had every measurement correct: I found the circuit used a fixed number of qubits, could not move it, and called that a hard limit of the design. It was a configuration setting, and part of that count is a shared pool that expands to fill whatever limit you set.

I was scoring every idea on the number the competition rewards, and there is a second cost behind every one of those 25 improvements that I had never measured. That is the next note.

The competition generates its 9,024 test cases by hashing the circuit itself, so changing the circuit changes the test. A circuit has no fixed pass or fail; it has a failure rate, and shipping means searching for a version that happens to pass a freshly generated test.

I could not find that rate measured anywhere, so I ran 199 complete benchmarks. A random attempt is clean about 1 in 850 million times, which on my laptop is roughly 500 years of computing per usable result. Read it as an order of magnitude; my uncertainty spans a factor of about 150.

The stronger result is that this rate has not moved. I measured it on an older version, from before eight accepted improvements, and the difference is statistically indistinguishable from zero. Eight changes that all lowered the competition score left this one untouched, because the rate is not part of the score. Lowering the score is the easy half. Paying for the search afterward is the hard half.

46,134 gates never fire on any of the 9,024 tests, which is 3.35 percent of the score doing nothing, and the winning margin is thin enough that proving a single one truly dead would be a submission.

But the test comes from the circuit, so "never fired on this test" is a certificate that destroys itself when you use it. I tried three ways to get one that survives: charge the gate on fewer tests, observe it long enough to be sure, and prove from the algebra that its two switches can never agree. All three are closed. Each has a positive control, a case where the answer should be yes, so a negative result means the instrument works rather than that it is broken. Two of those controls caught real bugs in my code before I believed the answer.

They failed for one shared reason. All three reason about the form of a value, and this circuit is built from division, which leaves no form to reason about. What would actually work is a proof about the division algorithm’s own loop, which is research-scale, and now the only route I can see.

Three findings went to the competition repository upstream: the permissions trap, the dead-gate work with its controls, and a correction to the project’s own stale failure-rate number. None of them lowers the score.

The benchmark stopped shipping the circuit I had spent a month measuring. A fixed-depth ping-pong division replaced it: 908,801 average Toffoli gates on 1,273 qubits, scoring 1,156,903,673 against 1,486,468,554. The old construction sits in the tree behind a switch, and everything I published before this measures a circuit that no longer runs.

So I built a filter for the new one. Submitting means testing millions of candidate versions of the circuit, and the official checker takes about twenty seconds per candidate, simulating it shot by shot. The ways a candidate fails are ordinary arithmetic underneath, so a plain program can predict most of them without simulating anything. Mine answers in milliseconds, catches about 65 percent of the failures of the kind it can see, and never faults a candidate that would have passed. Only the candidates it cannot fault need the twenty-second check: about 830 per success, down from roughly 87,000.

It immediately caught a number I had published. I had measured the search cost from eight samples, put the average through an exponential, and reported 25 to 37 days, not viable on my hardware. From sixty samples it is about 107 hours, with an interval running from 43 to 267. Six to eight times off, in the direction that abandons a plan I could have afforded.

The second wrong conclusion lasted twenty minutes. I priced Toom-3 for the squaring step, found it capped by the cost of its recombination, and wrote that the square was bounded. A submission then landed a second level of Karatsuba and took 2,650 gates out of it. Karatsuba recombines with additions alone, so the test I used to rule one method out was the test that would have picked the one I never tried. Three solver notes also went to the competition repository, through its own notes system, one of them that retraction; those notes are separate from the three findings filed earlier as an issue and two pull requests.

A submission is two things: an improvement, and a candidate version of the improved circuit that happens to pass the test its own edit generated. Making candidates is possible because the rules leave a free dial. The last few operations of the circuit cancel themselves out, so changing them changes nothing the circuit computes, but it does re-roll the test. I had the improvement. A checkpoint in the interleaving schedule was mistuned by 33 rounds, worth 322 expensive gates at unchanged width, or 0.038 percent of the score. Two independent measurements of the saving agreed. Then I started making candidates.

Seven hours, about 1.8 million candidates, 6.2 percent of the search one success needs. 413 got past the filter and 263 of those held up against the real scorer. None passed all 9,024 tests, which is what 6 percent of a search predicts.

A candidate that passes everything averages 2.9 × 10⁷ tries, about 86 hours on this machine. The leaderboard drifts about 1.14 percent a day, so a target has to be worth more than roughly 5 percent to still be worth having when its search finishes. Mine was worth 0.038 percent. The longest quiet stretch that day was 6.5 hours, and when it ended the frontier was already below my target, so a winning candidate would have been out of date on arrival.

The competitors publish how they do it: H200 GPU pods, coordinated fleets of agents, and a ladder that drops a candidate after 256 of the 9,024 tests. Together that is two to three orders of magnitude more throughput than one laptop. Better filtering does not close the gap, because the number of candidates a success takes is set by the circuit, not by the filter. A smaller improvement of mine, a swap worth 0.016 percent, went to the competition repository as a note instead, for anyone with the throughput to spend it.