Deep divefrom Episode 4AI & computing29 September 202621 min

Bitcoin's Curve, Twenty Thousand Ions, Twenty-Six Days

A deep dive into one paper: what was known before, what the researchers did, what the numbers say and what they don't.

The paper: Computing 256-bit elliptic curve discrete logarithms in 26 days on a fault-tolerant trapped-ion quantum computer with 20,000 qubits (arXiv)

MP3

Chapters

Transcript

The script the two AI voices read from. The times are worked out from the script, not heard, so a line can start a few seconds early or late.

Read the whole episode

Cold open

Host 1You heard the trailer — this is the whole story. Welcome to the Hastrup Review of Science — where artificial intelligence reads real science, so you don't have to pretend you understood the paper. One paper today: a detailed blueprint for a quantum computer that could recover a Bitcoin private key from its public key, and an honest bill for what that machine would cost in qubits and days.

Host 2The paper is called Computing two-hundred-fifty-six-bit elliptic curve discrete logarithms in twenty-six days on a fault-tolerant trapped-ion quantum computer with twenty thousand qubits. It comes from fourteen researchers at the quantum computing company IonQ, with Thomas Häner, Felix Tripier and Jacob Young contributing equally. It is a preprint on the arXiv, not yet peer reviewed, and every author works for the company whose architecture it describes.

Host 1So nobody broke anything. This is a design on paper.

Host 2Exactly. No quantum computer ran any of this; it is a resource estimate for a machine that does not exist yet. What makes it unusual is how far down the stack they compiled it, from the mathematics all the way to physical ions moving on a chip.

The problem

Host 1Start with the problem itself. What is an elliptic curve discrete logarithm?

Host 2An elliptic curve over a finite field is a set of points with a rule for adding two points to get a third. Take a public starting point and add it to itself some secret number of times, and you land on another point. The discrete logarithm problem is going backwards: given the start and the end, find the secret number.

Host 1And going forwards is easy, going backwards is hard.

Host 2For classical computers, yes. As established background, the best known classical attacks on a well-chosen two-hundred-fifty-six-bit curve take roughly two to the one hundred and twenty-eight operations, which is far out of reach. That asymmetry is what elliptic curve signatures rely on: your private key is the secret number, your public key is the point you land on.

Host 1Which curve is this paper about?

Host 2A specific one called sec-p-two-five-six-k-one, which is the curve used by Bitcoin and other blockchain systems. The authors chose it because its security protects vast amounts of cryptocurrency, and because its prime has a special shape, just below a power of two, that makes the arithmetic cheaper. The most competitive previous estimates also targeted this curve, so comparisons are direct.

Shor's algorithm

Host 1Where does the quantum computer come in?

Host 2In nineteen ninety-four Peter Shor showed that a quantum computer could factor large numbers and compute discrete logarithms efficiently. The version for elliptic curves was worked out by Proos and Zalka in two thousand and three. The core idea is to put two scalar registers into superposition, compute a combination of point multiples, and then use a quantum Fourier transform to extract a hidden period that reveals the secret.

Host 1What is the expensive part?

Host 2Almost all of the cost is the arithmetic: computing point multiples in superposition, which means repeated elliptic curve point additions. Each point addition needs modular inversions, multiplications and squarings on two-hundred-fifty-six-bit numbers, all done reversibly. The Fourier transform itself is cheap by comparison.

Host 1And how do people measure the cost?

Host 2Two headline numbers at the logical level: how many error-corrected qubits you need, and how many Toffoli gates, a three-qubit gate that is the expensive non-Clifford operation in fault-tolerant machines. Then those logical numbers get translated into physical qubits and wall-clock time for a specific hardware design, which is where most of the uncertainty lives.

A history of shrinking estimates

Host 1How has that cost moved over time?

Host 2The authors give the trajectory. For factoring two-thousand-forty-eight-bit numbers, the physical qubit estimate fell from about a billion in twenty twelve to about a million on a two-dimensional grid, or around one hundred thousand if you assume long-range connections. For elliptic curves, Proos and Zalka's two thousand and three estimate was six billion gates; by twenty twenty-three it was about two hundred million Toffolis.

Host 1And this year?

Host 2Earlier in twenty twenty-six, André Schrottenloher published circuits needing about one thousand four hundred sixty-two logical qubits and eighty-four million Toffolis for a general curve, and about sixty million for Bitcoin's curve. Other groups traded more gates for fewer qubits, getting down to about twelve hundred, and even below eight hundred fifty logical qubits. At the hardware level, recent estimates suggested under twenty thousand physical qubits on a neutral-atom machine, and fewer than five hundred thousand on a superconducting one.

