Moving Measurements Earlier: When Does Complete AC Matching Pay Off for Qubit Reuse?

Quantum hardware can now measure a qubit partway through a circuit, reset it, and reuse it. A compiler that measures each qubit as early as possible can therefore run an algorithm on far fewer physical qubits. How early a qubit can be measured depends on which operations may legally be reordered around the measurement. Current compilers treat two operations as reorderable mostly when they act on different qubits. Physics allows much more. A measurement is non-destructive for an observable (the quantity being read out) when it leaves that observable's value unchanged, and this holds whenever the observable commutes with the evolution that follows. A measurement in the computational (Z) basis therefore commutes with every gate that is diagonal in that basis, even gates on the same qubit. A controlled gate whose control is the measured qubit can then be replaced by a gate driven by the classical measurement result. Once these facts are written as equations, reordering a circuit becomes term rewriting modulo associativity and commutativity (AC): diagonal gates behave like an unordered bag of symbols with cancellation laws. The automated-reasoning literature has complete algorithms for that problem, but it also shows the problem is NP-complete in the worst case.

This note proposes to build a measurement-aware equational rewriter for qubit reuse and to use it to settle an empirical question the field has not asked. Does complete AC matching find qubit savings that a cheaper, enlarged pairwise-commutation check misses? And does its worst-case exponential cost ever appear on real circuits? The answer is useful whichever way it goes. If complete matching adds nothing beyond a smarter pairwise check, compiler writers can skip it. If it adds savings, we learn which circuit families need it and at what compile-time price.

Core Claim

We claim that the qubit savings available from mid-circuit measurement come in two tiers.

The first tier comes from non-demolition commutation. A Z-basis measurement slides past gates that are diagonal on its own qubit, and controls on a measured qubit become classical controls. This tier can be captured exactly by adding one semantic rule to the pairwise commutation test inside an ordinary dependency graph (a DAG, or directed acyclic graph, recording which gate must precede which). Captured this way, it keeps polynomial cost.

The second tier needs reasoning over whole bags of gates. Examples include two controlled-Z gates that cancel only after regrouping, rotation angles that sum to a Clifford or to the identity, and diagonal gates separated by other diagonal gates on overlapping qubits. Pairwise tests cannot see these. The second tier requires matching modulo AC with cancellation, which is the object studied by Stickel's complete AC unification algorithm.

Our prediction is that tier two matters mainly on diagonal-heavy families: IQP circuits (Instantaneous Quantum Polynomial circuits, built largely from commuting diagonal gates), QFT, and phase estimation. We also predict that the matching instances arising in practice are small bags, so the NP-complete worst case identified by Dershowitz et al. is rarely reached. The second prediction is an empirical claim about instance distributions. We will measure it rather than assume it.

The closest existing work is Dynamic quantum circuit compilation. It already exploits gate commutativity for qubit reuse through DAG reordering, a binary integer program, and greedy heuristics. It does not formalize commutation as an equational theory. From the material available, we also cannot tell whether it uses same-qubit non-demolition commutation or the conversion of quantum controls into classical ones. Our proposal differs in three ways. It makes the commutation relation an explicit, checkable rewrite theory. It separates what pairwise commutation buys from what complete bag-level matching buys. It reports the empirical cost of completeness.

Research Program

The equational theory. We first write the theory $E$ that the rewriter works modulo. Its first part is the non-demolition rule, taken directly from the commutation criterion $[\hat{A}, \hat{H}] = 0$. That criterion is used in Stace et al.'s parity measurement analysis and in Brun's spin-readout simulations as the physical condition for readout without disturbance. Those papers supply the physical justification. We reuse the condition as a side condition on a rewrite rule: a Z measurement of qubit $q$ may move past a gate $G$ exactly when $G$ commutes with $Z_q$. The second rule turns a controlled gate with a measured control into a classically controlled gate. The third part treats diagonal gates as an AC operator with a unit, adding that rotation angles combine additively modulo a fixed period and that controlled-Z is self-inverse.

Following the classification scheme of Siekmann and Szabó, which sorts theories by how many most-general solutions their unification problems admit, we will determine the unification type of each fragment of $E$. We have a concrete conjecture here. The cancellation laws turn Stickel's non-negative Diophantine systems into linear equations modulo a period. Such equations can be solved by elimination, so the self-inverse fragment may be much easier than plain AC. If this holds, it would explain any empirical tractability we observe.

The rewriter. We will implement the rewriter in two layers. Rule selection uses the two-stage design of Bachmair et al.'s AC discrimination nets. A cheap index keyed on symbol counts discards rules that cannot match, and only the survivors reach the full AC matcher. Bachmair et al. evaluated this design only on one-way matching for term rewriting. We reuse it on circuit terms.

We also need Stickel's full two-way unification offline, to compute overlaps between rules of $E$. These overlaps, called critical pairs, are places where two rules apply to the same term. Checking them confirms that the rewrite system is confluent and that no rewrite is lost. Confluent means the order in which rules are applied does not change the final result.

