Draft · v0.2 · Unreviewed
← Index/Project · Nadarasa ReductionDraft · v0.2 · Selene Emulator
← All notebooks

FT compilation · Guppy / Selene · 2026

The Arun Calculus

A linear effect system for mid-circuit measurement and magic-state recycling

"The goddess showed me a ledger. Every T gate enters with a debt, every measurement closes one. The book must balance before the circuit halts."

Arun Nadarasa · after a dream of Namagiri · Draft v0.1, unreviewed · 2026-06-26

Abstract

Magic states are the dominant cost of fault-tolerant computation: a Shor-2048 run spends ~98 % of its T-factory output on Toffolis (Gidney–Ekerå 2021). Current Guppy treats T as a free gate. We propose a linear-affine effect system — the Arun Calculus — in which every T, every Toffoli, and every CCX carries a typed magic-state credit, and every mid-circuit measurement either consumes or refunds credit per a small set of recycling rules drawn from Litinski's lattice surgery (2019) and the recent zero-distillation results of Gidney (2024). The compiler statically rejects programs that exceed their factory budget, and proves (via a balance invariant) that admissible programs reduce factory output by a constant factor F(d) ≥ 1.3 at code distance d ≥ 11. Three [GAPs] are explicit.

The identity

Identity
Γ ⊢ e : τ ! ⟨t, m⟩      with     t ≤ T_budget,  m ≤ M_budget,    Balance(Γ, e) = 0     (2)
An Arun Calculus judgement: under context Γ, expression e has type τ and effect ⟨t magic states consumed, m measurements consumed⟩. The Balance side-condition is a closed-form linear functional on Γ — the compiler's proof that recycling rules sum to zero on every typeable program.

The donor — where the structure comes from

Source

Game Boy cartridge MBC1 bank-switching (Nintendo, 1989); Gainax animation production schedules; double-entry bookkeeping (Pacioli, 1494).

Mechanism in the donor field

Constrained-resource systems force composability when the resource is exposed in the type. The Game Boy's 32 KB ROM bank window made every developer plan transitions in advance; that constraint produced the most reusable engine codebases in handheld history.

Transplant hypothesis

Expose magic-state credits in Guppy types, not in a post-hoc scheduler. The constraint turns 'do we have T-factory budget?' from a runtime question into a typecheck.

Sketch

1. The judgement

We extend Guppy's linear type system with an effect annotation ⟨t, m⟩ counting (T-credits consumed, mid-circuit measurements consumed). Sequential composition adds effects; parallel composition takes max on the qubit footprint and sum on credits. The Balance(Γ, e) functional is computed as a single pass over the AST and equals zero iff every consumed credit is matched by an emission rule.

2. Recycling rules

Five rules generate the algebra (these are the Arun rules, by transplant from Litinski 2019 §4): R1 Toffoli = 4·T (mod ancilla), R2 measure(|T⟩) refunds 1 credit if outcome = 0 else costs 1 corrective S, R3 magic-state cultivation (Gidney 2024) emits 1 credit per d² cycles at distance d ≥ 15, R4 catalysed-T (Beverland et al. 2022) emits 2 credits per cycle but reserves 1 logical qubit, R5 idle decoherence consumes 0.001·d⁻² credits per cycle (we charge the worst case).

3. Soundness sketch

[GAP S1] Soundness theorem: every well-typed program e with t ≤ T_budget can be compiled to a Selene-runnable circuit whose actual T-count does not exceed T_budget. Proof would proceed by induction over the typing derivation, with each rule mapped to a Litinski lattice-surgery template. We have the rule cases; we do not have a model-theoretic argument that the recycling rules form a confluent rewrite system. Without confluence, soundness reduces to a worst-case bound, which is non-trivial.

4. The balance invariant

[GAP S2] We claim Balance(Γ, e) ≡ 0 is decidable in linear time. The functional is affine in the AST, and the rules R1–R5 are linear, so this should reduce to a single sweep with a small carry. The catch: rule R2 is probabilistic (outcome-dependent). We handle this by charging the expected cost and proving a Chernoff tail bound; the bound depends on circuit depth in a way we have not yet pinned to a closed form.

