open-standards/wai/wai-quantum/docs/estimate.md

Estimating a program's fault-tolerant resources

wai_quantum::engine::estimate answers what a fault-tolerant machine would need to run a program: how many physical qubits, for how long, with how many T-state factories. It works in three layers, each a deterministic function of the one before:

1. the program's logical counts, read from its circuit (or from a document of counts);
2. the planar model's layout: tiles, logical steps and T states;
3. the physical estimate on a physical qubit, with the code distance chosen by a code model calibrated from this crate's own decoders, and the frontier of estimates that trade qubits for time.

Every estimate is sealed in the resource-estimate receipt family (quantum_resource_receipt), binding the program's digest, every count, the error budget and each rotation's share of it.

wai-quantum estimate prog.qasm                          # on ns-e4, budget 1e-3
wai-quantum estimate prog.qasm --qubit us-e3 --budget 1e-4
wai-quantum estimate prog.qasm --qubit all              # the headline on each reference qubit
wai-quantum estimate prog.qasm --json > est.json        # sealed with your key
wai-quantum verify est.json                             # the seals, every receipt, and a re-run
wai-quantum estimate --counts counts.json               # a logical-counts document
wai-quantum estimate --routine program.json             # a routine document
wai-quantum estimate prog.qasm --export routine         # the program's counts as a document

The same estimate is POST /v1/estimate on the job service (sealed with the service's key; POST /v1/verify re-runs it), the MCP tool estimate_resources on both servers, QuantumEngine.estimate in a page, estimate in the desktop app, wai_quantum.estimate in Python, and the Studio's Estimate pane. wai-quantum lab estimate keeps the planar model's worked examples and counts given by hand.

An example

For the program

OPENQASM 3.0;
qubit[4] q;
h q;
ctrl(3) @ x q[0], q[1], q[2], q[3];
rz(0.3) q[0];
t q[1];

the estimate on the us-e3 qubit with a budget of 10⁻⁴ reads:

$ wai-quantum estimate ladder.qasm --qubit us-e3 --budget 1e-4
program      circuit, digest e7c22cd6343bdf7b…, 4 qubits (exact counts)
counts       5 logical qubits (1 ancilla), 4 measurements, 1 T, 3 Toffolis, 1 rotations (43 T in their words); T depth 46, depth 111
epsilon      budget 1.000e-4: synthesis 3.333e-5, 3.333e-5 each over 1 rotations (43 T each); the words' distances add to 2.667e-5
calibration  a = 0.0233, p* = 0.01004, fitted to the exact matching decoder's memory experiment, extrapolated from p = 0.002 to 0.005
estimate     us-e3, surface code (fit: exact matching), d = 11: 67276 physical qubits (13 factories, 93.5% of them), 382.8 ms
frontier     slowdown    d factories        physical  runtime
                    1   11        13           67276  382.8 ms  ← the estimate
                    2   13         6           35124  904.8 ms
                    4   13         3           20604  1.81 s
                    8   13         2           15764  3.62 s
                   16   15         1           12940  8.35 s
receipts     5 estimates sealed by did:key:z6Mk…; they verify and re-run here

The request

Field	Default	What it is
qasm, counts or routine	—	the program (OpenQASM 3 or 2), a logical-counts document, or a routine document; exactly one
budget	1e-3	the probability the run may fail, shared by logical errors, distillation and the rotations' synthesis
qubit	ns-e4	a reference qubit (below), or {"name", "instruction_set": "gate"|"measurement", "gate_ns", "meas_ns", "clifford_error", "t_error"}
calibration	exact_matching	the gate-based surface code's model: exact_matching, union_find (fitted to the decoders) or assumed (the planar model's own)
max_slowdown	256	the frontier slows the program by 1, 2, 4, … up to this (at most 4096)
clock	"steps"	how long a Toffoli takes: "steps", three logical steps; or {"reaction_us": t}, the reaction-limited clock (below), t above 0, below 10⁹ and no shorter than a measurement on the qubit
export	none	also give the counts as a counts or routine document
name	program	the program's name in a routine document

