betaFeedback

WorksPhysics and Astronomy

Latency-Preserving Rewrites and Translation Validation for Dynamic Quantum Circuits

Abstract

A dynamic quantum circuit measures qubits during a run and chooses later operations from the outcomes. These branches make the qubits wait: the outcome must reach the classical controller, and the controller must decide. We present qlin, a compiler that reduces this waiting time. qlin moves operations out of branches without delaying the program, a property proved in Lean 4. For error-correction decoders, which branch on syndromes that are almost always zero, qlin compiles the likely syndromes into one multiway branch and keeps the original program for the rest. A cost model decides when a classically controlled gate should become a quantum-controlled gate instead. On all benchmarks, qlin checks that the compiled program computes what its source computes, and the checker is proved sound in Lean 4. At the published per-decision cost of the QICK controller (42 ns), 10 of 65 programs run at least 10% faster than the best baseline in our cost model, up to 91.2%, mostly because one multiway branch replaces a long chain of if statements. On the register-transfer logic of the QubiC controller, a compiled distance-5 repetition decoder selects its correction in 21.3 instead of 151.1 expected cycles. Timing runs on an IBM device were too noisy to confirm or reject the model's ranking.

CCS Concepts: • Software and its engineering → Compilers; • Theory of computation → Program semantics.

Additional Key Words and Phrases: dynamic quantum circuits, mid-circuit measurement, speculative optimization, mechanized semantics, Lean

Introduction

A dynamic circuit measures a qubit, sends the outcome to a classical controller, and uses it to choose the next operations. Error-correction rounds, repeat-until-success loops, teleportation, and iterative phase estimation all work this way. A classically controlled operation waits for its measurement to end and then for a feedforward latency tfft_{\mathrm{ff}}. On IBM Heron devices tfft_{\mathrm{ff}} is about 600 ns [1], while a two-qubit gate on ibm_kingston takes 68 ns. The controller also spends time deciding a branch, and it can hold only a limited number of precompiled code segments.

Compilers for dynamic circuits mostly remove branches. Branch-aware quantum constant propagation (BQCP) removes branches whose condition is known at compile time and proves its analysis sound on paper [2]. Related passes simplify classically controlled operations by symbolic simulation [3], turn quantum operations into classical ones [4], or specialize code per branch [5]. The branches that survive these passes are still decided at run time, in all shots. Verified compilers also reach this setting. QPPM verifies in Lean a compiler for Pauli-product-measurement programs with classical feedback and certifies a depth bound for the candidates that it selects [6], and the type system of HyQ guarantees that all circuits are generated before the program runs [7]. Neither proves that a rewrite cannot delay a program whose timing includes feedforward latency, and a rewrite that keeps the semantics can make a program slower (§ 4).

This paper presents qlin, a compiler that reduces the time a dynamic circuit spends on classical control. It has three parts. First, a normal form moves operations out of branches (hoist and merge) without delaying the program: for all moves in an ideal timing model, and for moves of single operations with a controller that decides one branch at a time, with proofs in Lean. qlin checks the compiled output against its source, and the checker is proved sound in Lean, so a bug in the Rust passes shows up as a rejected output, not as a wrong program. Second, a fast path for likely outcomes. Most of the probability of an error-correction round sits on low-weight syndromes. qlin

Author’s Contact Information: Rylan Malarchick, [email protected], Embry-Riddle Aeronautical University, Daytona Beach, Florida, USA. fixes a reference outcome rr and a budget tt, and it compiles a multiway branch (a switch) with one case per outcome within tt bits of rr. Any other outcome takes an exit edge to the unchanged program. This is the hot and cold split of trace scheduling [8] and deoptimization [9], with two differences: the profile comes from a noise model, and the exit edges sit before any specialized operation, so the fallback needs no compensation code on a quantum state that the controller cannot read. Third, a cost model chooses, per branch, between classical feedforward and a quantum-controlled gate (deferred measurement). Deferring can remove all runtime branches of teleportation and still be slower on some devices, so the choice is a search over expected cost.

The fast path helps only when the controller spends time on a branch decision beyond the feedforward wait. We take that time from published controllers, 14 ns per control-flow instruction on QubiC 2.0 [10] and 42 ns per conditional jump on QICK [11], and from our measurement of 3.45 μ\mus on ibm_kingston. A controller can dispatch a multiway branch by a jump table, by a decision tree on the bits, or by a chain of compares, and we evaluate all three.

Contributions.

  1. A normal form whose hoist and merge steps never delay the program, at any position and in any sequence: for all moves in an ideal timing model, and for moves of single operations with a serial controller. The proofs are in Lean, and all side conditions are shown to be necessary (§ 4).

  1. Translation validation of the normal-form and fast-path passes: all 976 outputs on our benchmarks pass, and the 66 normal-form outputs also pass a timing check in both models. The checkers are proved sound in Lean (§ 7.2).

  1. A semantics over classical-quantum (cq) states with a density-matrix model, in which we prove the normal-form rules, the fast-path step, the Pauli sink (which moves Pauli corrections past Clifford gates), and the direct defer rule, with Lean’s standard axioms only (§ 3 and § 7).

  1. The fast-path construction, proved sound for any set of cases and therefore for all budgets and size limits (§ 6).

  1. A branch-and-bound search over defer choices, which finds the exhaustive optimum on 180 of 180 rows (§ 5).

  1. An evaluation on 50 programs against BQCP, Qiskit, and TKET and on 16 error-correction programs of 13 to 22 qubits, with a cycle count on the logic of the QubiC controller, an accounting check against the Selene emulator, and timing runs on ibm_kingston (§ 8).

A label in brackets gives the support for a claim: [Lean-checked], [exhaustive], [empirical], or [hand-derived], and for a number [modeled], [emulated], [RTL-simulated], or [measured]. Section A lists the claims with their evidence.

At the QICK cost with tree dispatch, 10 of 65 programs run at least 10% faster than the best baseline, up to 19.2% [modeled]. They are noisy repetition, Steane, and surface codes, whose lookup decoders have many branches on few bits. Most of the gain comes from replacing a chain of ifs by one multiway branch. Without the sink, a full switch over all outcomes comes within 0.3% of the fast path, and the budget tt keeps most of the gain with a fraction of the cases. With no controller time per branch, 4 programs gain 10% or more, at most 16.0%, all from the sink. On the five-qubit code the best defer program is fastest. On ibm_kingston, three timing experiments could not separate the variants (§ 8).

Overview

Figure 1 (left) shows one round of the three-qubit bit-flip repetition code. Qubits q3 and q4 collect the parities of neighboring data qubits, and a lookup decoder applies one correction per nonzero

Two qlin code listings for one round of the three-qubit repetition code and its fast path

Figure 1. Left: one round of the three-qubit repetition code with a lookup decoder, in the qlin text format. Right: the fast path for the reference outcome r=00r = 00 and budget t=1t = 1, as printed by qlin fastpath. The default case is the exit edge. It runs the source decoder unchanged.

qubits 5
bits 2
x q0
cx q0 q1
cx q1 q2
cx q0 q3
cx q1 q3
cx q1 q4
cx q2 q4
measure q3 -> c0
measure q4 -> c1
if c0 & !c1 { x q0 }
if c0 & c1 { x q1 }
if !c0 & c1 { x q2 }
... (same prefix) ...
measure q3 -> c0
measure q4 -> c1
switch c0 c1 {
  case 0 0 { }
  case 0 1 { x q2 }
  case 1 0 { x q0 }
  default {
    if c0 & !c1 { x q0 }
    if c0 & c1 { x q1 }
    if !c0 & c1 { x q2 }
  }
}

syndrome. The decoder is three ifs on the same two bits. An if is a runtime branch: it waits for both measurements, plus tfft_{\mathrm{ff}}, and a serial controller spends tbrancht_{\mathrm{branch}} deciding it.

Step 1: the normal form. The compiler first puts the program in a normal form: it folds constant conditions, hoists an op that both arms of an if contain, and merges a common suffix. Here all three ifs have an empty else, so nothing moves, and the three corrections stay runtime decisions. § 4 proves that these moves never delay the program.

Step 2: classical or coherent control. A correction if c0 & !c1 {x q0} could instead run as a coherent gate controlled by q3 and q4, with the measurements moved after it. That gate is a three-qubit gate with a negated control. With the assumed three-qubit gate time of our starting cost model, the search of § 5 keeps all three corrections classical. On jeff/teleportation the same search defers both corrections and cuts the modeled expected latency from 2090 to 1136 ns.

Step 3: the fast path. The three ifs read only c0 and c1, and they write neither bit. They form one dispatch group. The fast path replaces the group by one switch on c0 c1 (Figure 1, right). For a value within the budget, its case runs only the arms that the value selects. Value 11 is outside M1M_1, so it takes the default, which is the original group. The fallback starts from the state that the source program would have at the same point, so no compensation code is needed. A controller that spends tbranch=200t_{\mathrm{branch}} = 200 ns per decision now makes one decision instead of three if it has a jump table, and two with a decision tree on the two bits. With the jump table the modeled expected latency drops from 2372 to 1972 ns. With tbranch=0t_{\mathrm{branch}} = 0 both programs take 1772 ns, because the switch waits for the same two measurements [modeled]. This program has no noise, so its syndrome is 00 in all shots. § 8 uses variants with injected errors.

Step 4: why it is sound. The Lean theorem fastpath_step (§ 6) says that the switch equals “group, then rest” when three conditions hold. The group conditions read only the switch bits GG. The group writes no bit of GG. A case body equals the arms that its value selects, followed by the rest. All three hold here. The theorem holds for any set of cases, so it holds for all budgets tt and all size limits. It is stated over any leaf semantics that satisfies two axioms, and § 3 gives density-matrix model of gates, reset, and measurement in which both axioms are theorems. The checker of § 7.2, proved sound in Lean, also validates the switches that the Rust code builds.

Programs and Semantics

The Intermediate Representation (IR)

A program has qubits q0,…,qn−1q_0,\ldots,q_{n-1} and classical bits c0,…,cm−1c_0,\ldots,c_{m-1}. A block is a list of operations (ops):

o::=g q⃗∣measure⁡ q→b∣reset⁡ q(leaves)o ::= g\ \vec{q}\mid\operatorname{measure}\ q\to b\mid\operatorname{reset}\ q \qquad\text{(leaves)}
∣if⁡ e {A} else⁡ {B}∣loop⁡ max⁡ K {B} until⁡ e∣switch⁡ b⃗ {case⁡ v⃗i {Bi} …default⁡ {D}}\mid\operatorname{if}\ e\ \{A\}\ \operatorname{else}\ \{B\}\mid\operatorname{loop}\ \max\ K\ \{B\}\ \operatorname{until}\ e\mid\operatorname{switch}\ \vec{b}\ \{\operatorname{case}\ \vec{v}_i\ \{B_i\}\ \ldots\operatorname{default}\ \{D\}\}

Here gg is a gate with constant angles, ee is a Boolean expression over bits, AA, BB, BiB_i, and DD are blocks, and KK bounds the iterations of a loop that exits when ee holds after an iteration. A switch runs the first case whose values equal the bits b⃗\vec{b}, else the default. The IR has no static loops (the parser unrolls repeat), and a bit-dependent angle is an if. Figure 1 shows a program in the text format.