Matching runs independently on per-qubit subcircuits. The resulting substitutions are then merged using the iterative substitution-unification procedure of van Vaalen. That paper proves that merging the solutions of subproblems gives the same result as solving the combined problem. Van Vaalen's result has never been tested on a real workload, so the merge itself is part of what we evaluate.

The scheduling problem. Once the rewriter has exposed which measurements can move earlier, qubit reuse is still a scheduling problem. For that step we reuse the heuristics and exact integer program of Dynamic quantum circuit compilation unchanged. Our contribution is limited to enlarging the set of legal reorderings that the scheduler sees.

Baselines

Naive reference. Static compilation with no qubit reuse, where the qubit count equals the circuit width. This defines the ceiling every other method is measured against.

Strongest existing method. The DAG-plus-heuristic compiler of Dynamic quantum circuit compilation. The file reports that it "outperformed the previous leading method, DCKF, in 98.5% of random circuits" and nearly 100% of IQP circuits, and that it reduced Simon's algorithm "from $2n$ qubits to just 3 qubits, regardless of the input size $n$". It is the strongest competitor because it already exploits commutativity for exactly this objective. We will run its greedy, hybrid, and exact integer-program modes on identical input circuits, on the same machine, with the same wall-clock limit per instance.

Beating it means one of two things. The first is a strictly lower qubit count on a meaningful fraction of structured circuits while matching it everywhere else. The second is equal qubit counts at lower compile time. Matching the Simon result is a sanity requirement, not a win.

Key ablation. This is the baseline we expect to be hardest to beat. It is the same compiler with its pairwise commutation test enlarged by our non-demolition rule and the classical-control rule, but with no AC matching. Comparing it to the full rewriter isolates exactly what complete bag-level reasoning adds.

Second ablation. The full rewriter with the discrimination-net filter removed. This measures whether the filter drives the compile-time cost. Bachmair et al.'s claim that matching dominates execution time, up to 90% as they cite, suggests that it will.

Exact reference. On small circuits, the exact integer program over the enlarged move set gives an optimum. It tells us how far each heuristic is from the best possible result.

Why not just…?

Why not just enlarge the pairwise commutation check in the existing DAG compiler? This is the real threat, and the research program is built around it. Equivalence under pairwise commutation is the kind of reordering a dependency graph already captures in polynomial time. If the non-demolition rule alone accounts for nearly all qubit savings, the honest conclusion is that complete AC matching is unnecessary. We would then publish that result together with the enlarged-predicate compiler. The key ablation settles the question family by family. Our prediction that tier two matters only on diagonal-heavy circuits is falsifiable in exactly this comparison.

Why not just use ZX-calculus simplification? ZX-calculus is a graphical rewriting system for quantum circuits, and ZX-based tools such as ZX-DB handle phases and commuting spiders natively. However, they optimize a diagram, not a qubit-reuse schedule. Extracting a circuit with mid-circuit measurements from a simplified diagram is a separate, hard step, and the ZX calculus has also been shown incomplete for general quantum mechanics. We will include a ZX-simplify-then-schedule pipeline as an additional comparison wherever extraction succeeds, and report how often it fails.

Why not just search for reorderings by simulation? Simulation can check a candidate reordering, but it cannot generate reorderings. Full state-vector checking scales exponentially in qubit count, and the benchmark generators in VeriQBench reach beyond 50 qubits. We use simulation only as a correctness oracle on small instances, not as a competitor.

Proposed Experiments

Circuits. The dynamic and combinational classes of VeriQBench: Bernstein-Vazirani, QFT, phase estimation, Grover, adders, Clifford circuits, and semiclassical QFT. To these we add the random, IQP, and structured-algorithm circuits used by Dynamic quantum circuit compilation. VeriQBench reports no quantitative tool results, so no reported result found on Lacuna for any prior qubit-reuse method on that suite; our runs will be the first. Repeat-until-success circuits, which loop until a measurement gives the desired outcome, are outside scope, because the scheduler we reuse does not handle loops. We will state this exclusion explicitly.

Metrics. Per circuit, we record physical qubit count, depth, compile time, and idle time of measured qubits. Idle time is a crude proxy for the decoherence risk that imperfect non-demolition fidelity introduces. That risk is not otherwise modeled here, and this is a limitation. To test the complexity prediction, we log every AC matching call: bag size, number of distinct variables, and number of minimal solutions.

Correctness. Every rewritten circuit is checked against its original by exact simulation up to roughly 25 qubits. At larger sizes we use randomized input-output testing, an incomplete check, reported with its sample count.

Decisive checks. Three results decide the outcome.

The first is the gap between the key ablation and the full rewriter. If the full rewriter lowers qubit count on under a small, pre-registered fraction of structured circuits and on no family consistently, tier two is not worth its cost.

The second is the tail of the logged matching-instance distribution. If more than a trivial fraction of calls exceed the per-call time limit, the tractability prediction fails. The theoretical conjecture that the cancellation fragment is polynomial must then be examined against those hard instances.

The third is whether Simon's and Bernstein-Vazirani reproduce the published reductions under our pipeline. Failure there means our integration with the reused scheduler is broken, and no other comparison can be trusted until it is fixed.