The reference qubits are the planar model's six:

Name	Instruction set	Gate time	Measurement time	Clifford error	T error
us-e3	gate-based	100 µs	100 µs	10⁻³	10⁻⁶
us-e4	gate-based	100 µs	100 µs	10⁻⁴	10⁻⁶
ns-e3	gate-based	50 ns	100 ns	10⁻³	10⁻³
ns-e4	gate-based	50 ns	100 ns	10⁻⁴	10⁻⁴
meas-e4	measurement-based	100 ns	100 ns	10⁻⁴	0.05
meas-e6	measurement-based	100 ns	100 ns	10⁻⁶	0.01

Layer 1: logical counts (counts)

The program is read by the one reader, then written in the estimate's gate set: Clifford gates, T and T†, z rotations at angles off the multiples of π/4, Toffoli gates (each one CCZ state) and measurements.

• Gates are written as the compiler's lower pass writes them (h x y z s sdg t tdg cx cz swap rz, a rz at a multiple of π/4 named as the T, S or Z gates it is), except ccx and ccz, kept as one Toffoli each, and cswap, a Toffoli between two CNOTs. So cp(π/2) is three T gates and cp(π/4) three rotations, as the decomposition is.

• Gates under several controls. The reader lowers ctrl(c) @ g without ancillas, through a phase polynomial of 2^m − 1 rotations: exact, but no machine would run it that way. The estimate writes it through clean ancillas instead, a ladder of Toffolis computing the AND of the controls and then uncomputing it:

  Gate	Toffolis	Ancillas	Other
  x, y, z under c ≥ 3 controls	2c − 3	c − 2	Cliffords
  h under c ≥ 3 controls	2c − 3	c − 2	two T
  a phase (s, sdg, t, tdg, p(θ)) under c ≥ 2 controls	2c	c	the phase once, on the ancilla holding the AND

  With fewer controls the reader's own lowering already uses a Toffoli and is kept. One pool of ancillas, sized for the widest such gate, serves them all, so two of them never run at once; ladders counts them.

• Measurements are the program's (a program that measures nothing is measured on every qubit at the end, as every job reads it). A reset is a measurement and an x.

• A program that branches on what it measured is written step by step, each step once. The reader's jumps all go forward, so no step runs twice on any run: the counts bound every run's from above (bound: "upper"). A step that jumps back is refused (QE02).

Then each rotation is synthesised at its own angle, by the Ross–Selinger search in engine::synth::rz, within its share of the budget (below). Its T count is the word's own, never a formula; each distinct angle is synthesised once, and the answer's rotations lists up to 64 of them with their count, t_count, word length (gates), the word's distance to the rotation, and the denominator exponent k.

Field	Meaning
qubits, ancillas, logical_qubits	the program's qubits, the ladders' ancillas, and both
measurements, resets	measurements (a reset counted as one)
clifford_gates, t_gates, toffolis	the circuit's gates by cost (t_gates excludes the rotations' words)
rotations, angles, rotation_t	rotations, distinct angles, and the T gates in all their words
t_states	t_gates + rotation_t + 4·toffolis: the planar model's T states (a CCZ state costs four)
non_clifford_depth	layers of an as-soon-as-possible schedule in which only non-Clifford gates take a layer; a Clifford gate takes none but orders what follows on its qubits
rotation_layers, rotation_steps	the layers holding a rotation, and over them the sum of each layer's longest word in T gates
t_depth	the sum over the layers of each layer's longest T sequence: 1 for a T or a Toffoli (a CCZ state), the word's T count for a rotation
depth	the total depth of the Clifford+T+Toffoli circuit: every gate one layer, a rotation its word's length, every measurement one
ladders, bound	gates written through ancillas; exact, or upper for a branching program

The budget (epsilon)

The budget B is the probability that the run fails. As in the planar model, it is shared evenly among the parts the program uses: logical errors, distillation (when there are T states) and synthesis (when there are rotations). With rotations and T states each part gets B/3.

