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 . On IBM Heron devices 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 and a budget , and it compiles a multiway branch (a switch) with one case per outcome within bits of . 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 s 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.
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).
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).
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).
The fast-path construction, proved sound for any set of cases and therefore for all budgets and size limits (§ 6).
A branch-and-bound search over defer choices, which finds the exhaustive optimum on 180 of 180 rows (§ 5).
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 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

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 and budget , 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 , and a serial controller spends 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 , 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 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 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 . The group writes no bit of . 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 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 and classical bits . A block is a list of operations (ops):
Here is a gate with constant angles, is a Boolean expression over bits, , , , and are blocks, and bounds the iterations of a loop that exits when holds after an iteration. A switch runs the first case whose values equal the bits , 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 of an op is its set of qubits , the bits that it reads, and the bits 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, , when .
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 be an additive commutative monoid. A state is a function , where an assignment gives a value to all bits. For a condition , the restriction keeps the branches where holds: if , else .
For a physical program, is the cone of unnormalized density operators on qubits, and is the quantum part on the branch where the bits equal . A block denotes the composition of its ops from left to right, and
A branch still in the loop after iterations stops there. This is the truncated trace that the implementation enumerates.
Definition 3.3 (Interpretation). An interpretation gives a leaf an additive map on states and satisfies two axioms:
A1 (locality) A leaf commutes with when 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 qubits with computational basis , and let be the complex matrices. For a set of qubits , a matrix is local to when depends only on the values of and on . Its lift acts as on and as the identity elsewhere:
A Kraus map on with operators is . The leaves are:
a gate with matrix local to its qubits : the Kraus map with one operator , applied on all branches;
reset q: the Kraus map on with operators and , on all branches;
measure q -> b: with the projector on ,
The measurement collects both old values of and keeps the part of the state where qubit agrees with the new value of .
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 of has one nonzero summand, at the basis state that agrees with on and with elsewhere. Both products equal when and agree outside , and otherwise. Two measurements of different qubits into different bits commute because the two updates of commute and the projectors commute. As a check that the model is faithful, the Kraus operators of measurement and of reset satisfy (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 , which gives a duration to a leaf and the feedforward latency . An outcome record gives the outcome of the -th measurement of a bit. The replay runs the trace that selects and keeps a state with five parts: the time at which qubit is free, the end time of the latest measurement of bit , the current bit values, a cursor per bit into , and a stop flag. An op runs with the set of gate bits: the condition bits of all enclosing if, switch, and loop exit. A leaf with footprint and duration finishes at
which becomes the ready time of all and the measurement end of all . A measurement reads its outcome from and advances the cursor of its bit. An if runs its taken arm with . A loop that does not exit within 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 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 that both arms contain in front of the if;
merge an op that both arms contain to after the if;
unroll the first iteration of a loop.
Hoist and merge carry side conditions. Write and for the ops that moves past in the two arms, for the condition, and for the gate bits of the if:
The conditions on matter only for latency. The semantic rules need only the disjointness conditions and, for hoist, (§ 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.
| pipeline | ran | fewer ff | smaller core | more dyn |
| bqcp | 46 | 17 | 17 | 0 |
| qiskit_o0 | 47 | 0 | 0 | 6 |
| qiskit_o3 | 47 | 0 | 0 | 6 |
| tket | 34 | 0 | 0 | 0 |
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 , gate bits , and start state that is not stopped: if one hoist or merge step under the side conditions above turns op into block , and the replay of does not stop, then the replay state after is no later than the replay state after . 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 hold when follows from 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 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 in the place of . If , then for all gate bits and all start states , if the replay of from does not stop, the replay state after from is no later than the replay state after from . (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 . 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.

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 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 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 , which the evaluation sweeps under a limit on the number of case blocks. For a program with one dispatch group the expected cost splits as
where is the fast path, the fallback, and 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 be any matrix local to a qubit set with , and let be on controlled by qubit on value (the identity on when qubit holds ). Then
(defer_cq) [Lean-checked]
The proof is an identity of matrices. With , the projector on , the product equals when and otherwise (proj_ctrl). Moving the measurement further, past ops that touch neither nor , 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 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 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 . 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.
| benchmark | cand. | source | M0 | best | floor | deferred | +2q | +q |
| dynamarq/cnot_ladder4 | 3 | 2317 | 2317 | 1236 | 1080 | 3 | 6 | 0 |
| dynamarq/fanout4 | 3 | 2399 | 2399 | 1376 | 1220 | 3 | 8 | 0 |
| dynamarq/five_qubit_code | 5 | 4278 | 4278 | 3565 | 3213 | 5 | 5 | 0 |
| dynamarq/five_qubit_code_noisy | 5 | 4189 | 4189 | 3565 | 3211 | 5 | 5 | 0 |
| dynamarq/ghz5 | 4 | 2310 | 2310 | 1240 | 998 | 4 | 10 | 0 |
| dynamarq/ipe3 | 3 | 5860 | 5860 | 5860 | 5860 | 0 | 0 | 0 |
| dynamarq/long_range_cnot3 | 2 | 2074 | 2074 | 1136 | 1016 | 2 | 3 | 0 |
| dynamarq/repetition3_0 | 3 | 1172 | 1172 | 1172 | 1172 | 0 | 0 | 0 |
| dynamarq/repetition3_0_noisy | 3 | 1376 | 1376 | 1376 | 1174 | 0 | 0 | 0 |
| dynamarq/repetition3_1 | 3 | 1340 | 1340 | 1340 | 1340 | 0 | 0 | 0 |
| dynamarq/repetition3_1_noisy | 3 | 1541 | 1541 | 1541 | 1342 | 0 | 0 | 0 |
| hand/mbqc_chain4 | 4 | 4632 | 4632 | 1604 | 1108 | 4 | 7 | 0 |
| hand/repetition3 | 3 | 1172 | 1172 | 1172 | 1172 | 0 | 0 | 0 |
| hand/teleportation | 2 | 1466 | 1466 | 1104 | 1000 | 2 | 2 | 0 |
| jeff/iqft_3 | 3 | 5544 | 5544 | 5544 | 5544 | 0 | 0 | 0 |
| jeff/iqft_5 | 10 | 9320 | 9320 | 9320 | 9320 | 0 | 0 | 0 |
| jeff/iqft_7 | 21 | 13160 | 13160 | 13160 | 13160 | 0 | 0 | 0 |
| jeff/iqpe_3 | 3 | 5844 | 5844 | 5844 | 5844 | 0 | 0 | 0 |
| jeff/iqpe_5 | 10 | 9820 | 9820 | 9820 | 9820 | 0 | 0 | 0 |
| jeff/iqpe_7 | 21 | 13684 | 13684 | 13684 | 13684 | 0 | 0 | 0 |
| jeff/teleportation | 2 | 2090 | 2090 | 1136 | 1000 | 2 | 2 | 0 |
Table 1. Defer search at 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 : 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 . The budget is the set of outcomes of weight at most , and for bits [Wolfram-checked for ].
A dispatch group is a maximal run of consecutive top-level dynamic ifs whose condition bits are all written before the run and not written inside it. For a group , the rest of the program, and a remaining budget , the fast path is
where is the weight of and replaces the ifs of by the arm that selects. 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 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 syndrome bits has up to ifs, and a decision tree needs 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 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 be a block whose if conditions read only bits in and which writes no bit of . Let be any list of cases such that for all cases the body satisfies . Then
(fastpath_step) [Lean-checked]
Case runs only on branches where the bits of equal . On those branches all ifs of the group take the arm that selects, because the group writes no bit of (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 is again a fast path. A relation FastPathOf describes the programs that the construction can build, and induction over it gives 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 , , and 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: with . The table covers h, s, sdg, sx, x, y, z, cx, cy, cz, and swap, and its entries are Lean theorems over or 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 in § 8.
Theorem 6.2 (Sink step in the density-matrix model). Let , , and be one-qubit matrices with for some , placed on qubit . Then . The same holds for a two-qubit on qubits and a Pauli leaf on both of them, with .
(sink1_cq, sink2_cq, instances sink_h_cq and sink_cx_cq) [Lean-checked]
The sign drops out of the channel because (chan_sign). Together with the rule sink_past_clifford, which moves a whole Pauli if past given the arm facts, this closes the sink step for quantum channels. A table entry holds for all nonzero multiples of (conj_smul), so the table can use and and avoid square roots.
Size. Without the sink, the quantum error correction (QEC) benchmarks fit in for all . 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 . iqft_7 and iqpe_7 reach it at . 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 and all states . The _cq theorems instantiate them, or prove new facts, in the density-matrix model of § 3.3.
| theorem | statement |
den_restrict, den_comm | A1 and A2 lift from leaves to all ops. |
fold_true, fold_false | A 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_sound | The semantic hoist and merge rules (§ 4). |
unroll_sound | A loop with fuel equals its body, then an if on the exit that runs the loop with fuel . |
fastpath_step | Theorem 6.1, for any set of cases. |
sink_past_clifford | A Pauli if followed by equals followed by the conjugated if, given the fact for both arms. |
conj_h ... conj_swap | Table entries: with . |
hoist_latency, merge_latency | Theorem 4.1 (C1). |
m0Steps_latency | Theorem 4.2: C1 at any position and for sequences of steps. |
lift_comm, chan_comm | Lifts, and Kraus maps, on disjoint qubits commute. |
Spec.sem_restrict, Spec.sem_comm | Theorem 3.4: A1 and A2 for gates, reset, and measurement. |
meas_complete, reset_complete | for measurement and reset. |
sink1_cq, sink2_cq | Theorem 6.2: the sink step for channels. |
defer_cq | Theorem 5.1: direct defer with one control bit. |
hoist_sound_cq, merge_sound_cq, fastpath_step_cq | The rule theorems in the density-matrix model. |
checkBlock_sound, checkFP_sound, checkLat_sound | Theorem 7.1: the translation-validation checkers. |
m0StepsK_latency, checkLatLeaf_soundK | Theorem 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 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 of the enclosing gate bits, and it also decides the latency side conditions of Theorem 4.1: a hoisted op writes no bit of , and the ops that a merged op moves past write no bit of . 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 for all interpretations and all states whose support has the bits of at 0. If checkFP f P T = true, then for all interpretations. If checkLat f W E P Q = true, then for all gate bits and all start states with the bits of at 0, if the replay of from does not stop, the replay state after from is no later than the replay state after from (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 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 and from seeded random product states. It compares the output distribution over the bits. It also compares on all branches for four seeded random vectors , with extra ancilla qubits traced out. A check of the bits alone cannot see a 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 , , or 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 and from seeded inputs with up to three qubits in or eigenstates. The tableau agrees with the dense simulator, in branches, probabilities, and states, on 28 benchmarks from , 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 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 = 600 ns. HERON_KINGSTON takes gates, measurement (1760 ns mid-circuit), and reset (2312 ns) from the ibm_kingston calibration snapshot, and 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 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 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 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 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 s that we measured on ibm_kingston (RQ4) and . 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].
| controller | (ns) | table | tree | chain |
| zero cost | 0 | 4 (16.0%) | ||
| QubiC | 14 | 8 (80.2%) | 7 (79.1%) | 8 (78.0%) |
| QICK | 42 | 11 (92.0%) | 10 (91.2%) | 10 (89.4%) |
| IBM | 3450 | 13 (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, ns). Columns: how a switch is dispatched. With 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.
| benchmark | qubits | 0 ns | QubiC, tree | QICK, tree | IBM, chain |
| dynamarq/five_qubit_code | 11 | −18.9% | −17.8% | −17.1% | 29.0% |
| dynamarq/five_qubit_code_noisy | 12 | −18.6% | −18.0% | −17.3% | 28.7% |
| dynamarq/repetition3_1_noisy | 6 | 3.1% | 1.6% | −1.5% | −169.8% |
| dynamarq/repetition5_0_noisy | 10 | −2.4% | 2.6% | 11.4% | 80.2% |
| dynamarq/repetition5_1_noisy | 10 | 9.5% | 9.1% | 12.1% | 79.7% |
| dynamarq/steane_noisy | 15 | 14.3% | 13.9% | 12.5% | 58.7% |
| qec/repetition11_0_noisy | 22 | −1.9% | 78.7% | 91.2% | 96.9% |
| qec/repetition11_1_noisy | 22 | 16.0% | 79.1% | 90.7% | 96.9% |
| qec/repetition7_0_noisy | 14 | −2.2% | 18.3% | 40.7% | 90.8% |
| qec/repetition7_1_noisy | 14 | 12.2% | 26.0% | 41.6% | 90.6% |
| qec/repetition9_0_noisy | 18 | −2.0% | 49.0% | 73.4% | 94.9% |
| qec/repetition9_1_noisy | 18 | 14.3% | 52.2% | 72.6% | 94.9% |
| qec/surface3_0_noisy | 19 | 7.1% | 5.4% | 13.8% | 70.9% |
| qec/surface3_1_noisy | 19 | −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 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 9.5% at distance 5 and 12.2, 14.3, and 16.0% at distance 7, 9, and 11. From 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 to 91.2% at . 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 gains 13.8% at the QICK cost with a decision tree. Prepared in 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 , which limits the switch to likely outcomes. A full switch, the fast path with equal to the number of group bits, has a case for all outcomes and never takes the exit edge. Without the sink, the best fast path with 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, gains 83.5% with 56 cases, and 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 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 (Table 6). A budget over groups with random bits, such as the logical readout of the five-qubit code, makes exit 95% of the time.
| benchmark | branch cost | 1 | 2 | 3 | 4 | 5 | 6 | |
| dynamarq/five_qubit_code | 0 ns | 1.01 | 1.01 | 1.01 | 1.01 | 1.01 | 1.01 | – |
| dynamarq/five_qubit_code | QICK, tree | 1.03 | 1.01 | 0.98 | 0.96 | 0.96 | 0.96 | – |
| dynamarq/repetition5_0_noisy | 0 ns | 1.00 | 1.00 | 1.00 | 1.00 | 1.00 | – | – |
| dynamarq/repetition5_0_noisy | QICK, tree | 0.91 | 0.89 | 0.87 | 0.87 | 0.87 | – | – |
| dynamarq/repetition5_1_noisy | 0 ns | 1.00 | 1.00 | 1.00 | 1.00 | 1.00 | – | – |
| dynamarq/repetition5_1_noisy | QICK, tree | 0.92 | 0.90 | 0.88 | 0.88 | 0.88 | – | – |
| dynamarq/repetition3_1_noisy | 0 ns | 1.00 | 1.00 | 1.00 | 1.00 | – | – | – |
| dynamarq/repetition3_1_noisy | QICK, tree | 0.99 | 0.99 | 0.99 | – | – | – | – |
Table 6. Fast-path expected latency over the source latency, for budgets to 6 (modeled, block model, HERON_LIKE values, ns). Branch cost 0 ns: 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: from 1760 to 4000 ns, from 224 to 700 ns, and from 0 to 1000 ns. “Defer beats the normal form” holds at all 12 () 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 . The five-qubit gain at 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 . 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 if_else blocks on that bit, then measures a second qubit. We ran with three jobs of 1000 shots per (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 per block (95% CI 0.32 to 6.58 ) [measured]. The probe ifs read the same bit, so the slope measures plus one x gate per block. It is our only measured value of .
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 blocks | jobs | mean per shot (s) | sd (s) |
| 0 | 3 | 1100.28 | 7.70 |
| 1 | 3 | 1106.98 | 16.31 |
| 2 | 3 | 1098.07 | 4.30 |
| 4 | 3 | 1119.98 | 11.85 |
| 8 | 3 | 1126.18 | 30.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 per shot faster than the source. A first run of 27 rounds, one job per program and round (Figure 3), gave -2.95 (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 (95% CI to 51.90 ). Against 19 the -test gives , and against 0 the Wilcoxon test gives [measured]. The interval contains both 0 and the predicted 19 , so the run does not resolve the ranking. The spread between jobs dominates a 19 effect on a 1.2 ms shot (Shapiro–Wilk on the differences). The teleportation variants differ by less than the 7.7 spread of repeated jobs (2 to 7 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 times in one circuit, with all qubits reset between copies, so the modeled gap grows by 19.22 per copy. With the analysis again fixed in advance, 15 rounds of one job per program and (120 jobs, submitted as one batch, 4 dropped by the outlier rule) give a mean gap slope of 6.97 per copy (95% CI to 22.63 , Figure 4). Against 19.22 the -test gives , and against 0 the Wilcoxon test gives [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 , 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 s per copy.
Time per copy (post hoc). The measured time per copy (41.89 and 36.69 ) matches the model at for the source and 1.95 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.
| quantity | where | model | measured | gap and mechanism |
| time per shot | Selene | per-outcome trace | 39988 of 44000 shots | at most 0.17% of a shot, from compile-time gate cancellation in Selene |
| IBM | 14, 42 ns (FPGA controllers) | 3.45 s (0.32 to 6.58) | controller time per if_else block, far above the FPGA controllers | |
| decision | QubiC RTL | 14 ns (cited) | 12 ns compare, 20 ns if no not-equal: an if adds a jump | |
| gap per shot | IBM | 19 s | 21.06 s ( to 51.90) | not resolved: job-to-job spread on a 1.2 ms shot |
| gap per copy | IBM | 19.22 s | 6.97 s ( to 22.63) | not resolved |
| time per copy | IBM | 78.35, 59.13 s | 41.89, 36.69 s | post hoc: matches a branch cost of 1.62 and 1.95 s |
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
| approach | semantics | latency | per output |
| VOQC [19] | optimizer code, Coq | no | not needed (verified code) |
| CertiQ, Giallar [20, 21] | passes, SMT and rewrite rules | no | no |
| QPPM [6] | compiler, Lean | depth bound | depth certificate |
| BQCP [2] | analysis, on paper | no | no |
| qlin | rules, Lean (cq model) | moves, Lean | normal 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 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 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 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 in the block model. With 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. grows as . On long syndrome loops 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 (95% CI 0.32 to 6.58 ), 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
| claim | statement | status |
| C1 | Hoist and merge steps, at any position and in any sequence, never delay the replay state | Lean-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 |
| C2 | With defer, the classical core can shrink to zero | hand-derived, shown on teleportation |
| C3 | The normal-form rules preserve the semantics | Lean-checked (rules, any model of A1, A2; A1, A2 Lean-checked for density matrices). M0 outputs: Lean-checked per output |
| C4 | Branch and bound finds the optimum on small inputs | exhaustive, 180 of 180 rows |
| C5 | Expected-latency gain on benchmarks | modeled (HERON_LIKE; from published controllers; three switch costs) |
| C6 | The cost model ranks variants correctly on a device | measured, not resolved (27 pairs post hoc; 60 pairs and an amplified design with copies, analysis fixed first) |
| C7 | Defer preserves distribution and state | direct form, one bit: Lean-checked. Other forms: empirical, Wolfram-checked on two instances |
| C8 | Fast-path size stays within on QEC | empirical: without the sink for ; sink variants of the larger codes reach at |
| C9 | The relaxed bound is below all completions | hand-derived, exhaustive on all prefixes |
| C10 | The fast path and the sink preserve the semantics | Lean-checked (dispatch step, whole construction, and sink, density-matrix model); fast-path outputs Lean-checked per output (910 jobs); sink outputs: empirical |
| C11 | The Pauli conjugation table | Lean-checked, Wolfram-checked, 96 simulator cases |
| C12 | Per-outcome accounting matches Selene | emulated, 39988 of 44000 shots match |
| C13 | “Defer beats the normal form” holds over the sourced ranges | modeled |
| C15 | Fast-path gain past 12 qubits at | modeled, 12.2–16.0% on 4 noisy codes; stabilizer check on 252 variants |
| C16 | Dispatch cycles on the QubiC controller logic | RTL-simulated (one core, no qubits); time linear in executed instructions within 1 cycle |
| C14 | IBM per-branch cost | measured, 3.45 s (95% CI 0.32–6.58) |
Table 9.
References
- [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]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]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]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]Yanbin Chen. Unleashing Optimizations in Dynamic Circuits through Branch Expansion, 2025. URL https://arxiv.org/abs/2504.09234.
- [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]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]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]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]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]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]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]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]Tudor Achim, Alex Best, Alberto Bietti, et al. Aristotle: IMO-level Automated Theorem Proving, 2025. URL https://arxiv.org/abs/2510.03146.
- [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]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]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]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]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]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]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]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]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]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]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]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]Yanbin Chen, Innocenzo Fulginiti, and Christian B. Mendl. Reducing Mid-Circuit Measurements via Probabilistic Circuits, 2024. URL https://arxiv.org/abs/2405.13747.
- [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]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]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]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]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]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]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]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]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]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]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]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]Kun Fang, Munan Zhang, Ruqi Shi, and Yinan Li. Dynamic quantum circuit compilation, 2023. URL https://arxiv.org/abs/2310.11021.
- [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]Lukas Burgholzer and Robert Wille. Handling Non-Unitaries in Quantum Circuit Equivalence Checking, 2021. URL https://arxiv.org/abs/2106.01099.
- [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]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]Adam Laabs. AlchemQ: Proof-Carrying Quantum Circuit Optimization with Per-Result Equivalence Certificates, 2026. URL https://arxiv.org/abs/2609.19160.
- [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]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]Charles Yuan. Cobble: Compiling Block Encodings for Quantum Computational Linear Algebra, 2025. URL https://arxiv.org/abs/2511.01736.
- [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]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]Nicolas Delfosse. Hierarchical decoding to reduce hardware requirements for quantum computing, 2020. URL https://arxiv.org/abs/2001.11427.
- [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]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]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]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.