Host 1And for trapped ions?

Host 2Previous trapped-ion estimates for this problem ranged from one point two million to nine point four million physical qubits. So the headline of this paper is a drop to about twenty thousand on that platform. The authors also argue that many earlier estimates left things out, which is the second theme of the paper.

The open question

Host 1What did earlier estimates leave out?

Host 2Their list is specific: qubit transport, leakage and loss, which matter a lot for atoms and ions. Syndrome extraction times assumed to be one millisecond regardless of code. And the cost of Clifford gates and logical measurements, which do not show up in a Toffoli count at all.

Host 1Give me an example of that last one.

Host 2They point out that half the cost of a standard Gidney adder is in uncomputing temporary values by measurement, a cost the Toffoli count does not capture. So the open question here is not just whether the logical circuit can shrink, but what the full bill looks like once every operation has been compiled onto a real architecture, including moving data around.

Method: a cheaper circuit

Host 1Let us go through what they actually did, layer by layer. Start with the circuit.

Host 2They start from Schrottenloher's circuits and make two main changes. The first concerns the modular inversion, which uses a binary greatest-common-divisor procedure. They change how the registers are represented, so that controlled additions become conditionally-inverted additions, meaning add or subtract depending on a bit, which costs about half as many non-Clifford gates.

Host 1And the second?

Host 2A dedicated modular squaring circuit. They adapt a multiplier by Litinski into a squarer with roughly half the non-Clifford cost, and use a single Karatsuba split, an old trick that splits the number into high and low halves, together with the special near-power-of-two shape of Bitcoin's prime to make the modular reduction cheap.

Host 1What does that buy them?

Host 2Each windowed point addition costs about one point two million Toffolis, taking the largest count seen across one hundred runs. With twenty-eight point additions plus table lookups, the whole algorithm needs about thirty-nine million Toffolis, down from Schrottenloher's roughly fifty-eight million, at one thousand four hundred fifty-seven logical qubits.

Host 1Why twenty-eight point additions?

Host 2They process the scalars in windows of sixteen bits, loading precomputed tables of points. They drop the last three windows and recover those forty-eight bits by classical post-processing, and replace the first addition with one direct table lookup. That is a known technique from prior work, not new here.

Method: proving the success probability

Host 1The arithmetic is approximate. Does that mean some answers come out wrong?

Host 2Yes, by design. To save gates, these circuits ignore rare exceptional cases, truncate some comparisons and carry chains, and uncompute some values by measurement, which can leave a stray minus sign. On a small fraction of inputs, the output or its phase is wrong.

Host 1How do they know how small?

Host 2This is one of the more careful parts. They add random offsets, a random nonzero starting point and random shifts to every lookup table, sampled fresh for each run, so that no fixed input is always a failure case. That lets them prove a per-input failure bound and turn it into a lower bound on the overall success probability that is at most four times that failure rate below the ideal.

Host 1And earlier work did not do that?

Host 2According to the authors, earlier work used heuristics or informal fidelity arguments, and the rigorous alternative gave much looser bounds that scale with the square root of the failure rate. Part of their bound comes from Monte Carlo sampling of the multiplications, which is why it holds with confidence at least one minus two to the minus one hundred and twenty-eight.

Method: the trapped-ion machine

Host 1Now the hardware. What is the Walking Cat architecture?

Host 2It is IonQ's recently proposed general-purpose design: a two-dimensional grid of trapped ions, each holding one qubit, which can be physically transported across the chip. Because ions can move, distant qubits can interact, which allows quantum low-density parity-check codes, error-correcting codes that pack many logical qubits into fewer physical ones than the surface code.

Host 1What error rates do they assume?

Host 2Two-qubit gates failing one time in ten thousand, which has been demonstrated experimentally on small trapped-ion devices, and single-qubit operations failing one time in one hundred thousand, which the authors describe as within reach. Their logical error estimates include transport noise, leakage and loss.

Host 1Why not just run Shor on the general-purpose version?

Host 2They show the naive version would take about four hundred eleven days. Each Toffoli would need seven T gates, and each injection costs a logical measurement of about forty milliseconds, built from five error-correction cycles of six point seven milliseconds each. That adds up to at least nine hundred ten milliseconds per Toffoli, and the existing magic-state factories were not clean enough either.