Definition 3.1 (Footprint). The footprint fp⁡(o)=(Q,R,W)\operatorname{fp}(o)=(Q,R,W) of an op is its set of qubits QQ, the bits RR that it reads, and the bits WW that it writes. A measurement writes its bit. An if, a loop, and a switch read the bits of their condition, and a compound op takes the union over its parts. Two footprints are disjoint, (Q,R,W)⊥(Q′,R′,W′)(Q,R,W)\perp(Q',R',W'), when Q∩Q′=W∩W′=W∩R′=R∩W′=∅Q\cap Q'=W\cap W'=W\cap R'=R\cap W'=\varnothing.

All moves in this paper use this one relation, and the Lean definition copies the Rust one.

Semantics over cq-states

Definition 3.2 (cq-state). Let DD be an additive commutative monoid. A state is a function s:Assign⁡→Ds:\operatorname{Assign}\to D, where an assignment β∈Assign⁡\beta\in\operatorname{Assign} gives a value to all bits. For a condition cc, the restriction s∣cs|_c keeps the branches where cc holds: s∣c(β)=s(β)s|_c(\beta)=s(\beta) if c(β)c(\beta), else 00.

For a physical program, DD is the cone of unnormalized density operators on nn qubits, and s(β)s(\beta) is the quantum part on the branch where the bits equal β\beta. A block denotes the composition of its ops from left to right, and

⟦if⁡ c A B⟧s=⟦A⟧(s∣c)+⟦B⟧(s∣¬c),\llbracket\operatorname{if}\ c\ A\ B\rrbracket s=\llbracket A\rrbracket(s|_c)+\llbracket B\rrbracket(s|_{\neg c}),
⟦loop⁡ K B c⟧s=LK(s),L0(s)=s,LK+1(s)=(⟦B⟧s)∣c+LK((⟦B⟧s)∣¬c),\llbracket\operatorname{loop}\ K\ B\ c\rrbracket s=L_K(s),\qquad L_0(s)=s,\qquad L_{K+1}(s)=\left(\llbracket B\rrbracket s\right)|_c+L_K\left(\left(\llbracket B\rrbracket s\right)|_{\neg c}\right),
⟦switch⁡ G ((v1,B1)::cs) D⟧s=⟦B1⟧(s∣G=v1)+⟦switch⁡ G cs D⟧(s∣G≠v1),⟦switch⁡ G [] D⟧=⟦D⟧.\llbracket\operatorname{switch}\ G\ ((v_1,B_1)::cs)\ D\rrbracket s=\llbracket B_1\rrbracket(s|_{G=v_1})+\llbracket\operatorname{switch}\ G\ cs\ D\rrbracket(s|_{G\ne v_1}),\qquad\llbracket\operatorname{switch}\ G\ []\ D\rrbracket=\llbracket D\rrbracket.

A branch still in the loop after KK iterations stops there. This is the truncated trace that the implementation enumerates.

Definition 3.3 (Interpretation). An interpretation II gives a leaf an additive map on states and satisfies two axioms:

A1 (locality) A leaf commutes with s↦s∣cs\mapsto s|_c when cc reads no bit that the leaf writes.

A2 (disjointness) Two leaves with disjoint footprints commute.

Both axioms lift from leaves to all ops by induction on the op (den_restrict and den_comm) [Lean-checked]. A third fact follows from A1: an op keeps a bit at 0 on the support of the state when it does not write that bit (supp_den). Constant folding uses this fact. qlin knows the value of a bit only before any op writes it. It never infers a bit value from a quantum state, which is the job of a propagation pass such as BQCP [2].

A density-matrix model

The results of § 4 and § 6 hold for all interpretations. This subsection gives the physical one and proves that it satisfies A1 and A2, so that those results apply to quantum channels without a hand-checked step.

Fix nn qubits with computational basis {0,1}n\{0,1\}^{n}, and let DD be the complex 2n×2n2^{n} \times2^{n} matrices. For a set of qubits QQ, a matrix kk is local to QQ when kxyk_{xy} depends only on the values of xx and yy on QQ. Its lift acts as kk on QQ and as the identity elsewhere:

(lift⁡Qk)xy={kxyif x and y agree outside Q,0otherwise.(\operatorname{lift}_{Q} k)_{xy} = \begin{cases} k_{xy} & \text{if } x \text{ and } y \text{ agree outside } Q, \\ 0 & \text{otherwise.} \end{cases}

A Kraus map on QQ with operators K1,…,KrK_{1},\ldots,K_{r} is ρ↦∑i(lift⁡QKi)ρ(lift⁡QKi)†\rho\mapsto\sum_{i}(\operatorname{lift}_{Q}K_{i})\rho(\operatorname{lift}_{Q}K_{i})^{\dagger}. The leaves are:

  • a gate with matrix UU local to its qubits QQ: the Kraus map with one operator UU, applied on all branches;

  • reset q: the Kraus map on {q}\{q\} with operators ∣0⟩⟨0∣\lvert0\rangle\langle0\rvert and ∣0⟩⟨1∣\lvert0\rangle\langle1\rvert, on all branches;

  • measure q -> b: with PνP_{\nu} the projector on q=νq=\nu,

⟦measure⁡ q→b⟧s(β)=Pβ(b)(s(β[b↦0])+s(β[b↦1]))Pβ(b).\llbracket\operatorname{measure}\ q \to b\rrbracket s(\beta)=P_{\beta(b)}\bigl(s(\beta[b\mapsto0])+s(\beta[b\mapsto1])\bigr)P_{\beta(b)}.

The measurement collects both old values of bb and keeps the part of the state where qubit qq agrees with the new value of bb.

Theorem 3.4 (A1 and A2 for density matrices). In this model all leaves satisfy A1, and any two leaves with disjoint footprints commute (A2). (Spec.sem_restrict, Spec.sem_comm, and the interpretation CQ.interp) [Lean-checked]

The core of the proof is that lifts of matrices local to disjoint qubit sets commute (lift_comm). Entry (x,z)(x,z) of lift⁡Pa⋅lift⁡Qb\operatorname{lift}_{P}a\cdot\operatorname{lift}_{Q}b has one nonzero summand, at the basis state that agrees with zz on PP and with xx elsewhere. Both products equal axzbxza_{xz}b_{xz} when xx and zz agree outside P∪QP\cup Q, and 00 otherwise. Two measurements of different qubits into different bits commute because the two updates of β\beta commute and the projectors commute. As a check that the model is faithful, the Kraus operators of measurement and of reset satisfy ∑iKi†Ki=1\sum_i K_i^{\dagger}K_i=1 (meas_complete, reset_complete), so both are trace preserving [Lean-checked].

The Lean interpretation takes a table that assigns one of these operations to a leaf id. A leaf whose declared footprint does not cover its operation denotes the identity, which keeps both axioms true for all declared footprints. A leaf whose footprint is its own, as in all programs that the Rust code builds, denotes its operation (interp_leaf).

The Normal Form and a Latency Theorem

Replay latency

qlin scores a program by its expected replay latency under a cost model CC, which gives a duration to a leaf and the feedforward latency tfft_{\mathrm{ff}}. An outcome record RR gives the outcome of the kk-th measurement of a bit. The replay runs the trace that RR selects and keeps a state σ\sigma with five parts: the time ready⁡(q)\operatorname{ready}(q) at which qubit qq is free, the end time mEnd⁡(b)\operatorname{mEnd}(b) of the latest measurement of bit bb, the current bit values, a cursor per bit into RR, and a stop flag. An op runs with the set γ\gamma of gate bits: the condition bits of all enclosing if, switch, and loop exit. A leaf with footprint (Q,R,W)(Q,R,W) and duration dd finishes at

fin=max⁡(max⁡b∈γ(mEnd⁡(b)+tff),max⁡q∈Qready⁡(q))+df_{\mathrm{in}}=\max\left(\max_{b\in\gamma}\left(m\operatorname{End}(b)+t_{\mathrm{ff}}\right),\max_{q\in Q}\operatorname{ready}(q)\right)+d

which becomes the ready time of all q∈Qq \in Q and the measurement end of all b∈Wb \in W. A measurement reads its outcome from RR and advances the cursor of its bit. An if runs its taken arm with γ∪bits⁡(c)\gamma\cup\operatorname{bits}(c). A loop that does not exit within KK iterations sets the stop flag, and the replay skips all later ops. The makespan is the largest ready time. The expected latency weights the makespan of a record by its probability, which comes from one state-vector simulation of the source (at most 12 qubits).

We call this the ideal model. The block model adds a serial controller. An executed branch takes tbrancht_{\mathrm{branch}} of controller time and stalls the qubits in its footprint until the decision, taken or not. Numbers from these models are labeled modeled.

The normal form

The normal form (M0 in our tables) applies four moves:

  • fold a condition that is constant on the known bits, and keep the live arm;

  • hoist an op xx that both arms contain in front of the if;

  • merge an op xx that both arms contain to after the if;

  • unroll the first iteration of a loop.

Hoist and merge carry side conditions. Write pAp_A and pBp_B for the ops that xx moves past in the two arms, cc for the condition, and γ\gamma for the gate bits of the if:

Hoist∀y∈pA∪pB. fp⁡(x)⊥fp⁡(y)W(x)∩(bits⁡(c)∪γ)=∅if c (pA++x::A) (pB++x::B)⇝x; if c (pA++A) (pB++B)\begin{aligned} &\text{Hoist}\\ &\forall y \in p_A \cup p_B.\ \operatorname{fp}(x) \perp\operatorname{fp}(y) \qquad W(x) \cap(\operatorname{bits}(c) \cup\gamma) = \varnothing\\ &\text{if }c\ (p_A ++ x :: A)\ (p_B ++ x :: B) \leadsto x;\ \text{if }c\ (p_A ++ A)\ (p_B ++ B) \end{aligned}
Merge∀y∈sA∪sB. fp⁡(x)⊥fp⁡(y)∀y∈sA∪sB. W(y)∩γ=∅if c (A++x::sA) (B++x::sB)⇝if c (A++sA) (B++sB); x\begin{aligned} &\text{Merge}\\ &\forall y \in s_A \cup s_B.\ \operatorname{fp}(x) \perp\operatorname{fp}(y) \qquad\forall y \in s_A \cup s_B.\ W(y) \cap\gamma= \varnothing\\ &\text{if }c\ (A ++ x :: s_A)\ (B ++ x :: s_B) \leadsto\text{if }c\ (A ++ s_A)\ (B ++ s_B);\ x \end{aligned}

The conditions on γ\gamma matter only for latency. The semantic rules need only the disjointness conditions and, for hoist, W(x)∩bits⁡(c)=∅W(x) \cap\operatorname{bits}(c) = \varnothing (§ 7).

The dynamic core is the set of leaves that stay inside a runtime branch after all moves apply. It holds the unmatched ops of the dynamic ifs and the leaves of a loop body that repeats on a measured bit. The core leaves and the number of dynamic conditions are the program metrics of Table 3.

pipelineranfewer ffsmaller coremore dyn
bqcp4617170
qiskit_o047006
qiskit_o347006
tket34000

Table 3. Baselines on 50 benchmarks. “ran”: the pipeline produced a program that passed the semantics guard. “fewer ff”, “smaller core”: fewer dynamic conditions, or fewer core leaves, than the source. “more dyn”: more ops inside dynamic branches. Three programs are too large for the guard.

The latency theorem

Theorem 4.1 (C1: hoist and merge never delay the replay). For all cost models, records RR, gate bits γ\gamma, and start state σ\sigma that is not stopped: if one hoist or merge step under the side conditions above turns op oo into block o′o', and the replay of oo does not stop, then the replay state after o′o' is no later than the replay state after oo. That is, it has the same bit values, cursors, and stop flag, and no ready time or measurement end is later than the original. (hoist_latency, merge_latency) [Lean-checked]

The proof rests on two lemmas. The replay is monotone in its start state and in its gate bits (run_mono). An exchange lemma also holds: a block that writes no gate bit of a disjoint block can move in front of it without delay. A pointwise smaller state has a smaller makespan (makespan_le). The expected latency is a sum over records with nonnegative weights, so it does not grow either (hoist_expected_latency, merge_expected_latency) [Lean-checked]. The theorem covers the ideal model on records with no truncated loop. The expected forms score both programs on the outcome records of the source.

Theorem 4.2 (Closure of C1). Let P⇒EQP \Rightarrow_E Q hold when QQ follows from PP by hoist and merge steps at any position: in a block, in an arm of an if, in a loop body, or in a case or the default of a switch,

and by any sequence of such steps. Here EE bounds the enclosing gate bits (an arm adds its condition bits, a case adds the switch bits), and all steps meet the side conditions above with EE in the place of γ\gamma. If P⇒EQP \Rightarrow_{E} Q, then for all gate bits γ⊆E\gamma\subseteq E and all start states σ′≤σ\sigma' \leq\sigma, if the replay of PP from σ\sigma does not stop, the replay state after QQ from σ′\sigma' is no later than the replay state after PP from σ\sigma. (m0Steps_latency, m0Steps_expected_latency) [Lean-checked]

The proof is an induction on the derivation, with Theorem 4.1 at the root and the monotonicity of the replay in all contexts. A truncated loop stops the replay, and the latency report gives the probability of such records apart.

With a serial controller. The block model of § 8 adds a controller that decides one branch at a time. A hoisted if can then add latency (hoist_block_can_delay): on one program the normal form raises the expected latency from 2078 to 2208 ns [modeled].

Theorem 4.3 (C1 in the block model). If all hoisted or merged ops are leaves, and a merged leaf writes no enclosing gate bit and no condition bit, then Theorem 4.1 and Theorem 4.2 hold in the block model. (hoist_block_leaf, merge_block_leaf, m0StepsK_latency) [Lean-checked]

Why the conditions on γ\gamma. Without them a hoist can delay a program. In Figure 2 the outer if reads c0, and both inner arms end with measure q0 -> c0. Hoisting that measurement in front of the inner if keeps the semantics, but x q1 now waits for the new measurement of c0, because an op waits for the latest measurement of all enclosing condition bits. The expected latency rises from 1532 to 1690 ns [modeled]. A merge has the mirror problem: an op that moves past a new write of an enclosing bit waits for that write (1348 to 1506 ns on a second program). This rule of the replay is conservative: a controller that latched the condition at the decision would not wait.

A hoist that delays a program

Figure 2. A hoist that delays a program (3 qubits, 2 bits). Left: source, 1532 ns expected. Right: after a hoist that the condition on γ\gamma forbids, 1690 ns (modeled). The normal form instead keeps the measurement in the inner arms and merges it after the inner if.

Negative theorems show that the conditions on γ\gamma are necessary: without one, instances of the two programs above refute both steps (hoist_latency_needs_henc, merge_latency_needs_henc) [Lean-checked]. No measurement inside a branch of the 50 benchmark files writes a bit that an enclosing branch reads. An exhaustive check compares the normal form with all prefixes of the hoist and merge sequences at the top-level ifs, on all benchmarks with at most 12 qubits [exhaustive].

Expected Cost and the Defer Choice

The objective

The compiler scores a program by its expected replay latency over the outcome records. Two choices set it: which ifs to defer, which the search of this section makes, and the fast-path budget tt, which the evaluation sweeps under a limit SS on the number of case blocks. For a program with one dispatch group the expected cost splits as

E[cost⁡]=∑β∈Mtp(β) C(F,β)+∑β∉Mtp(β) (C(exit⁡)+C(G,β)),\mathbb{E}[\operatorname{cost}] = \sum_{\beta\in M_t} p(\beta)\,C(F,\beta) + \sum_{\beta\notin M_t} p(\beta)\,\left(C(\operatorname{exit}) + C(G,\beta)\right),

where FF is the fast path, GG the fallback, and pp the outcome distribution. With several groups an outcome can leave the budget at a later group, and the replay accounts for it. The objective is cost, not the size of the dynamic core. The deferred-measurement rewrite (defer) replaces a classically controlled gate by a quantum controlled gate and moves the measurement later. It removes a feedforward wait, and it costs a multi-qubit gate and sometimes a fresh qubit. With defer, teleportation keeps no runtime branch [hand-derived], but the coherent program is not faster on all devices, so the cost model decides.

The defer rule

A candidate is a top-level dynamic if. Its condition bits were last written by a top-level measurement, and its arms hold only gates with a controlled form. A deferred if reads its bits from a control qubit in one of two forms. The direct form uses the measured qubit itself, and the measurement moves to after its last user. It needs no other op on that qubit, no classical reader of the bit, and no new write of the bit in between. The copy form uses a fresh ancilla: cx q anc goes just before the measurement, and the gates use the ancilla.

Theorem 5.1 (Direct defer, one control bit). In the density-matrix model, let UU be any matrix local to a qubit set TT with q∉Tq \notin T, and let CvUC_vU be UU on TT controlled by qubit qq on value vv (the identity on TT when qubit qq holds ¬v\neg v). Then

[[measure⁡q→b; if⁡(b=v) {U}]]=[[CvU; measure⁡q→b]].\left[\left[\operatorname{measure} q \to b;\ \operatorname{if}(b=v)\ \{U\}\right]\right] = \left[\left[C_vU;\ \operatorname{measure} q \to b\right]\right].

(defer_cq) [Lean-checked]

The proof is an identity of matrices. With PwP_w, the projector on q=wq=w, the product Pw⋅CvUP_w \cdot C_vU equals U⋅PvU \cdot P_v when w=vw=v and PwP_w otherwise (proj_ctrl). Moving the measurement further, past ops that touch neither qq nor bb, is A2. The theorem covers the direct form with one control bit and one gate in the arm. Four cases stay outside Lean: the copy form (which needs a partial trace over the ancilla), conditions on several bits, XOR conditions, and arms with several gates. Simulation checks them [empirical], and symbolic evaluation checks two programs [Wolfram-checked] (§ 7).

Search

The search keeps a candidate classical or defers it. The objective is expected replay latency, with ties broken on fewer added multi-qubit gates, then fewer added qubits. For a partial assignment, the lower bound keeps the undecided ifs classical but relaxed: they skip the feedforward wait. On all records, relaxed is no slower than classical: a relaxed if runs its arms under fewer gate bits, and the replay is monotone in its gate bits (run_mono; Lean does not model relaxed ifs). It is also no slower than deferred: the base gate is no slower than its controlled form, it runs only when its condition holds, and the measurement does not move. This second part is hand-derived, and an exhaustive search checks the bound on all prefixes [exhaustive]. Branch and bound prunes with it.

Results. Over 188 benchmark and tfft_{\mathrm{ff}} rows (0, 150, 600, and 2400 ns, HERON_LIKE values), exhaustive search certifies 180 rows. Branch and bound finds the exhaustive optimum on 180 of them, with 0 bound violations [exhaustive]. At tff=600t_{\mathrm{ff}} = 600 ns the simulation check passed on 3046 scored search leaves. It did not run on 26 leaves, which need more than 12 qubits with their copy qubits. Table 1 lists the rows with candidates. Defer beats the normal form on 9 of the 21 benchmarks with candidates at this tfft_{\mathrm{ff}}. On jeff/teleportation the best program defers both corrections. It takes 1136 ns against 2090 ns for the source, with two added two-qubit gates and no new qubit [modeled]. The floor column is the relaxed bound at the root.

benchmarkcand.sourceM0bestfloordeferred+2q+q
dynamarq/cnot_ladder432317231712361080360
dynamarq/fanout432399239913761220380
dynamarq/five_qubit_code54278427835653213550
dynamarq/five_qubit_code_noisy54189418935653211550
dynamarq/ghz542310231012409984100
dynamarq/ipe335860586058605860000
dynamarq/long_range_cnot322074207411361016230
dynamarq/repetition3_031172117211721172000
dynamarq/repetition3_0_noisy31376137613761174000
dynamarq/repetition3_131340134013401340000
dynamarq/repetition3_1_noisy31541154115411342000
hand/mbqc_chain444632463216041108470
hand/repetition331172117211721172000
hand/teleportation21466146611041000220
jeff/iqft_335544554455445544000
jeff/iqft_5109320932093209320000
jeff/iqft_72113160131601316013160000
jeff/iqpe_335844584458445844000
jeff/iqpe_5109820982098209820000
jeff/iqpe_72113684136841368413684000
jeff/teleportation22090209011361000220

Table 1. Defer search at tff=600t_{\mathrm{ff}} = 600 ns, HERON_LIKE values (modeled, expected latency in ns). “cand.” is the number of candidates, “floor” the root lower bound, “+2q” and “+q” the added two-qubit gates and qubits of the best program.

The Fast Path: Speculation over Outcomes

Budget and construction

Fix a reference outcome rr: for a bit, the more likely value at that point of the program (ties go to 0). The weight of an assignment is the number of its bits that differ from rr. The budget MtM_t is the set of outcomes of weight at most tt, and for mm bits ∣Mt∣=∑k≤t(mk)|M_t| = \sum_{k \le t} \binom{m}{k} [Wolfram-checked for m≤12m \le12].

A dispatch group is a maximal run of consecutive top-level dynamic ifs whose condition bits GG are all written before the run and not written inside it. For a group gg, the rest ρ\rho of the program, and a remaining budget kk, the fast path is

Fk(g;ρ)=switch⁡G{case⁡ v:sel⁡v(g)++Fk−∣v∣(ρ)v∈{0,1}G, ∣v∣≤kdefault⁡(g++ρ),F_k(g;\rho) = \operatorname{switch} G \left\{ \begin{array}{ll} \operatorname{case}\ v : \operatorname{sel}_v(g) ++ F_{k-|v|}(\rho) & v \in\{0,1\}^{G},\ |v| \le k \\ \operatorname{default} & (g ++ \rho), \end{array} \right.

where ∣v∣|v| is the weight of vv and sel⁡v(g)\operatorname{sel}_v(g) replaces the ifs of gg by the arm that vv selects. FkF_k of a program with no further group is the program itself. A group stays generic when it has too many bits, or when the tree would pass the size limit SS of precompiled case blocks (4096 in our runs).

The default case is the exit edge, and it is the deoptimization point. In a classical JIT compiler, deoptimization must rebuild the frames of the unoptimized code from the state of the optimized code [9]. Here the default runs before any specialized op of its group, so the state at the exit edge is the state that the source program has at the same point. The fallback is the unchanged source, and the compensation code is empty. The price is that the fast path cannot speculate across a group boundary: a repair on exit would have to act on a quantum state that the controller cannot read.

In the block model, the source takes one controller decision per if. A switch takes one decision if the controller has a jump table, one per switch bit if it dispatches with a decision tree on the bits, and one per compare, up to the matching case, if it tests the cases in order. The fast path saves time when these decisions are fewer than the ifs that it replaces. A lookup decoder for mm syndrome bits has up to 2m2^m ifs, and a decision tree needs mm decisions, so the saving survives without a jump table. In the ideal model a branch costs only its feedforward wait, and a switch waits for the same bits, so the dispatch by itself saves no time [hand-derived]. It can cost a little: the code under the switch waits for all group bits, and at tbranch=0t_{\mathrm{branch}} = 0 the fast path is slower than the normal form on 8 programs, by at most 0.99% [modeled].

Soundness of the dispatch step

Theorem 6.1 (Dispatch step). For all interpretations, let gg be a block whose if conditions read only bits in GG and which writes no bit of GG. Let cscs be any list of cases such that for all cases (v,B)(v, B) the body satisfies ⟦B⟧=⟦sel⁡v(g)++ρ⟧\llbracket B\rrbracket= \llbracket\operatorname{sel}_{v}(g) ++ \rho\rrbracket. Then

⟦switch⁡ G cs (g++ρ)⟧=⟦g++ρ⟧.\llbracket\operatorname{switch}\ G\ cs\ (g ++ \rho)\rrbracket= \llbracket g ++ \rho\rrbracket.

(fastpath_step) [Lean-checked]

Case vv runs only on branches where the bits of GG equal vv. On those branches all ifs of the group take the arm that vv selects, because the group writes no bit of GG (A1, lifted). The cases and the default split the state, and the denotation is additive, so the sum equals the group. The theorem quantifies over the list of cases, so it covers all budgets, references, and size limits. The case body of FkF_k is again a fast path. A relation FastPathOf describes the programs that the construction can build, and induction over it gives ⟦Ft(P)⟧=⟦P⟧\llbracket F_t(P)\rrbracket= \llbracket P\rrbracket for the whole tree (fastpath_sound) [Lean-checked]. A negative theorem refutes the step when the group writes a dispatch bit (fastpath_needs_hw) [Lean-checked].

Pauli sink

A correction if whose arms are products of XX, YY, and ZZ can move forward. It passes an op with a disjoint footprint unchanged. It passes a Clifford gate on its qubits, and its arms are conjugated through the gate: CP=φP′CCP = \varphi P'C with φ=±1\varphi= \pm1. The table covers h, s, sdg, sx, x, y, z, cx, cy, cz, and swap, and its entries are Lean theorems over 2×22 \times2 or 4×44 \times4 complex matrices. After the sink the Clifford ops no longer wait for the decision of the correction, which is the source of the small gains at tbranch=0t_{\mathrm{branch}} = 0 in § 8.

Theorem 6.2 (Sink step in the density-matrix model). Let CC, PP, and P′P' be one-qubit matrices with CP=φP′CCP = \varphi P'C for some φ=±1\varphi= \pm1, placed on qubit qq. Then ⟦P;C⟧=⟦C;P′⟧\llbracket P; C\rrbracket= \llbracket C; P'\rrbracket. The same holds for a two-qubit CC on qubits a≠ba \ne b and a Pauli leaf on both of them, with C(A1⊗A2)=φ(B1⊗B2)CC(A_1 \otimes A_2) = \varphi(B_1 \otimes B_2)C.

(sink1_cq, sink2_cq, instances sink_h_cq and sink_cx_cq) [Lean-checked]

The sign drops out of the channel because (φK)ρ(φK)†=∣φ∣2KρK†(\varphi K)\rho(\varphi K)^\dagger= |\varphi|^2K\rho K^\dagger (chan_sign). Together with the rule sink_past_clifford, which moves a whole Pauli if past CC given the arm facts, this closes the sink step for quantum channels. A table entry holds for all nonzero multiples of CC (conj_smul), so the table can use 2H\sqrt{2}H and 2SX2SX and avoid square roots.

Size. Without the sink, the quantum error correction (QEC) benchmarks fit in S=4096S = 4096 for all t≤6t \le6. The sink splits a group into several, and its variants of Steane, of the repetition code of distance 7 to 11, and of the surface codes reach the limit at t≥3t \ge3. iqft_7 and iqpe_7 reach it at t≥4t \ge4. Groups past the limit stay generic [empirical].

Mechanization and Checking

We check soundness at three levels. Lean 4 [12] with Mathlib [13] proves that the rewrite rules preserve the denotation of § 3. The checker of § 7.2, also proved sound in Lean, validates the programs that the Rust code outputs against their inputs. State-vector and stabilizer simulation compares outputs with sources on all benchmarks up to 22 qubits but one, a non-Clifford program with 14 qubits.

What Lean proves

The development has 4846 lines, and 6585 with the checkers of § 7.2. A list of 73 theorems (Table 2 shows the main ones) is checked by a script: they depend only on propext, Classical.choice, and Quot.sound, and no theorem uses sorry. The rule theorems quantify over all interpretations II and all states ss. The _cq theorems instantiate them, or prove new facts, in the density-matrix model of § 3.3.

theoremstatement
den_restrict, den_commA1 and A2 lift from leaves to all ops.
fold_true, fold_falseA condition that is constant whenever the known bits are 0 selects its arm, on states whose support has those bits at 0.
hoist_sound, merge_soundThe semantic hoist and merge rules (§ 4).
unroll_soundA loop with fuel K+1K + 1 equals its body, then an if on the exit that runs the loop with fuel KK.
fastpath_stepTheorem 6.1, for any set of cases.
sink_past_cliffordA Pauli if followed by CC equals CC followed by the conjugated if, given the fact for both arms.
conj_h ... conj_swapTable entries: CP=φP′CCP = \varphi P'C with φ=±1\varphi= \pm1.
hoist_latency, merge_latencyTheorem 4.1 (C1).
m0Steps_latencyTheorem 4.2: C1 at any position and for sequences of steps.
lift_comm, chan_commLifts, and Kraus maps, on disjoint qubits commute.
Spec.sem_restrict, Spec.sem_commTheorem 3.4: A1 and A2 for gates, reset, and measurement.
meas_complete, reset_complete∑iKi∗Ki=1\sum_i K_i^{*}K_i = 1 for measurement and reset.
sink1_cq, sink2_cqTheorem 6.2: the sink step for channels.
defer_cqTheorem 5.1: direct defer with one control bit.
hoist_sound_cq, merge_sound_cq, fastpath_step_cqThe rule theorems in the density-matrix model.
checkBlock_sound, checkFP_sound, checkLat_soundTheorem 7.1: the translation-validation checkers.
m0StepsK_latency, checkLatLeaf_soundKTheorem 4.3 and its checker; hoist_block_can_delay: a hoisted if can add latency.

Table 2. The main Lean theorems. The checked list has 73 entries, including the negative theorems.

Negative theorems. For all side conditions, a Lean theorem refutes the rule without it, by a concrete counterexample. The counterexamples use an interpretation over D=ND = \mathbb{N} in which one leaf sets bit 0 and another doubles the weight. The refuted rules are hoist without the condition-bit rule, hoist or merge past an op that is not disjoint, a dispatch whose group writes a dispatch bit, and the two latency steps without the enclosing-bit rules.

Trusted base. A reader must trust four things beyond the Lean kernel, the checker’s JSON parser, the Lean compiler that runs the checkers on the jobs, and the Rust exporter src/tv.rs, which must copy the footprints of all leaves. The first is that the Lean IR copies the control structure of the Rust IR. The second is that the density-matrix model states the textbook semantics of gates, reset, and Z-basis measurement on a cq state. Its definitions are in CQ.lean, and the completeness theorems above check one property of them. The third is that the timing semantics copies the replay code (Latency.lean names the Rust functions that it copies), except that the replay skips the injected noise operations of the _noisy programs, which Lean treats as ordinary operations. The fourth is the gap between rules and code. For the normal-form and fast-path passes the checker of § 7.2 closes it for the programs we compiled. For the sink and defer passes the simulation checks cover it.

How the proofs were made. For the rule and latency theorems we wrote all statements by hand, typechecked it with sorry, and committed it before any proof. The Aristotle prover [14] filled those proofs in four rounds, and we graded the rounds locally. A script checks that these statements are unchanged from their committed drafts, so no statement was weakened to make a proof pass. The density-matrix files, the closure and block-model theorems, and the checkers were written later, statement and proof together, without Aristotle. CI repeats the build and the axiom check.

Translation validation

The rule theorems do not show that the Rust code applies only those rules. Translation validation closes this gap one program at a time: instead of verifying the compiler, a checker verifies its outputs [15, 16]. Check.lean defines a syntactic copy of the IR with bit expressions and injectively coded leaves, and two Boolean checkers. checkBlock decides whether a target block follows from a source block by fold steps on known-zero bits, hoists, merges, and congruence into arms. It decides all semantic side conditions on the syntax. A second checker, checkLat, accepts the same derivations with one more argument, a bound EE of the enclosing gate bits, and it also decides the latency side conditions of Theorem 4.1: a hoisted op writes no bit of EE, and the ops that a merged op moves past write no bit of EE. checkFP decides whether a target is a fast path of its input: equal programs, an equal head, or one dispatch whose default is the input and whose case bodies are, again, fast paths of the arms their values select. All three are proved sound:

Theorem 7.1 (Checker soundness). If checkBlock f W P Q = true, then [ ⁣[P] ⁣]=[ ⁣[Q] ⁣][\![P]\!] = [\![Q]\!] for all interpretations and all states ss whose support has the bits of WW at 0. If checkFP f P T = true, then [ ⁣[T] ⁣]=[ ⁣[P] ⁣][\![T]\!] = [\![P]\!] for all interpretations. If checkLat f W E P Q = true, then for all gate bits y⊆Ey \subseteq E and all start states σ′≤σ\sigma' \leq\sigma with the bits of WW at 0, if the replay of PP from σ\sigma does not stop, the replay state after QQ from σ′\sigma' is no later than the replay state after PP from σ\sigma (ideal model). If checkLatLeaf f W E P Q = true, the same holds in the block model. (checkBlock_sound, checkFP_sound, checkLat_sound, checkLatLeaf_soundK) [Lean-checked]

checkLat_sound uses Theorem 4.2 for hoists and merges, and monotonicity for a fold, whose live arm runs under fewer gate bits. checkLatLeaf is checkLat with the conditions of Theorem 4.3, and its proof uses that theorem.

The command qlin tv-export writes, for one benchmark, the job “source to normal form” and the jobs “normal form (or its sink) to fast path” for t=0t = 0 to 6, the budgets of § 8. A small Lean program parses the jobs and runs the checkers. A normal-form job passes only if checkBlock and checkLat both accept it. On all 66 benchmarks, 976 of 976 jobs pass [Lean-checked per output], so all 66 normal-form outputs are, in the ideal model, no later than its source. checkLatLeaf also accepts all 66, so they are no later in the block model either. The one benchmark whose outcome records cannot be computed (qft-adder-quantum_7) contributes its normal-form job only. A test plants a hoist of an op that one arm lacks, and a case body that drops the arm its value selects. The checker rejects both. The checker is sound but not complete: a correct output that it cannot match would fail, and no output failed.

Simulation checks

Up to 12 qubits, the equivalence check runs both programs on a state-vector simulator, from ∣0…0⟩\lvert0\ldots0\rangle and from seeded random product states. It compares the output distribution over the bits. It also compares ⟨v∣ρβ∣v⟩\langle v\lvert\rho_\beta\rvert v\rangle on all branches β\beta for four seeded random vectors vv, with extra ancilla qubits traced out. A check of the bits alone cannot see a Z/XZ/X swap on an unmeasured qubit, so the witnesses are needed. The check is sound but not complete, and a planted-error test shows that it rejects a missing correction. It passed on the normal forms of all benchmarks with at most 12 qubits, on 3046 defer search leaves, and on 282 fast-path and sink variants [empirical].

Past 12 qubits, the check runs on a stabilizer tableau (the Aaronson–Gottesman representation). A one-qubit non-Clifford gate is allowed on an unentangled qubit, which the tableau recognizes as a ZZ, XX, or YY eigenstate. The qubit then holds its 2-vector until its next measurement. This covers the error source of the noisy benchmarks, a rotation followed by a measurement. The check compares bit distributions and, per outcome, the mixture of canonical stabilizer states, from ∣0…0⟩\lvert0\ldots0\rangle and from seeded inputs with up to three qubits in XX or YY eigenstates. The tableau agrees with the dense simulator, in branches, probabilities, and states, on 28 benchmarks from ∣0…0⟩\lvert0\ldots0\rangle, on 114 product-state runs, and on 300 random Clifford programs. Four planted sign errors in the tableau all fail the random test [empirical].

Defer beyond Theorem 5.1. The copy form and multi-bit conditions are outside the Lean rule. Beyond the simulation check, a Wolfram Language script runs teleportation and long_range_cnot3 in classical and deferred form, with a symbolic input state on q0. Both forms give the same cq state, and a planted wrong defer does not [Wolfram-checked, two instances]. The Pauli table has three independent checks: Lean, Wolfram, and 96 cases against the simulator.

Evaluation

The evaluation answers four questions.

RQ1 Do the compiled programs, and those of the baselines, agree with the source on real benchmarks?

RQ2 When does the fast path lower the modeled expected latency?

RQ3 Is the defer choice stable over the sourced range of device parameters?

RQ4 Does the cost model agree with an emulator, with the logic of a real controller, and with a device?

Section 5 already compares the defer search with the exhaustive optimum. Modeled numbers come from the timing model of Section 4, emulated from the Selene emulator, RTL-simulated from the logic of the QubiC controller without qubits, and measured from ibm_kingston.

Benchmarks. We use 50 programs from three sources:

  • hand-written: teleportation, a repetition code round, a chain of adaptive measurements in measurement-based computation,

  • the jeff structured benchmarks: teleportation, repeat-until-success, the inverse quantum Fourier transform (iQFT), iterative quantum phase estimation (iQPE), and others,

  • the dynamaq suite [1]: repetition, five-qubit, and Steane codes with lookup decoders, constant-depth long-range CNOT and fan-out, GHZ-state preparation, and iterative phase estimation.

Some QEC programs have a _noisy variant with an injected error qubit. Before the first gate on a syndrome ancilla, a data qubit takes an XX error with probability 0.05, once, and the injection ops cost no time. The latency, search, and checks need simulation without sampling, so programs above 12 qubits (with copy qubits) are reported as skipped.

Cost presets. HERON_LIKE holds starting values. A one-qubit gate takes 32 ns, a two-qubit gate 68 ns, a measurement 800 ns, and a reset 1000 ns, with tfft_{\mathrm{ff}} = 600 ns. HERON_KINGSTON takes gates, measurement (1760 ns mid-circuit), and reset (2312 ns) from the ibm_kingston calibration snapshot, and tfft_{\mathrm{ff}} from Shirgure et al. [1]. All values have a tagged source line, and a unit test checks the file against the code. The three-qubit gate time and tbrancht_{\mathrm{branch}} have no source and are marked assumed.

RQ1: semantics on real programs. Table 3 runs BQCP [2] (at most 512 amplitudes and 4 branches), Qiskit at optimization levels 0 and 3, and TKET [17] on all benchmarks. A semantics guard compares the outputs with the sources by simulation. BQCP reduces the number of dynamic conditions on 17 benchmarks. Qiskit and TKET reduce it on no benchmark. Qiskit O3 raises the number of dynamic ops on 6 benchmarks, because basis translation adds gates inside the arms. TKET could not convert 13 programs (conditions on expressions, while loops, and non-basic gates inside conditions). One BQCP output failed the guard, on hand/mbqc_chain4. There BQCP removes an if on a bit that both arms of an earlier if measure. The output distribution differs by up to 0.0177, and Qiskit Aer confirms the difference. A three-qubit program reproduces it: the source gives P(c2=1)=0.497P(c_2 = 1) = 0.497 and the BQCP output gives 0.000 (Aer, 100000 shots). In the BQCP implementation, a measurement inside a branch body marks its qubit as unknown but keeps the old tracked value of its bit. A later if on that bit then folds as if the bit were still 0. BQCP proves its analysis sound on paper [2]. The mismatch is in the code, which is the gap that the simulation check covers for qlin too. All qlin outputs with at most 12 qubits passed the equivalence check of § 7.

RQ2: when the fast path pays. The block model charges tbrancht_{\mathrm{branch}} per controller decision, and a switch takes one decision (jump table), one per bit (decision tree), or one per compare (chain), as § 6 defines. We take tbrancht_{\mathrm{branch}} from controllers: QubiC 2.0 runs a control-flow instruction in at most 7 cycles at 500 MHz, 14 ns [10], and QICK evaluates a condition and jumps in 42 ns [11]. We add the 3.45 μ\mus that we measured on ibm_kingston (RQ4) and tbranch=0t_{\mathrm{branch}} = 0. The sweep covers 65 programs, up to 12 qubits with the dense simulator and 13 to 22 qubits with the stabilizer backend, which runs Steane, the repetition codes of distance 7, 9, and 11 with a minimum-weight lookup decoder (63, 255, and 1023 corrections), and the rotated surface code of distance 3 with minimum-weight lookup decoders for both syndrome types (30 corrections). All 252 fast-path and sink variants past 12 qubits pass the check. A variant gains when it beats the best baseline, the best of the source, the normal form, the best defer program, BQCP, and Qiskit O3. Table 4 counts the programs that gain 10% or more, and Table 5 lists the programs that gain at some point [modeled].

controllertbrancht_{\mathrm{branch}} (ns)tabletreechain
zero cost04 (16.0%)
QubiC148 (80.2%)7 (79.1%)8 (78.0%)
QICK4211 (92.0%)10 (91.2%)10 (89.4%)
IBM345013 (99.8%)13 (98.9%)13 (96.9%)

Table 4. Programs, of 65, whose best fast-path or sink variant beats the best baseline by 10% or more, with the largest gain in parentheses (modeled, block model, HERON_LIKE values, tff=600t_{\mathrm{ff}} = 600 ns). Columns: how a switch is dispatched. With tbranch=0t_{\mathrm{branch}} = 0 the dispatch costs nothing. The table column is a lower bound for a controller without a jump table, such as the QubiC design of RQ4.

benchmarkqubits0 nsQubiC, treeQICK, treeIBM, chain
dynamarq/five_qubit_code11−18.9%−17.8%−17.1%29.0%
dynamarq/five_qubit_code_noisy12−18.6%−18.0%−17.3%28.7%
dynamarq/repetition3_1_noisy63.1%1.6%−1.5%−169.8%
dynamarq/repetition5_0_noisy10−2.4%2.6%11.4%80.2%
dynamarq/repetition5_1_noisy109.5%9.1%12.1%79.7%
dynamarq/steane_noisy1514.3%13.9%12.5%58.7%
qec/repetition11_0_noisy22−1.9%78.7%91.2%96.9%
qec/repetition11_1_noisy2216.0%79.1%90.7%96.9%
qec/repetition7_0_noisy14−2.2%18.3%40.7%90.8%
qec/repetition7_1_noisy1412.2%26.0%41.6%90.6%
qec/repetition9_0_noisy18−2.0%49.0%73.4%94.9%
qec/repetition9_1_noisy1814.3%52.2%72.6%94.9%
qec/surface3_0_noisy197.1%5.4%13.8%70.9%
qec/surface3_1_noisy19−4.8%−8.0%0.6%70.5%

Table 5. Gain of the best fast-path or sink variant over the best baseline, for the programs that gain at some point (modeled, as in Table 4). A negative gain means a baseline is faster; on the five-qubit code and on repetition3_1_noisy it is the best defer program.

With tbranch=0t_{\mathrm{branch}} = 0 the gains come only from the Pauli sink, which moves corrections past the unencoding Cliffords: 14.3% on steane_noisy, and on the repetition codes prepared in ∣+⟩|+\rangle 9.5% at distance 5 and 12.2, 14.3, and 16.0% at distance 7, 9, and 11. From ∣0…0⟩|0 \ldots0\rangle with no injected error all syndromes are 0, so BQCP removes all corrections and wins on the noiseless codes, the surface codes included. At the QICK cost, 10 programs gain 10% or more under a decision tree, and the gain grows with the distance, from 40.7% at d=7d = 7 to 91.2% at d=11d = 11. The lookup decoder has one if per syndrome value, and a serial controller pays for all of them, while the switch needs one decision per syndrome bit. The noisy surface code prepared in ∣1⟩|1\rangle gains 13.8% at the QICK cost with a decision tree. Prepared in ∣+⟩|+\rangle it gains 0.6%, and there BQCP is the best baseline. The switch cost changes the count by at most one program at any branch cost.

Switch or speculation. The gain on these decoders can come from the switch, which replaces a chain of ifs, or from the budget tt, which limits the switch to likely outcomes. A full switch, the fast path with tt equal to the number mm of group bits, has a case for all outcomes and never takes the exit edge. Without the sink, the best fast path with t<mt < m beats the full switch by at most 0.3% under a jump table or a decision tree, on all 42 programs whose full switch fits the size limit and at all branch costs [modeled]. So the gain comes from the switch. The source here is a lookup decoder with one if per syndrome value, which is how dynamarq and our generators write it. A decoder written as a tree of ifs on the syndrome bits would take one decision per bit, as the tree-dispatched switch does. The budget saves code instead. On repetition11_0_noisy at the QICK cost with a decision tree, the full switch gains 91.2% with 1024 cases, t=2t = 2 gains 83.5% with 56 cases, and t=4t = 4 gains 90.5% with 386 cases. Under a compare chain a case costs a compare, so a smaller switch is also faster. At the IBM cost the best fast path beats the full switch by 11.4% on steane_noisy and by 5.9 to 6.0% on the two noisy surface codes. These are the only 3 programs where this margin exceeds 1% and the program gains 10% or more.

Noise. For error probabilities from 0.001 to 0.1 instead of 0.05, 4 and 10 programs still gain 10% or more [modeled]. On repetition11_0_noisy the best budget gains 90.9 to 91.2%, while t=2t = 2 falls from 91.2 to 67.7%.

The fast path does not always win. On the five-qubit code the best defer program beats all fast paths by 17.1 to 18.9% at 0 to 42 ns, and the fast path wins only at the IBM cost. At the IBM cost, on repetition3_1_noisy, the defer program removes the branches and is 2.7 times faster than the best fast path. The exit probability decides the best tt (Table 6). A budget over groups with random bits, such as the logical readout of the five-qubit code, makes t=0t = 0 exit 95% of the time.

benchmarkbranch costt=0t = 0123456
dynamarq/five_qubit_code0 ns1.011.011.011.011.011.01–
dynamarq/five_qubit_codeQICK, tree1.031.010.980.960.960.96–
dynamarq/repetition5_0_noisy0 ns1.001.001.001.001.00––
dynamarq/repetition5_0_noisyQICK, tree0.910.890.870.870.87––
dynamarq/repetition5_1_noisy0 ns1.001.001.001.001.00––
dynamarq/repetition5_1_noisyQICK, tree0.920.900.880.880.88––
dynamarq/repetition3_1_noisy0 ns1.001.001.001.00–––
dynamarq/repetition3_1_noisyQICK, tree0.990.990.99––––

Table 6. Fast-path expected latency over the source latency, for budgets t=0t = 0 to 6 (modeled, block model, HERON_LIKE values, tff=600t_{\mathrm{ff}} = 600 ns). Branch cost 0 ns: tbranch=0t_{\mathrm{branch}} = 0 with a jump table. QICK, tree: 42 ns per decision with a decision tree. A dash marks a budget above the one that already covers all outcomes.

RQ3: sensitivity. We scored the variants over a grid of sourced ranges: tmeast_{\mathrm{meas}} from 1760 to 4000 ns, tfft_{\mathrm{ff}} from 224 to 700 ns, and tbrancht_{\mathrm{branch}} from 0 to 1000 ns. “Defer beats the normal form” holds at all 12 (tmeas,tfft_{\mathrm{meas}}, t_{\mathrm{ff}}) points on 9 benchmarks and at no point on 17, so it does not flip inside the sourced ranges. The fast-path gain depends only on tbrancht_{\mathrm{branch}}. The five-qubit gain at tbranch=200t_{\mathrm{branch}} = 200 ns does not hold under HERON_KINGSTON at any grid point [modeled].

RQ4: Selene. The Selene SimpleRuntime executes one operation at a time and charges no feedforward cost, so it cannot test the schedule. It can test the per-outcome accounting. On 220 program variants of 44 benchmarks, 39988 of 44000 shots take the time that qlin’s per-outcome trace predicts, and 199 variants match in all shots. The other shots come from Selene’s compile-time gate cancellation. There qlin predicts 64 or 128 ns more, at most 0.17% of the shot [emulated]. Selene also gives the same output distribution as qlin’s simulator on all benchmarks with at most 12 qubits, within the stated sampling tolerance.

RQ4: QubiC. No available device runs the fast path, so we simulate the logic of an open controller cycle by cycle. We run the first dispatch group of four codes on the register-transfer logic of the open-source QubiC distributed processor [10] (commit c22ce8): one core, no qubits, in Verilator. This design jumps only to fixed addresses and has no bitwise AND, so a switch compiles to a compare chain or to a binary search on the syndrome value, and a jump table is not available. MCMit extends QubiC with a constant-latency multi-control branch [18], which we do not simulate. The syndrome arrives on the function-processor interface, and we count cycles from its arrival to the end of the group, for all syndrome values. Over 312 programs and values, the count is a linear function of the executed instructions to within 0.975 cycles: 6.0 cycles per conditional jump, taken or not, and 4.0 per unconditional jump [RTL-simulated]. QubiC has no not-equal comparison, so a compiled if takes a compare and a jump, 20 ns at 500 MHz, and the block model at the cited 14 ns per decision underestimates the source. Weighted by the syndrome probabilities, the group of the distance-5 repetition code takes 151.1 cycles as source and 21.3 as a compare chain at t=2t = 2. On the five-qubit code it takes 150.9 cycles against 79.7 for a tree. The worst case is slower: a syndrome outside the budget pays the compares and then the source ifs, 225 against 155 cycles. These are controller cycles, not shot times. The delivery of the syndrome, the same for all variants, is not included.

RQ4: IBM. We ran on ibm_kingston with the free Open Plan, which grants 600 s of device time per 28 days. The IBM toolchain rejects nested conditionals, measurements inside conditionals, and switch. So the fast path cannot run there, and a switch runs as a chain of if_else blocks.

Branch cost. A probe circuit measures one qubit, then runs kk if_else blocks on that bit, then measures a second qubit. We ran k∈{0,1,2,4,8}k \in\{0, 1, 2, 4, 8\} with three jobs of 1000 shots per kk (Table 7, Figure 3). The execution spans give the time per shot, which includes a fixed repetition delay. The least-squares slope is 3.45 μs\mu\mathrm{s} per block (95% CI 0.32 to 6.58 μs\mu\mathrm{s}) [measured]. The probe ifs read the same bit, so the slope measures tbrancht_{\mathrm{branch}} plus one x gate per block. It is our only measured value of tbrancht_{\mathrm{branch}}.

Figure 3. ibm_kingston (measured). Left: branch-cost probe, one point per job, with the least-squares fit and its 95% band. Right: source minus best defer program for the five-qubit code, one point per round of the first run. Two outliers are off the scale (arrows). The band is the mean and 95% CI of the 25 pairs kept by a post hoc rule. The 60-round run with a fixed analysis is not resolved (text). The dashed line is the modeled gap.

if_else blocksjobsmean per shot (μ\mus)sd (μ\mus)
031100.287.70
131106.9816.31
231098.074.30
431119.9811.85
831126.1830.89

Table 7. Branch-cost probe on ibm_kingston (measured, 1000 shots per job). The time per shot includes the repetition delay.

Ranking. At the measured branch cost, the model predicts that the best defer program of the five-qubit code is 19 μs\mu\mathrm{s} per shot faster than the source. A first run of 27 rounds, one job per program and round (Figure 3), gave -2.95 ±10.44\pm10.44 μs\mu\mathrm{s} (95% CI -24.50 to 18.60) after two outlier source jobs were dropped by a rule chosen after seeing the data. A second run of 60 interleaved rounds, with the analysis and the same outlier rule fixed before the first job, gave 21.06 μs\mu\mathrm{s} (95% CI −9.77-9.77 to 51.90 μs\mu\mathrm{s}). Against 19 μs\mu\mathrm{s} the tt-test gives p=0.89p = 0.89, and against 0 the Wilcoxon test gives p=0.73p = 0.73 [measured]. The interval contains both 0 and the predicted 19 μs\mu\mathrm{s}, so the run does not resolve the ranking. The spread between jobs dominates a 19 μs\mu\mathrm{s} effect on a 1.2 ms shot (Shapiro–Wilk p<0.0001p < 0.0001 on the differences). The teleportation variants differ by less than the 7.7 μs\mu\mathrm{s} spread of repeated jobs (2 to 7 μs\mu\mathrm{s} in the model), so we make no ranking claim for them.

Amplified ranking. A third run lets the gap grow while the job noise stays fixed. A program runs its body k∈{1,2,4,8}k \in\{1, 2, 4, 8\} times in one circuit, with all qubits reset between copies, so the modeled gap grows by 19.22 μs\mu\mathrm{s} per copy. With the analysis again fixed in advance, 15 rounds of one job per program and kk (120 jobs, submitted as one batch, 4 dropped by the outlier rule) give a mean gap slope of 6.97 μs\mu\mathrm{s} per copy (95% CI −8.69-8.69 to 22.63 μs\mu\mathrm{s}, Figure 4). Against 19.22 μs\mu\mathrm{s} the tt-test gives p=0.1156p = 0.1156, and against 0 the Wilcoxon test gives p=0.8040p = 0.8040 [measured]. This run does not resolve the ranking either. Wolfram reproduces the numbers of both analyses from the result files [Wolfram-checked].

Figure 4. Amplified ranking test on ibm_kingston (measured). Left: time per shot against the number of copies kk, one point per kept job, with a least-squares line per program. The 4 jobs that the outlier rule drops are not shown. Right: the gap slope per round (source minus best defer program), with its mean and 95% CI. The dashed line is the modeled 19.22 μ\mus per copy.

Time per copy (post hoc). The measured time per copy (41.89 and 36.69 μs\mu\mathrm{s}) matches the model at tbranch=1.62 μst_{\mathrm{branch}} = 1.62\ \mu\mathrm{s} for the source and 1.95 μs\mu\mathrm{s} for the defer program, inside the CI of the probe and below its point estimate. This reading came after the data. Table 8 lists the modeled values next to their emulated or measured value.

quantitywheremodelmeasuredgap and mechanism
time per shotSeleneper-outcome trace39988 of 44000 shotsat most 0.17% of a shot, from compile-time gate cancellation in Selene
tbrancht_{\mathrm{branch}}IBM14, 42 ns (FPGA controllers)3.45 μ\mus (0.32 to 6.58)controller time per if_else block, far above the FPGA controllers
decisionQubiC RTL14 ns (cited)12 ns compare, 20 ns if no not-equal: an if adds a jump
gap per shotIBM19 μ\mus21.06 μ\mus (−9.77-9.77 to 51.90)not resolved: job-to-job spread on a 1.2 ms shot
gap per copyIBM19.22 μ\mus6.97 μ\mus (−8.69-8.69 to 22.63)not resolved
time per copyIBM78.35, 59.13 μ\mus41.89, 36.69 μ\muspost hoc: matches a branch cost of 1.62 and 1.95 μ\mus

Table 8. Modeled against emulated or measured values. Intervals are 95% CIs. “time per copy”: source and best defer program of the five-qubit code. The model uses the probe’s branch cost on IBM.

Related Work

Verified quantum compilation. VOQC is an optimizer for quantum circuits written in Coq and extracted to OCaml. Its gate optimizations are proved correct against the matrix semantics of unitary SQIR programs, and two optimizations of programs with measurement are proved against the density-matrix semantics of full SQIR [19]. SQIR has no classical bit store, so a program branches on an outcome only at its measurement, and VOQC rewrites gates. qlin keeps the measured bits in its state and rewrites the control structure. CertiQ and Giallar verify Qiskit compiler passes with little manual proof, by an SMT encoding and by symbolic rewrite rules, and both found

bugs in the Qiskit implementation [20, 21]. CoqQ gives a program logic proved sound against a denotational semantics of a deeply embedded quantum language [22], and QEDIA mechanizes a quantum Hoare logic with classical variables in Lean 4 to verify programs [23]. Ying et al. verify algebraic laws of quantum programs in Coq and derive the principle of deferred measurement from them, in a language that discards intermediate outcomes [24]. The defer rule of qlin keeps the measured bits in the cq-state (Theorem 5.1). A survey covers the wider field [25]. QPPM verifies in Lean a compiler for Pauli-product-measurement programs with classical feedback. Its compilation and optimizations preserve the outputs and the recorded measurement results, and its scheduler picks the candidate with the smallest certified serial-depth bound, checked by a certificate per candidate [6]. It is the closest verified compiler to qlin. It proves no theorem that a rewrite never delays the schedule, and its depth model counts logical measurements and leaves out Pauli feedback. These works verify that a pass preserves the semantics. qlin also proves a performance property: hoist and merge steps never delay the program (Theorems 4.1 to 4.3), and the checker validates this bound for the normal-form outputs. Its semantics is a cq-state over mid-circuit measurement and classical control, and its density-matrix model makes the leaf axioms theorems. VOQC verifies its implementation, so it needs no check per output, and it trusts Coq extraction and its OCaml driver. qlin uses translation validation [15, 16] instead: the checker, proved sound in Lean, validates the semantics of the normal-form and fast-path outputs. Its trusted base moves to the Lean kernel, the Lean copy of the IR, the exporter in the Rust compiler, and the job parser. On the programs we compiled, a semantic bug in those Rust passes would appear as a rejected output, not as a wrong program. A validator of transpiler output, also proved sound in Lean, checks a structural policy instead of equivalence: no gate acts near the qubits of another tenant [26]. Table 9 compares what the approaches prove and what they check per output.

Classical control in dynamic circuits. BQCP tracks measured values and post-measurement states along bounded paths, and it proves its analysis and its simplifications sound on paper [2]. A related pass uses symbolic simulation and a probabilistic circuit model to remove classically controlled operations, and names a hardware-aware cost model for measurement and feedforward as future work [3]. Constant propagation across the classical–quantum boundary can turn quantum operations into classical ones [4], and branch expansion creates branch-specific simplifications [5]. Chen et al. compute measurement outcome probabilities at compile time by constant propagation, and replace

approachsemanticslatencyper output
VOQC [19]optimizer code, Coqnonot needed (verified code)
CertiQ, Giallar [20, 21]passes, SMT and rewrite rulesnono
QPPM [6]compiler, Leandepth bounddepth certificate
BQCP [2]analysis, on papernono
qlinrules, Lean (cq model)moves, Leannormal form (with timing), fast path: Lean sink, defer: simulation

caption: What the approaches prove and check. “semantics”: what is proved to preserve the semantics, and how. “latency”: a proved timing property of the rewrites (QPPM: a certified depth bound per candidate, not a theorem about rewrites). “per output”: a check of the compiled programs. “no”: the cited work states no such result.

:::

some mid-circuit measurements by randomized gates [27]. These passes decide which branches exist. qlin takes the remaining branches as given and decides how to execute them, against a cost model, with a latency theorem for its normal form and a mechanized semantics. BQCP has no cost model and does not change how the remaining branches are dispatched. It can run before qlin, and we run it as a baseline (§ 8).

Speculation and specialization. Trace scheduling [8] and superblocks [28] compile a likely path as straight-line code with side exits. Profile-guided code positioning separates hot from cold code [29]. Dynamic deoptimization lets optimized code fall back to unoptimized code by rebuilding its frames [9]. Flückiger et al. give a correctness argument for speculation guarded by assume instructions with deoptimization [30], and Barrière et al. verify speculation and deoptimization in a JIT compiler in Coq [31]. A verified superblock scheduler in CompCert proves that scheduling preserves the semantics, and it measures the speedup [32]. In quantum control, ARTERY predicts the branch of a feedback in hardware, from branch history and the readout pulse, and pre-executes instructions [33]. It targets the feedforward wait, which the fast path does not shorten. The fast path reduces the number of controller decisions instead, and a predictor could select a case of its switch early. MCMit adds a constant-latency multi-control branch instruction to QubiC and lowers the feedback latency by up to 70% [18]. Our cost model has no class for this instruction. The qlin fast path is a compile-time form of the split between a likely and an unlikely path, with two differences. The outcome distribution comes from a noise model, and a simulation of the source computes it on small programs. The exit edge sits before any specialized op, so the fallback needs no state reconstruction. In the terms of verified deoptimization, no speculated effect precedes the guard and the frame map is empty. This case matters here because the controller cannot read the quantum state.

Structure and mapping. Rovara et al. compile structured programs without unrolling them [34], and our importer reads such programs in the jeff format. Rice et al. make gates first-class values of an IR [35]. DynamiQ maps dynamic circuits onto coupling graphs [36], and CLASS places qubits to cut the latency between distributed controllers [37]: both change the layout, not the branches. The Helios runtime maps qubits and schedules transport while the program runs [38], and our cost model has no transport term. Qubit reuse adds classically controlled operations to save qubits [39, 40], the opposite of defer. AC/DC puts feedforward into a synthesis objective [41].

Benchmarks and equivalence. The dynamarq suite defines an expected depth over outcome probabilities and runs on IBM hardware and on the Helios-1E emulator [1]. We use its programs and its device numbers. Burgholzer and Wille give two schemes that let equivalence checkers treat dynamic circuits as if they had no non-unitary operations [42]. Hybrid path sums give a symbolic semantics with rewrite rules for programs with classical and quantum control [43]. Irene checks the equivalence of bounded hybrid programs with measurement and classical control, and it found 15 bugs in quantum compilers [44]. These three could check the sink outputs and the defer forms outside Theorem 5.1, which we check only by simulation (§ 7). AlchemQ ships an equivalence certificate with its optimized circuits, for unitary circuits [45]. Neither Irene nor AlchemQ is proved sound in a proof assistant.

Cost of control. Yuan and Carbin price quantum control flow in T gates [46]. The quantum control machine shows where classical-style jumps stop working in superposition [47]. Cobble pairs a language with a time and space cost analysis [48]. qlin prices classical control flow in latency. The defer rewrite converts classical control into quantum control, so one cost model can choose between them per device. Palsberg et al. ask for IRs with a precise semantics for mid-circuit measurement, and for space, time, and classical control costs reported apart [49]. HyQ targets the same latency from the language side: its staged type system guarantees that all circuits are generated before the program runs, so the controller generates no circuit between a measurement and the next circuit. Its typing and its progress proofs are mechanized in Beluga [7]. This removes the latency of circuit generation. It does not bound the time that the controller needs to decide a branch, and HyQ has no cost model for that time. qlin starts from a program whose circuits exist. It chooses from the outcome probabilities which outcomes get a specialized path, and it proves that hoist and merge steps never delay the schedule.

Common case and fallback in error correction. Decoders split a cheap common case from a full fallback: Clique [50], hierarchical decoding [51], and speculative window decoding [52, 53]. Pipelined fault-tolerant execution speculates on decoder results at run time [54]. GreenPeas compiles decoding hypergraphs just in time, because hypergraphs for all branches cost exponential memory [55]. The budget MtM_t sits between these two extremes: it precompiles the likely branches and leaves the rest generic. In a search of arXiv, OpenAlex, Crossref, and Semantic Scholar (November 2026), we found no earlier compile-time fast path over measurement outcomes with a sound fallback.

Limitations: Where the Budget Does Not Pay

Outcome distributions. The budget pays only when one outcome carries most of the probability. Teleportation has two uniform bits, so its fast path at t=2t = 2 is the full tree, and its gain comes from defer. In iQPE and iQFT the outcomes depend on the input phase, and for a phase that the register represents without error BQCP can remove the branches first. From ∣0…0⟩\lvert0 \ldots0 \rangle with no noise all QEC syndromes are 0, so constant propagation makes the QEC branches trivial. We read the QEC results as statements about the _noisy variants.

Feedforward only. In the ideal model a branch costs its feedforward wait and nothing else. The fast path cannot remove that wait: the switch still waits for its bits. It gains only when the controller spends time per branch, which is tbrancht_{\mathrm{branch}} in the block model. With tbranch=0t_{\mathrm{branch}} = 0 only the sink gains 10% or more, on 4 codes. A real controller can also spend time on communication between its cores for a branch on bits from several qubits, which no class of our sweep models.

Scale. ∣Mt∣\lvert M_t \rvert grows as (mt)\binom{m}{t}. On long syndrome loops tt must stay small, or the fast path must work per round. Latency, search, and checks without sampling run up to 12 qubits on any program, and past 12 qubits only on Clifford programs whose non-Clifford gates act on untangled qubits. One benchmark (14 qubits) is reported as skipped.

Where the normal form acts. It changes 3 of the 66 benchmarks (ipe3, and two that we wrote to exercise it). Its theorems guard the pass and do not produce the reported gains.

What is not mechanized. Lean proves the rules, and checkers validate the normal-form and fast-path outputs, but the Rust code itself is not verified, and the sink and defer outputs are checked by simulation only. The latency theorems hold in the ideal model and compare two programs on the same outcome record. In the block model, in which the reported gains arise, Lean covers moves of single operations only, and the fast path has no latency theorem in either model. Two steps are hand-derived: the relaxation bound of the defer search (checked exhaustively on all prefixes), and the claim that defer can empty the classical core. Theorem 5.1 covers only the direct form with one control bit and one gate in the arm.

Devices. The IBM stack cannot run the fast path at all. On Helios the runtime owns layout and transport [38], which our cost model does not represent. Selene has no feedforward cost. On the QubiC logic the fast path runs, but without qubits or measurement. On ibm_kingston three timing experiments left the ranking of the five-qubit variants unresolved. So no scheduling ranking of this paper has a device confirmation.

Conclusion

qlin compiles the time that a dynamic circuit spends on classical control. Its normal form moves operations out of branches without delaying the program, in the ideal timing model for all moves and with a serial controller for moves of single operations. qlin checks the normal-form outputs for semantics and timing, and the fast-path outputs for semantics. These properties, the rewrite rules, the fast-path step, the Pauli sink, and the direct defer rule are proved in Lean over a density-matrix model. The fast path compiles the likely outcomes into one multiway branch and falls back to the unchanged program for the rest, so no compensation code acts on the quantum state.

The gains depend on the controller’s time per branch decision. Without it, only the Pauli sink gains 10% or more, on 4 noisy codes. At the 42 ns per decision of QICK, 10 programs gain 10% or more, up to 91.2%, mostly because one switch replaces a chain of ifs. The budget then saves code more than time. On ibm_kingston a branch took 3.45 μs\mu\mathrm{s} (95% CI 0.32 to 6.58 μs\mu\mathrm{s}), and three timing experiments could not separate the variants. Open problems are a device run of the fast path, a less noisy timing measurement, a latency theorem for the fast path, and a mechanized copy form of defer.

Use of Generative AI

We used generative AI tools in this work, and we checked their output as follows. The Aristotle prover [14] produced the proofs of the rule and latency theorems from statements that we wrote and froze first (§ 7). An AI coding assistant (Claude, by Anthropic) helped write the Rust and Python code, the density-matrix Lean files, the latency closure theorem, the latency checkers, the block model, and their proofs, and the text of this paper. The Lean kernel checks all proofs, and a script checks the axioms of the listed theorems. Tests and the simulation checks cover the code. We checked all numbers in the text against the result files, and all references against a fetched arXiv or Crossref record. The author takes responsibility for all content.

Data-Availability Statement

The artifact holds the Rust implementation, the Lean development, the benchmark programs with their source records, the scripts that produce the tables, figures, and numbers of this paper, and the raw device results ([https://github.com/rylanmalar chick/qlin](https://github.com/rylanmalar chick/qlin)). The full certifier suite takes about 8 minutes on one desktop machine.

References

Claims ledger

claimstatementstatus
C1Hoist and merge steps, at any position and in any sequence, never delay the replay stateLean-checked, in expectation too, and checked per M0 output by checkLat (ideal model, no truncated loop). Block model: Lean-checked for leaf moves, checked per output by checkLatLeaf; a hoisted if can add latency (Lean-checked). Old hand argument wrong, rules fixed
C2With defer, the classical core can shrink to zerohand-derived, shown on teleportation
C3The normal-form rules preserve the semanticsLean-checked (rules, any model of A1, A2; A1, A2 Lean-checked for density matrices). M0 outputs: Lean-checked per output
C4Branch and bound finds the optimum on small inputsexhaustive, 180 of 180 rows
C5Expected-latency gain on benchmarksmodeled (HERON_LIKE; tbrancht_{\mathrm{branch}} from published controllers; three switch costs)
C6The cost model ranks variants correctly on a devicemeasured, not resolved (27 pairs post hoc; 60 pairs and an amplified design with k≤8k \le8 copies, analysis fixed first)
C7Defer preserves distribution and statedirect form, one bit: Lean-checked. Other forms: empirical, Wolfram-checked on two instances
C8Fast-path size stays within S=4096S = 4096 on QECempirical: without the sink for t≤6t \le6; sink variants of the larger codes reach SS at t≥3t \ge3
C9The relaxed bound is below all completionshand-derived, exhaustive on all prefixes
C10The fast path and the sink preserve the semanticsLean-checked (dispatch step, whole construction, and sink, density-matrix model); fast-path outputs Lean-checked per output (910 jobs); sink outputs: empirical
C11The Pauli conjugation tableLean-checked, Wolfram-checked, 96 simulator cases
C12Per-outcome accounting matches Seleneemulated, 39988 of 44000 shots match
C13“Defer beats the normal form” holds over the sourced rangesmodeled
C15Fast-path gain past 12 qubits at tbranch=0t_{\mathrm{branch}} = 0modeled, 12.2–16.0% on 4 noisy codes; stabilizer check on 252 variants
C16Dispatch cycles on the QubiC controller logicRTL-simulated (one core, no qubits); time linear in executed instructions within 1 cycle
C14IBM per-branch costmeasured, 3.45 μ\mus (95% CI 0.32–6.58)

Table 9.

References

  1. [1]Sumeet Shigure, Efekan Köksü, Anupam Mitra, Wibe Albert de Jong, Costin Iancu, and Siyuan Niu. Scalable Benchmarking Framework for Dynamic Quantum Circuits, 2026. URL https://arxiv.org/abs/2604.03360.
  2. [2]Innocenzo Fulginiti and Yanbin Chen. Branch-Aware Quantum Constant Propagation for Dynamic Quantum Circuits. In 2026 IEEE International Conference on Quantum Software (QSW), pages 141–151. IEEE, 2026. doi: 10.1109/qsw72780.2026.00024.DOI
  3. [3]Innocenzo Fulginiti, Yanbin Chen, Christian B. Mendl, and Helmut Seidl. Compile-Time Simplification of Classically Controlled Operations in Dynamic Circuits, 2026. URL https://arxiv.org/abs/2605.28439.
  4. [4]Lian Remme, Alexander Weinert, Andre Waschk, Lukas Burgholzer, and Robert Wille. Automatic De-Quantization of Quantum Programs Using Constant Propagation, 2026. URL https://arxiv.org/abs/2605.22980.
  5. [5]Yanbin Chen. Unleashing Optimizations in Dynamic Circuits through Branch Expansion, 2025. URL https://arxiv.org/abs/2504.09234.
  6. [6]John Zhuoyang Ye and Jens Palsberg. Verified Pauli-Product Measurement Compilation for Fault-Tolerant Quantum Computation, 2026. URL https://arxiv.org/abs/2610.31694.
  7. [7]Chuta Sano, Peng Fu, Ryan Kavanagh, Jennifer Paykin, and Brigitte Pientka. Staged Hybrid Quantum-Classical Programming, 2026. URL https://arxiv.org/abs/2609.06743.
  8. [8]Joseph A. Fisher. Trace Scheduling: A Technique for Global Microcode Compaction. IEEE Transactions on Computers, C-30(7):478–490, 1981. doi: 10.1109/tc.1981.1675827.DOI
  9. [9]Urs Hölzle, Craig Chambers, and David Ungar. Debugging optimized code with dynamic deoptimization. In Proceedings of the ACM SIGPLAN 1992 conference on Programming language design and implementation - PLDI ’92, pages 32–43. ACM Press, 1992. doi: 10.1145/143095.143114.DOI
  10. [10]Yilin Xu, Gang Huang, Neelay Fruitwala, et al. QubiC 2.0: An Extensible Open-Source Qubit Control System Capable of Mid-Circuit Measurement and Feed-Forward, 2023. URL https://arxiv.org/abs/2309.10333.
  11. [11]Leandro Stefanazzi, Ken Treptow, Neal Wilcer, et al. The QICK (Quantum Instrumentation Control Kit): Readout and control for qubits and detectors, 2021. URL https://arxiv.org/abs/2110.00557.
  12. [12]Leonardo de Moura and Sebastian Ullrich. The Lean 4 Theorem Prover and Programming Language. In Automated Deduction – CADE 28, pages 625–635. Springer International Publishing, 2021. doi: 10.1007/978-3-030-79876-5_37.DOI
  13. [13]The mathlib Community. The lean mathematical library. In Proceedings of the 9th ACM SIGPLAN International Conference on Certified Programs and Proofs, pages 367–381. ACM, 2020. doi: 10.1145/3372885.3373824.
  14. [14]Tudor Achim, Alex Best, Alberto Bietti, et al. Aristotle: IMO-level Automated Theorem Proving, 2025. URL https://arxiv.org/abs/2510.03146.
  15. [15]A. Pnueli, M. Siegel, and E. Singerman. Translation validation. In Tools and Algorithms for the Construction and Analysis of Systems, pages 151–166. Springer Berlin Heidelberg, 1998. doi: 10.1007/BFb0054170.
  16. [16]George C. Necula. Translation validation for an optimizing compiler. In Proceedings of the ACM SIGPLAN 2000 conference on Programming language design and implementation, pages 83–94. ACM, 2000. doi: 10.1145/349299.349314.
  17. [17]Seyon Sivarajah, Silas Dilkes, Alexander Cowtan, Will Simmons, Alec Edgington, and Ross Duncan. t|ket| : A Retargetable Compiler for NISQ Devices, 2020. URL https://arxiv.org/abs/2003.10611.
  18. [18]Emmanouil Giortamis, Felix Gust, Aleksandra Świerkowska, Sandra Stankovic, Innocenzo Fulginiti, Yanbin Chen, Xiaorang Guo, Benjamin Lienhard, Martin Schulz, and Pramod Bhattotia. MCMit: Hardware-Software Co-Design for Mid-Circuit Measurement Error Mitigation, 2026. URL https://arxiv.org/abs/2604.25863.
  19. [19]Kesha Hietala, Robert Rand, Shih-Han Hung, Xiaodi Wu, and Michael Hicks. A verified optimizer for Quantum circuits. Proceedings of the ACM on Programming Languages, 5(POPL):1–29, 2021. doi: 10.1145/3434318.DOI
  20. [20]Yunong Shi, Runzhou Tao, Xupeng Li, Ali Javadi-Abhari, Andrew W. Cross, Frederic T. Chong, and Ronghui Gu. CertiQ: A Mostly-automated Verification of a Realistic Quantum Compiler, 2019. URL https://arxiv.org/abs/1908.08963.
  21. [21]Runzhou Tao, Yunong Shi, Jianan Yao, Xupeng Li, Ali Javadi-Abhari, Andrew W. Cross, Frederic T. Chong, and Ronghui Gu. Gualliar: Push-Button Verification for the Qiskit Quantum Compiler, 2022. URL https://arxiv.org/abs/2205.00661.
  22. [22]Li Zhou, Gilles Barthe, Pierre-Yves Strub, Junyi Liu, and Mingsheng Ying. CoqQ: Foundational Verification of Quantum Programs, 2022. URL https://arxiv.org/abs/2207.11350.
  23. [23]Yuan-Jie Ren, Zhicheng Zhang, Junyi Liu, Jinzheng Li, Yidi Qi, and Mingsheng Ying. QEDIA: Quantum Program Verification in Lean, 2026. URL https://arxiv.org/abs/2610.17708.
  24. [24]Mingsheng Ying, Li Zhou, and Gilles Barthe. Laws of Quantum Programming. ACM Transactions on Software Engineering and Methodology, 35(7):1–37, 2026. doi: 10.1145/3765903.DOI
  25. [25]Marco Lewis, Sadegh Soudjani, and Paolo Zuliani. Formal Verification of Quantum Programs: Theory, Tools and Challenges, 2021. URL https://arxiv.org/abs/2110.01320.
  26. [26]Ali Hamza Malik and Muhammad Taqi Raza. Certified Confinement: Kernel-Checked Validation of Untrusted Quantum-Cloud Transpiler Output. In Proceedings of the 2026 ACM Conference on Post-Quantum and Quantum-based Security, pages 106–121. ACM, 2026. doi: 10.1145/3839338.3857240.DOI
  27. [27]Yanbin Chen, Innocenzo Fulginiti, and Christian B. Mendl. Reducing Mid-Circuit Measurements via Probabilistic Circuits, 2024. URL https://arxiv.org/abs/2405.13747.
  28. [28]Wen Mei W. Hwu, Scott A. Mahlke, William Y. Chen, et al. The superblock: An effective technique for VLIW and superscalar compilation. The Journal of Supercomputing, 7(1-2):229–248, 1993. doi: 10.1007/BF01205185.DOI
  29. [29]Karl Pettis and Robert C. Hansen. Profile guided code positioning. In Proceedings of the ACM SIGPLAN 1990 conference on Programming language design and implementation - PLDI ’90, pages 16–27. ACM Press, 1990. doi: 10.1145/93542.93550.DOI
  30. [30]Olivier Flückiger, Gabriel Scherer, Ming-Ho Yee, Aviral Goel, Amal Ahmed, and Jan Vitek. Correctness of speculative optimizations with dynamic deoptimization. Proceedings of the ACM on Programming Languages, 2(POPL):1–28, 2018. doi: 10.1145/3158137.DOI
  31. [31]Aurèle Barrière, Sandrine Blazy, Olivier Flückiger, David Pichardie, and Jan Vitek. Formally verified speculation and deoptimization in a JIT compiler. Proceedings of the ACM on Programming Languages, 5(POPL):1–26, 2021. doi: 10.1145/3434327.DOI
  32. [32]Cyril Six, Léo Gourdin, Sylvain Boulmé, David Monniaux, Justus Fasse, and Nicolas Nardino. Formally verified superblock scheduling. In Proceedings of the 11th ACM SIGPLAN International Conference on Certified Programs and Proofs, pages 40–54. ACM, 2022. doi: 10.1145/3497775.3503679.DOI
  33. [33]Wuwei Tian, Liqiang Lu, Siwei Tan, Yun Liang, Tingting Li, Kaiwen Zhou, Xinghui Jia, and Jianwei Yin. ARTERY: Fast Quantum Feedback using Branch Prediction. In Proceedings of the 52nd Annual International Symposium on Computer Architecture, pages 285–298. ACM, 2025. doi: 10.1145/3695053.3731086.
  34. [34]Damian Rovara, Daniel Haag, Marck Koch, et al. Why Are We Unrolling? The Importance of Structured Quantum Programs for Compilation, 2026. URL https://arxiv.org/abs/2609.16171.
  35. [35]Alex Rice, Chris Heunen, and Tobias Grosser. A Dynamic Intermediate Representation for Hybrid Quantum-Classical Programs, 2026. URL https://arxiv.org/abs/2609.01037.
  36. [36]Marouane Benbetka, Merwan Bekkar, Bokyeong Yoon, Riyadh Baghdadi, and Martin Kong. Mapping Dynamic, Hierarchical Quantum Circuits, 2026. URL https://arxiv.org/abs/2609.08075.
  37. [37]Yu Chen, Yilun Zhao, Bing Li, He Li, Mengdi Wang, Yinhe Han, and Ying Wang. CLASS: A Controller-Centric Layout Synthesizer for Dynamic Quantum Circuits, 2025. URL https://arxiv.org/abs/2509.15742.
  38. [38]Anthony Ransford, M. S. Allman, Jake Arkinstall, et al. Helios: A 98-qubit trapped ion quantum computer, 2025. URL https://arxiv.org/abs/2511.05465.
  39. [39]Damian Rovara, Lukas Burgholzer, and Robert Wille. Qubit Reuse Beyond Reorder and Reset: Optimizing Quantum Circuits by Fully Utilizing the Potential of Dynamic Circuits, 2025. URL https://arxiv.org/abs/2511.22712.
  40. [40]Kun Fang, Munan Zhang, Ruqi Shi, and Yinan Li. Dynamic quantum circuit compilation, 2023. URL https://arxiv.org/abs/2310.11021.
  41. [41]Siyuan Niu, Efekan Kokcu, Anupam Mitra, Aaron Szasz, Akel Hashim, Justin Kalloor, Wibe Albert de Jong, Costin Iancu, and Ed Younis. AC/DC: Automated Compilation for Dynamic Circuits, 2024. URL https://arxiv.org/abs/2412.07969.
  42. [42]Lukas Burgholzer and Robert Wille. Handling Non-Unitaries in Quantum Circuit Equivalence Checking, 2021. URL https://arxiv.org/abs/2106.01099.
  43. [43]Christophe Chareton, Jad Issa, Mathieu Nguyen, Nicolas Blanco, and Sébastien Bardin. Hybrid Path-Sums for Hybrid Quantum Programs, 2026. URL https://arxiv.org/abs/2604.24578.
  44. [44]Jingyu Ke, Jingyang Li, and Guoqiang Li. Irene: Equivalence Checking of Hybrid Quantum Programs via Structure-Preserving Symbolic Reduction, 2026. URL https://arxiv.org/abs/2609.36065.
  45. [45]Adam Laabs. AlchemQ: Proof-Carrying Quantum Circuit Optimization with Per-Result Equivalence Certificates, 2026. URL https://arxiv.org/abs/2609.19160.
  46. [46]Charles Yuan and Michael Carbin. The T-Complexity Costs of Error Correction for Control Flow in Quantum Computation, 2023. URL https://arxiv.org/abs/2311.12772.
  47. [47]Charles Yuan, Agnes Villanyi, and Michael Carbin. Quantum Control Machine: The Limits of Control Flow in Quantum Programming, 2023. URL https://arxiv.org/abs/2304.15000.
  48. [48]Charles Yuan. Cobble: Compiling Block Encodings for Quantum Computational Linear Algebra, 2025. URL https://arxiv.org/abs/2511.01736.
  49. [49]Jens Palsberg, Jason Cong, Yufei Ding, Bill Fefferman, Moinuddin Qureshi, Gokul Subramanian Ravi, Kaitlin N. Smith, Hanrui Wang, Xiaodi Wu, and Henry Yuen. Computer Science Challenges in Quantum Computing: Early Fault-Tolerance and Beyond, 2026. URL https://arxiv.org/abs/2601.20247.
  50. [50]Gokul Subramanian Ravi, Jonathan M. Baker, Arash Fayazi, Sophia Fuhui Lin, Ali Javadi-Abhari, Massoud Pedram, and Frederic T. Chong. Better Than Worst-Case Decoding for Quantum Error Correction, 2022. URL https://arxiv.org/abs/2208.08547.
  51. [51]Nicolas Delfosse. Hierarchical decoding to reduce hardware requirements for quantum computing, 2020. URL https://arxiv.org/abs/2001.11427.
  52. [52]Joshua Viziali, Jason D. Chadwick, Sarang Joshi, Gokul Subramanian Ravi, Yanjing Li, and Frederic T. Chong. SWIPER: Minimizing Fault-Tolerant Quantum Program Latency via Speculative Window Decoding. In Proceedings of the 52nd Annual International Symposium on Computer Architecture, pages 1386–1401. ACM, 2025. doi: 10.1145/3695053.3731022.DOI
  53. [53]Rylan Malarchik. The verifier side of speculative window decoding: a predictability bracket, a machine-checked blast-radius bound, and a decoder-agnostic recover loop, 2026. URL https://arxiv.org/abs/2607.13062.
  54. [54]Aditi Awasthi, Gokul Subramanian Ravi, and Jonathan Mark Baker. Stalls and Speculation: Pipelined Execution for Fault Tolerant Quantum Computation, 2026. URL https://arxiv.org/abs/2606.15993.
  55. [55]Abbas B. Ziad, Juba Xo, and Hongxiang Fan. GreenPeas: Unlocking adaptive quantum error correction with just-in-time decoding hypergraphs, 2026. URL https://arxiv.org/abs/2604.16613.

Paper details

vlnc:W_2cjwp3vp
Version
v1 · latest
Published
Fresh — added to the Hub within the last 30 days
Added
License
CC BY 4.0
Usage

views · 7

downloads · 0

A view counts once per browser per day, a download each time the PDF is requested.

  • Physics and Astronomy

Aristotle prover, Claude

View statement
Looking for related papers…
Contents