The synthesis share S is shared evenly by the R rotations: each = S/R (at most 1/2). Each rotation's word is within each of it in the operator norm, up to a global phase, its distance recomputed from the word itself. By the triangle inequality the whole circuit is within bound = Σ distance ≤ S of the program, so its output distribution is within S in total variation. A share below 10⁻¹⁵, the synthesiser's floor, is refused (QE04).

Field	Meaning
budget, synthesis, each	B, S and S/R
rotations, angles	R, and the distinct angles synthesised
bound	the sum of the words' distances, at most synthesis
t_per_rotation	the fewest and the most T gates a word took

A word's T count grows as about 3·log₂(1/ε). That is exact search over Clifford+T operators; synthesis that measures and falls back reaches fewer T gates per rotation and is not assumed here.

Layer 2: the layout

The planar model (quantum_resource, parallel-synthesis sequential Pauli computation) takes three numbers:

• tiles Q = 2N + ⌈√(8N)⌉ + 1 for N logical qubits (the ancillas included);
• logical steps, at least C = M + R + T + rotation_steps + 3·X for M measurements, R rotations, T T gates and X Toffolis: a rotation layer takes as many steps as its longest word has T gates, so this is where each rotation's real T count enters;
• T states t_states, as above.

Layer 3: the physical estimate (estimate, frontier)

On a physical qubit and a planar code:

• the code distance d is the smallest odd distance with Q·C·P(d) ≤ B_logical, where P(d) = a·(p/p*)^((d+1)/2) is the logical error per tile per step at physical error p;
• T factories are 15-to-1 distillation, up to three rounds, each the space-efficient or the Reed–Muller unit, on physical qubits or on a code patch: the search over all of them is exhaustive, keeping the factory of the smallest space-time volume that meets t_target = B_distillation / t_states per state. When the raw T error already meets it, there is no factory;
• enough factory copies run that the program's T states arrive within its runtime.

The clock. By default a Toffoli takes three logical steps, as the planar model has it. On the reaction-limited clock, "clock": {"reaction_us": t} (wai-quantum estimate --reaction-us t), a Toffoli has its Clifford fixups teleported away from the data and takes one tick: the slower of the reaction time t and the CCZ supply, the rule quantum_arch's clock takes too (arXiv:1905.09749 §2.11). Then:

• the Toffolis' 3·X steps leave the steps, and X ticks join the runtime: runtime = steps × τ(d) + X × tick, every Toffoli after the one before, as the layout runs its steps;
• the distance holds the tiles' error over the whole runtime;
• the factories are as many as the T states need over the runtime, and at least as many as deliver a CCZ state (four T states) every tick, so the supply keeps up and a tick is the reaction time;
• a slowed program stretches its ticks as its steps: s times the reaction time;
• a reaction includes the logical measurement it reacts to (arXiv:1905.09749 App. B.1), so a reaction time shorter than a measurement on the qubit is refused (QE08): the 100 µs qubits have no 10 µs tick. wai-quantum estimate --qubit all --reaction-us t shows such a qubit as refused, with the reason, beside the others.

Without a clock, or with "steps", the answer and its receipts are what they were before the clock was named, bit for bit.

Field	Meaning
qubit, code, distance, slowdown	the qubit, the code (with its calibration), d, and how many times slower than the fewest steps the program runs
physical_qubits = algorithm_qubits + factory_qubits	tiles × qubits per tile, and the factories'
factories, factory_fraction	factory copies, and their share of the physical qubits
runtime_s, steps, step_us	wall-clock time = steps × the step time τ(d); on the reaction-limited clock, steps are the lattice-surgery steps alone and the runtime adds the ticks
clock	on the reaction-limited clock only: reaction_us, tick_us (at this slowdown) and the toffolis run on ticks
tiles, tile_qubits	Q and the physical qubits of one tile at d
logical_error	P(d), per tile per step
t_states, t_target	the T states and the error each must meet
budget	the logical, distillation and synthesis shares
factory	its qubits, duration, output error, and each round: unit, distance, copies, qubits of one copy