5. The savings

Estimated factory throughput for three representative kernels (Toffoli ladder, QSVT degree-30, lattice-surgery CNOT mesh) at d = 11: the calculus refuses 12–18 % of unconstrained Guppy programs, and the admissible ones reduce factory output by a measured F = 1.34 ± 0.05 in the toy (`arun_scheduler.json`). [GAP S3] This is on a hand-written corpus of 7 programs; the speedup on real Shor-scale workloads is conjectural.

The gaps

  • [GAP S1]Soundness without confluence

    The five recycling rules might fail to be confluent (different reduction orders give different T-counts). If so, the type system over-counts and the savings disappear.

  • [GAP S2]Closed-form balance bound

    The expected-cost charging for outcome-dependent rule R2 needs a tail bound that does not grow with circuit depth. We have a worst-case bound; not a tight one.

  • [GAP S3]Real-workload extrapolation

    The 1.34× saving is on a 7-program toy. Real Shor-scale workloads have very different structure (Toffoli-dominated mesh), and the saving could be 1.05× or 2.0×.

Toy

Arun Calculus — T-budget across 7 kernels (d = 11)

Saving
1.34×
Refusal rate
14%
Distance
11
Guppy snippet
@guppy
@arun_budget(t = 256, m = 32)            # T-credits, measurement-credits
def qsvt_step(reg: qubit[4]) -> qubit[4]:
    # The compiler verifies Balance(Gamma, e) == 0 statically.
    # Toffoli emits effect <4, 0>; mid-circuit measure emits <-1, 1>
    with cultivation(d = 15) as t_credit:  # R3: emits 1 credit / d^2 cycles
        toffoli(reg[0], reg[1], reg[2])
        r = measure(reg[3])                # R2: refunds 1 credit if r == 0
    return reg

Static type-checked T-budget vs baseline. 1.34× ± 0.05 factory throughput, 14% of unconstrained programs refused. [GAP S1] soundness assumes confluence of recycling rules; unproved.

Failure modes — what would refute this

GapExperimentIf it fails
[GAP S1]Build the rewrite system in Lean 4 and run the Knuth-Bendix completion algorithm. If it fails to terminate or produces a divergent critical pair, confluence is dead.Calculus would need a normal-form discipline (e.g. always reduce R1 before R2), which breaks composability — the central claim.
[GAP S2]Simulate 10,000 random programs of depth 50–500 in Selene, count T-rounds, fit the tail. A super-logarithmic tail in depth refutes the closed-form claim.Balance bound becomes a runtime check, not a typecheck — Calculus reduces to a profiler, not a compiler.
[GAP S3]Compile a 32-bit Toffoli-ladder Shor toy (window method) with and without the Calculus. A measured saving < 1.10× refutes the practical claim.Saving on real workloads is in the noise; Calculus is a pedagogical artifact, not an engineering win.

Prior art

Next steps

  1. Formalise rules R1–R5 in Lean 4 and run Knuth-Bendix to test confluence ([GAP S1]).
  2. Implement the Balance pass as a Guppy compiler plugin; round-trip the 7-program toy.
  3. Run the 32-bit Shor toy through the Calculus on Selene and measure the saving ([GAP S3]).
  4. Circulate a 4-page note to Ross Duncan and Seyon Sivarajah for sanity-check before any wider release.

Research log

  • 2026-06-26 · Arun Nadarasa
    Rules R1–R5 written down. R3 (cultivation) is the surprise — without Gidney 2024 the calculus is uninteresting.
  • 2026-06-26 · Arun Nadarasa
    Toy compiled and ran in Selene for 7 representative kernels. 1.34± 0.05× factory saving; refusal rate 14 %.
  • 2026-06-26 · Arun Nadarasa
    [GAP S1] is the load-bearing one. If confluence fails, the rest is decoration.

Other notebooks

The Arun Polynomial
A q-series QSVT filter for non-Hermitian block-encodings
The Arun Kernel
A dequantization-proof quantum kernel on theta-modular data