Host 1And memory?

Host 2Storing about fifteen hundred logical qubits in a distance-nine surface code would take two hundred forty-three thousand physical qubits before doing any computation. A denser code from the Walking Cat paper, which packs twenty-two logical qubits into one hundred and two data qubits, brings that to roughly twenty thousand. But dense blocks make it hard to run several operations in one block at once.

Method: speeding up the Toffoli

Host 1So how did they get from four hundred eleven days to twenty-six?

Host 2Mainly by making Toffoli gates fast. They built a magic-state factory that directly produces the three-qubit resource state for a Toffoli inside an error-correcting code, instead of assembling it from seven T states, with logical error below one in a billion. Combined with a depth-one injection circuit, a Toffoli takes twenty-nine point five milliseconds, thirty-one times faster than the naive version.

Host 1How many factories?

Host 2Four, using three hundred nineteen physical qubits each, together producing a resource state on average every twenty-eight milliseconds or so, enough to keep a continuous flow. The factory uses a new code the authors introduce, encoding four logical qubits in sixty-six physical ones. They named the distillation scheme Eastinthillation.

Host 1Why only four? More factories would be faster.

Host 2The algorithm is essentially serial: at most about one Toffoli can run at a time, because each step of the arithmetic waits on the previous one. So extra factories would sit idle. That serial structure is a constraint, and the authors exploit it repeatedly to save qubits.

Method: saving qubits

Host 1How do they exploit it?

Host 2Three ways. First, a scheme called logical Clifford noise reduction, which keeps the bookkeeping inside dense blocks simple; done naively it would add forty thousand qubits, but because the arithmetic sweeps along serially they pipeline it with just four extra blocks, saving thirty-nine thousand two hundred qubits. Second, instead of giving every block its own resource states for measurements, a limited pool of these cat states is moved around to wherever the computation currently is.

Host 1And the third?

Host 2A new model for losing ions. The previous design assumed a lost ion could spread its damage, so every block carried extra beacon qubits to detect losses. They adopt a swap-loss model, in which an interaction can move a loss but not spread it, and with a new loss-correction unit they remove the beacon qubits, about a third of every memory block.

A word from our sponsor

Host 1Do you have problems with hair that has been in the lab for twenty-six days straight? Then you are in luck.

Host 1The Hastrup Review of Science is brought to you by dry shampoo. A light spray at the roots, a quick brush through, and you are ready to face the room, no water required.

Host 2I keep a can next to the cryostat. When the run goes long, it helps me stay fresh all the way to the end.

Host 1It comes in scented and unscented versions, and in travel sizes for when you cannot get home between shifts. It is widely available and very reasonably priced.

Host 2And it absorbs everything. Nobody needs to know how long you have been going at it.

Host 1Dry shampoo. Our referral link is in the show notes.

Method: compiling everything

Host 1Back to the paper. They also built a compiler. Why does that matter for the estimate?

Host 2Because most previous estimates stop at gate counts. Here every major component, adders, multipliers, table lookups, the squaring routine, is compiled into an executable schedule of logical measurements that obeys the architecture's rules. Those rules include sixty-nine memory blocks of twenty-two logical qubits, at most three simultaneous measurements per block, and one Toffoli injection per layer.

Host 1And the data movement between blocks?

Host 2They call it integrated routing: moving qubits between blocks with a few measurements, and hiding those moves inside the serial rippling of the arithmetic. For a two-hundred-fifty-six-bit modular adder, the theoretical floor is about six hundred sixty-nine measurement layers, and the compiled version takes six hundred seventy-four. Across the whole algorithm, they report routing overhead of about five percent of runtime.

Host 1How do they know the compiled circuits are correct?

Host 2Each component carries a machine-checkable contract describing what it should do, and the verifier checks that each decomposition meets it. Small components are checked exhaustively, large ones by sampling; the approximate modular adder for Bitcoin's prime was checked on one hundred thousand random inputs. As a pipeline test, they also compiled Shor's factoring algorithm for three- and five-bit numbers and simulated the result exactly.

Results

Host 1Put it all together. What are the numbers?

Host 2Seventy-five point three million measurement layers at twenty-nine point five milliseconds each, which is six hundred sixteen point six hours, or twenty-five point seven days per attempt. The device has nineteen thousand three hundred ninety-seven physical qubits. The in-place multiplications account for about three hundred seventy-seven of those hours, and table lookups for another hundred and eighty.

