Latency-Preserving Rewrites and Translation Validation for Dynamic Quantum Circuits
Rylan Malarchick
quant-ph
Nov 14, 2026 · v1
cs.PL
TL;DR
Proves in Lean 4 with Mathlib that the compiler's rewrite rules preserve semantics and latency, and that its translation-validation checkers are sound.
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.
Problem
Dynamic quantum circuits branch on mid-circuit measurement outcomes, so qubits wait for feedforward latency and for controller decisions. Existing compilers remove statically known branches. None proves that a rewrite cannot delay a program whose timing includes feedforward latency.
Approach
qlin is a Rust compiler that puts programs in a normal form by hoisting and merging operations out of branches. For likely error-correction syndromes it compiles a fast-path multiway switch and keeps the original program as the fallback. A cost model decides when to replace classically controlled gates with quantum-controlled ones. A Lean 4/Mathlib development (6585 lines, 73 sorry-free theorems) proves the rewrite rules preserve the density-matrix semantics, proves the latency theorems, and proves the translation-validation checkers that validate the Rust outputs sound.
Results
All 976 compiled outputs pass translation validation. At QICK's 42 ns per-decision cost, 10 of 65 programs run at least 10% faster than the best baseline in the model, up to 91.2%. On QubiC RTL, a distance-5 repetition decoder selects its correction in 21.3 instead of 151.1 expected cycles. IBM device timing runs were too noisy to confirm or reject the model's ranking.