The frontier runs the program at slowdowns 1, 2, 4, … up to max_slowdown on each code the qubit supports, and keeps the estimates that no other beats on both physical qubits and runtime, fastest first. Running slower needs fewer factories, until one suffices; past that a slower program only needs a larger distance. The estimate (the headline) is the one of smallest space-time volume at full speed; it is on the frontier, marked headline.

The calibration (calibration)

The planar model assumes a = 0.03, p* = 0.01 for the surface code on gate-based qubits. Here they are fitted instead to what this crate's own decoders achieve on the rotated surface-code memory experiment (quantum_frame::surface_code_memory: d rounds, every noise knob at p, circuit-level noise), sampled once per point and decoded twice on the same shots:

Calibration	Decoder	a	p*
exact_matching	exact minimum-weight perfect matching (quantum_match)	0.0233	0.01004
union_find	union-find, near-linear time (quantum_uf)	0.0214	0.00952
assumed	none: the planar model's constants	0.03	0.01

The grid is d ∈ {3, 5, 7} by p ∈ {0.002, 0.003, 0.004, 0.005}, with 100,000 shots per point at d = 3 and 5 and 25,000 at d = 7, seed 1. The fit is least squares on ln P − x·ln p = ln a − x·ln p* with x = (d+1)/2, each point weighted by its failure count (quantum_match::fit_code_model). The table of failure counts is in the crate (engine::estimate::calibration::POINTS); a release build's test measures every point again and requires the same counts, and cargo run --release --example estimate_calibration --features full prints them. wai-quantum lab qec --fit measures the exact-matching grid the same way.

The fits apply to the surface code on gate-based qubits, what the experiment measures. A qubit whose error rate lies outside 0.002 to 0.005 (every reference qubit's does) uses the fitted form extrapolated, and the answer says so (extrapolated: true). Measurement-based qubits keep the planar model's assumed surface and Floquet-code models (applies: false): no decoder here has measured them.

Documents

Logical counts are the flat JSON object resource estimators read: numQubits, tCount, rotationCount, rotationDepth, cczCount, ccixCount (AND gates, each one CCZ state) and measurementCount. The memory counts (numComputeQubits, readFromMemoryCount, writeToMemoryCount) are read only as zero; an unknown key is refused.

Routines are the open interchange format for a program as routines and their costs, version v1: {"version": "v1", "program": routine}, a routine with a name, ports (input, output or through, each with a size), resources (additive, multiplicative, qubits or other, each with a value), children, connections between their ports ("a.out -> b.in" or {"source", "target"}), input_params, local_variables, linked_params and meta. A document is checked against the schema as far as the counts need: names, directions, resource types and value types, unique names among siblings, and every connection's ends on a port of the routine or of one of its children. A routine's totals are its own resources where it states them, else its children's (additive ones add, qubits ones take the largest child's, multiplicative ones multiply). The counts are read by name: T_gates, toffs, rotations, rotation_depth, measurements, and a qubits resource (else the root's port sizes); other names are listed as not read. A symbolic value (an expression in the routine's parameters) and a repetition are refused.

A document gives no angles, so each of its rotations costs the most T gates any of eight reference angles, (2k+1)·π/17, needs within its share. Its digest is BLAKE3 of the document's canonical JSON, and its t_depth and depth are not known. A routine without rotation_depth takes each rotation as its own layer, and says so.

export: "counts" and export: "routine" write a program's counts in either form; the routine carries the depths, the ancillas, each rotation's share and the program's digest under meta.

The answer and its seals

{"request", "result"}, the result holding format (wai.quantum.estimate/1), program (origin, digest: BLAKE3 of the program's text as given, qubits, bound), counts, rotations, epsilon, calibration, options, estimate, frontier, notes (the model's assumptions, in words) and, when asked, export.

