# 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. ```sh runnable 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 ```qasm file=ladder.qasm 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: ```console runnable $ 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) | | `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. | 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)` | | `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. 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 or the export | ## 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. - 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`.