Transaction-Science/open-standards
Watch
1
0
Fork
You've already forked open-standards
 0
Code Issues Pull requests Projects Releases 17 Packages Wiki Activity Actions 132
open-standards/wai/wai-quantum/docs/estimate.md
Transaction Science c4c1294e00 wai-quantum: documentation that runs in CI, its drift fixed, an index of every page, and a changelog entry 
wai/tools/quantum-docs/check_docs.py runs every block marked runnable on the
pages docs.json names (the engine, the command line, the service, Python,
the Studio, the desktop app, the editors, the providers, the compiler,
estimates, verdicts, the feature matrix, the course and the agent skill) in
a scratch directory of fixtures, holds each shown output to the real one,
verifies every receipt a block writes, builds and runs the Rust blocks, and
checks every block that cannot run for the commands and flags it names,
every wai-quantum command in the prose, every relative link and every
dependency shown; a translation must hold its English page's code. ci.sh
builds the command line, the service and the wheel and starts a service, as
wai-quantum-docs.yml runs it, beside the course's and the locales' tests.

Drift fixed: the crate pinned "0.4", named an unrelated crate for the command
line, ran its research tools outside lab, claimed the whole suite under
wasip2, and split its feature table from its header; the command line's
README said the reader refuses while, inv and pow, used placeholders and
optional flags that do not run, and merged versions that do not exist; the
estimate page's output lacked its receipts line; build steps now match CI.
An observable may lead with its coefficient ("0.5 X2"), as documented.

Co-Authored-By: Claude Opus 5.5 <[email protected]>
2026-10-28 08:43:06 -04:00

364 lines
20 KiB
Markdown
Raw Permalink Blame History

This file contains ambiguous Unicode characters

This file contains Unicode characters that might be confused with other characters. If you think that this is intentional, you can safely ignore this warning. Use the Escape button to reveal them.

# 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`.
Reference in a new issue View git blame Copy permalink