Host 1Where do the nineteen thousand qubits go?

Host 2Sixty-nine memory blocks of two hundred seven physical qubits each, fourteen thousand two hundred eighty-three in total. Then two thousand eight hundred eighty for the moving cat-state bundles, one thousand two hundred seventy-six for the four factories, eight hundred twenty-eight for the four noise-reduction blocks, and small numbers for Bell-state bundles and reserve ions to reload lost ones.

Host 1And does it work?

Host 2Not every time. The chance of an uncorrected logical error during one attempt is about twenty-six percent. Combined with the algorithm's own success rate, one run succeeds with probability forty point seven percent using a rigorous lower bound by Mosca, or sixty-three point three percent using a heuristic estimate by Ekerå.

Host 1So you might need to run it twice.

Host 2Or run several machines in parallel. The authors note that with five identical devices and independent failures, the chance at least one succeeds rises to ninety-nine point three percent, in the same twenty-six days. That is five machines of twenty thousand qubits, though.

Host 1Are these numbers optimistic or pessimistic?

Host 2The authors say they chose simplicity over squeezing out every gain. They charge every logical measurement as if it took as long as a Toffoli injection, assume all sixty-nine memory blocks are active for the whole run, use one adder design throughout, and keep the device layout fixed. They call the runtime a conservative upper bound, and name more classical post-processing and parallel runs as ways to shrink it.

Why it matters

Host 1Step back. Why does this matter?

Host 2The principle is that the cost of breaking elliptic curve cryptography keeps falling from both ends at once: better circuits, and hardware designs tailored to the algorithm. This paper is a detailed data point on the hardware side, for one platform, with the whole compilation chain shown. It lowers the trapped-ion estimate for this problem by more than an order of magnitude compared with the earlier ones they cite.

Host 1Who should care?

Host 2Anyone responsible for systems that rely on elliptic curve signatures, including cryptocurrencies, and the people planning migrations to post-quantum signatures. As background: standard post-quantum signature schemes already exist, and migration is slow, so estimates like this feed directly into how urgent people think that work is.

Host 1What does it not mean?

Host 2It does not mean Bitcoin is broken, or that such a machine exists. As background, today's trapped-ion computers are far smaller, on the order of a hundred physical qubits, and none runs full fault tolerance at this scale. Also, twenty-six days to recover one key is a very different threat from intercepting a transaction in minutes; as background, a slow attack mostly threatens public keys that stay exposed for a long time.

Caveats

Host 1What are the honest caveats?

Host 2First, the authors work at IonQ, and the architecture is theirs; this is a company preprint without peer review. Second, the whole estimate rests on hardware assumptions: one-in-ten-thousand two-qubit errors have been shown on small devices, but not across twenty thousand ions being shuttled around continuously for almost a month.

Host 1Go on.

Host 2Third, several architectural capabilities, like three simultaneous measurements per block and tracking Clifford gates inside blocks, are described as empirically validated for these specific arithmetic circuits, not proven in general. Fourth, the swap-loss model relaxes the hardware requirements for lost ions, but it is an assumption about how real losses behave that hardware will have to confirm.

Host 1Anything else?

Host 2Comparisons across platforms are hard, because different papers count different things; the authors themselves argue other estimates leave out transport, loss and Clifford costs. And one note on our side: our copy of the full text ended partway through the architecture section, so the appendices on the factory, footprint and runtime derivations we could not check directly.

What to watch

Host 1What should we watch for next?

Host 2Independent groups checking the circuits and the success-probability bound, since those are claims that can be verified without any hardware. Competing estimates for neutral atoms and superconducting machines that account for the same overheads, so the platforms can be compared fairly.

Host 1And on the hardware side?

Host 2Whether trapped-ion systems can hold one-in-ten-thousand error rates while scaling up and moving ions around, and whether the loss behavior matches the swap-loss model. And on the cryptography side, how fast systems move to post-quantum signatures while the estimates keep falling.

Sign-off

Host 1That is the deep dive: Computing two-hundred-fifty-six-bit elliptic curve discrete logarithms in twenty-six days on a fault-tolerant trapped-ion quantum computer with twenty thousand qubits, by Häner, Tripier, Young and colleagues at IonQ, a preprint on the arXiv. The link is in the show notes.

Host 2Every Friday this same feed carries the roundup episode: five new papers as trailers, and you pick which become deep dives. This has been the Hastrup Review of Science.