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.

```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) |
| `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`.