Each estimate's figures carry a receipt of the resource-estimate family (kind: "quantum-resource"): its job hash binds the counted program (its origin, its digest, every count, the ancillas, the rotations' T, the depths, the budget, the synthesis share, each rotation's share, the bound and the layout), the qubit, the code with its calibrated constants as exact IEEE-754 bits, and the slowdown; its result hash binds every figure of the estimate down to each factory round. On the reaction-limited clock the job is a clocked job (quantum_resource_receipt::ClockedJob): its hash is a form of its own, wai:resource-job-clocked\x01 over the job's hash and the reaction time, so a receipt sealed on one clock never verifies as sealed on the other. Such a receipt also says so itself: its clock member gives the runtime its steps do not account for (tick_time_ns_bits, tick_time_s), read from the figures it signs, and a step-clock receipt has none. How long one tick was is the job's. The frontier's receipts name the headline's as their parent. The whole result is then sealed in a job's form, so any surface's verify checks it as it checks a job.

engine::estimate::verify (wai-quantum verify, POST /v1/verify, verify_quantum_result and verify_quantum_receipt, verify_estimate in Python, engine_estimate_verify in a page) checks more: every receipt is signed by the key that sealed the answer and the frontier names the headline, and the request re-run here gives the same jobs, the same estimates bit for bit, and the same figures, counts and notes.

Refusals

Code	When
Q…	the reader's own codes: the program does not read
QE02	a step jumps back: no count bounds the program
QE03	more distinct rotation angles than an estimate synthesises (4096; 256 on the service)
QE04	a rotation's share of the budget is below the synthesiser's floor (10⁻¹⁵; 10⁻¹² on the service)
QE05	nothing to estimate: no qubits, or no measurement, T gate, rotation or Toffoli (no logical step)
QE06	the physical model refuses: the qubit's error is at or above the code's threshold, no distance up to 51 meets the logical share, or no factory meets the T target
QE07	a document that does not read: a key or a value that is not one, a symbolic value, a repetition, a schema violation
QE08	a request that does not read: the program, the budget, the qubit, the calibration, the slowdown, the clock or the export; or a reaction time shorter than a measurement on the qubit

What it assumes

• The planar model's assumptions: uniform, independent circuit noise; free transport of T states; smooth T consumption; lattice-surgery patches of a planar code. Block codes, magic-state cultivation and yoked storage are in quantum_arch (wai-quantum lab arch) and are not used here.
• A Toffoli is one CCZ state, four T states in the model's count, and its uncomputation in a ladder is another Toffoli (measurement-based uncomputation, which needs none, is not assumed).
• Classical control (the latency of a branch on a measured bit) is not modelled, except as the reaction-limited clock's tick when that clock is asked for. On either clock every Toffoli follows the one before: a program's Toffoli depth is not read.
• A rotation under two or more controls (ctrl(2) @ rz(θ), and rx, ry, u the same) is counted as the reader writes it, through its phase polynomial, not through ancillas.
• The calibrated code model is fitted where it was measured and extrapolated elsewhere; its prefactor and threshold are fits, not bounds.

How it is checked

• The planar model reproduces its source's published tables, distances and factory counts (quantum_resource's tests).
• The counts of programs whose counts are known exactly: a Bell pair, T chains in series and in parallel, the ripple-carry adder (2n Toffolis), the QFT (3(n−1) T gates and 3(n−1)(n−2)/2 rotations), gates under three and four controls.
• Every ladder is held to the gate it replaces on dense unitaries: the estimate's circuit, with its ancillas at |0⟩, acts as the program and returns them to |0⟩.
• Each rotation's T count is the synthesiser's for that angle and share, and the bound is at most the synthesis share.
• The distance is the smallest odd one the calibrated model allows; the frontier is Pareto and holds the headline.
• The documents meet the schema, the fixture's totals are known, and a program's counts exported and read back give the same estimate.
• The calibration table is what the decoders measure (every point, in a release build).
• An estimate is the same bytes natively, as a WASI component and in a browser (CI compares them); a changed figure, program or receipt fails verify.