Optimizing Quantum Circuits, Fast and Slow

Quantum circuit optimisers come in two incompatible kinds — pattern-matching rewrite rules that are instant but see only a few gates at a time, and unitary resynthesis that throws away a subcircuit and searches for a shorter replacement from scratch, which is powerful and takes minutes; GUOQ (Wisconsin) makes both look identical to the search by wrapping each as a black box with an error budget, then answers the question of what order to apply them in by not answering it, sampling randomly and beating a reinforcement-learning superoptimiser that needs a GPU.

Why this problem is worth solving

The two techniques available are almost perfectly complementary, which is why nobody combined them.

Being slightly wrong on purpose is a resource, provided you budget it.

What people did before, and where it broke

• Apply a fixed sequence of hand-crafted rewrite passes. What production compilers do: a curated list of rules, run in a curated order. Reliable, fast, and shipped in every toolkit. Where it broke. The rules are local by construction, the order is fixed regardless of the circuit, and the result stalls quickly — measured here, rules alone reach a local minimum within minutes and stay there for the rest of an hour.
• Synthesise the rewrite rules automatically. Rather than hand-writing rules, search for valid ones and use those, which produces far more of them. Where it broke. More rules is still only rules: the patterns remain small, exactness is still required, and the schedule problem is unchanged.
• Partition the circuit and resynthesise each piece. Cut a large circuit into subcircuits of a few qubits, hand each to a unitary synthesiser, and reassemble. This genuinely does what rules cannot. Where it broke. The partition is chosen once, so improvements available only across a different cut are unreachable, and the whole thing is slow enough that a fixed partition is all you get.
• Search over rewrite rules with a beam. Keep many candidate circuits, try every rule on each, keep the best. More thorough than a fixed schedule. Where it broke. Every iteration generates a candidate per applicable transformation, so the queue grows enormously and the search moves through the space slowly.
• Learn the schedule with reinforcement learning. The most sophisticated prior approach trains a policy to choose which rewrite to apply where. Where it broke. It needs a high-end GPU to run, it was trained on part of the benchmark suite it is evaluated on, and it is still rules-only — none of the training buys the ability to approximate or to rebuild a deep subcircuit.
• The gap. Every approach picks one of the two techniques and then invests in scheduling it better. Combining them was blocked by the phase-ordering problem — knowing when a slow, powerful move is worth its cost — which is exactly the question optimising compilers have never answered.

How two incompatible optimisers become one

The idea

Making the two techniques indistinguishable is what allows them to be combined at all. The obstacle was never that rules and resynthesis conflict but that they are described in incompatible terms — one is a pattern and a substitution, the other is a matrix and a search — so any system using both has to decide, explicitly, when a slow powerful move earns its cost against a fast weak one. The move here is to refuse to model that at all. A transformation is defined as nothing more than a function from a subcircuit to a replacement that does the same thing within a stated tolerance, and both techniques instantiate it: a rewrite rule with tolerance zero, a resynthesis call with whatever tolerance you allow. The accompanying result is deliberately unambitious — the deviation after a sequence is at most the sum of the individual deviations — and its crudeness is the point, because it holds for any sequence whatsoever, which is what lets the search stop reasoning about order. The tension between fast local pattern matching and slow global search is the same one the compiler synthesis work covered elsewhere on this site confronts for instruction selection, where the conclusion was that pattern matchers only find what somebody wrote down and synthesis should replace them; here the conclusion is that neither should be replaced.

The phase-ordering problem is answered by declining to answer it. Having made the transformations interchangeable, the natural next step is to be clever about which to apply where, and the paper reports trying exactly that and losing. A beam search keeping many candidates and applying every transformation to each moves through the space too slowly, because each iteration spawns a candidate per applicable rule. Splitting the hour in half — rules first, then resynthesis, or the reverse — is worse than interleaving, and notably the two orders reach different answers, which is itself evidence that ordering matters and therefore that getting it right is hard. What wins is a loop that samples a transformation uniformly, samples a location uniformly, applies it, and keeps it if the cost did not rise. The authors are explicit that this is a bitter lesson: the landscape has too little structure to reward a hand-crafted heuristic, and the payoff comes from covering ground quickly rather than from choosing well. It beats a reinforcement-learning superoptimiser that requires a high-end GPU and was trained on part of the benchmark suite, on 80 percent of the benchmarks. Searching a space of compiler decisions where the knobs interact and the ordering is itself a knob is precisely the problem the Bayesian autotuning work covered elsewhere on this site attacks with careful modelling — and the finding here is that for this particular landscape, careful modelling loses to speed.

Approximation is a resource, and treating it as a budget is what makes it safe to spend everywhere. Rewrite rules cannot approximate because a rule is an equality; resynthesis can, and that is a large part of why it finds circuits rules cannot. The framework turns this into an accounting problem: every transformation declares its tolerance, the running total is tracked, and any move that would breach the ceiling is skipped in favour of trying again with something free. The ceiling used throughout is small enough to be almost philosophical — many orders of magnitude below the error of a single two-qubit gate on real hardware, and comparable to the logical error rate of one error-correction cycle — so the approximation is genuinely free in physical terms while unlocking optimisations that exact reasoning cannot express. Spending a deliberate, provably bounded amount of inaccuracy to get a circuit that actually runs better on noisy hardware is the same trade the approximate circuit work covered elsewhere on this site makes when it observes that on a machine where every two-qubit gate costs one to three percent error, the exact circuit often gives worse answers than a shorter approximate one.

Following one circuit through an hour of random moves

The cost is a soft objective and the error ceiling is a hard constraint. A weighted sum lets a single number express, for example, that reducing one gate type is worth twice as much as another.

Why it works

• An abstraction removes the question that was blocking the combination. Rules and resynthesis are described in incompatible terms, so any system using both must decide explicitly when a slow move earns its cost → but defining a transformation as merely a function returning an equivalent subcircuit within a stated tolerance makes them indistinguishable → so the search never has to know which kind it just applied.
• A deliberately crude error bound buys unlimited freedom of ordering. A tight bound on accumulated approximation would depend on which transformations were applied in what order → whereas proving only that deviations add gives something true for every sequence → so the search can apply anything anywhere and stay correct by tracking a single running total against a ceiling.
• The landscape is too unstructured to reward planning. Beam search generates a candidate per applicable transformation each iteration and crawls; splitting the time budget into a rules phase and a resynthesis phase does worse than mixing, in both orders → so covering ground quickly beats choosing well → and uniform sampling outperforms a learned policy that needs a GPU and had seen part of the test set.
• The two techniques fail in opposite ways, which is what makes interleaving pay. Rules stall in a local minimum within minutes because their moves are small and local; resynthesis progresses steadily but each call costs minutes → so a rare resynthesis call relocates the candidate somewhere the cheap rules have fresh work again → and the combination beats either alone on almost every benchmark.
• The cost asymmetry has to be reflected in the sampling, not the reasoning. A rewrite rule costs microseconds and a resynthesis call minutes, which would ordinarily demand a scheduler → instead the expensive move is simply drawn 1.5 percent of the time and issued asynchronously so cheap work continues while it thinks → which captures the economics without any decision logic at all.

What it costs (trade-offs and scope)

• Most of the gain comes from resynthesis, not from the unification. The ablation states plainly that the bulk of the reduction is resynthesis working on its own, with rules pushing it further. The framing of combining fast and slow is accurate and slightly oversells relative to using the powerful technique and interleaving cheap rules.
• On error-corrected gate sets the balance inverts and the tool loses. For the fault-tolerant target, unitary synthesis over a finite gate set is much harder, rules contribute more than resynthesis, and a specialised graphical-calculus optimiser beats this one on the primary objective — matched or exceeded on only 45 percent of benchmarks.
• Everything is given an hour, which favours a search. Production compilers optimise for compile time as well as quality, so a comparison at equal wall clock is not a comparison at equal intent. The paper does use each tool at its most aggressive setting, which is the fair version of this choice.
• The approximation budget is a real asymmetry in the comparison. This tool and one baseline are permitted a small tolerance; the exact optimisers are not. The threshold is well argued — far below a physical gate error, comparable to one correction cycle — and it still means a slightly easier problem is being solved.
• One baseline was trained on part of the benchmark suite, which the paper states. Beating it anyway is meaningful and the comparison is not clean.
• The algorithm is barely annealing. The temperature was swept and set so that worsening moves are accepted very rarely, making this closer to randomised hill-climbing. The name is inherited from the family rather than earned by the behaviour.
• Several parameters were tuned on the same benchmarks used to evaluate — the temperature, the 1.5 percent resynthesis probability, and the three-qubit subcircuit limit.
• The slow mode is not very global. Resynthesis is capped at three-qubit subcircuits, so the powerful technique still sees a narrow window; what it gains over rules is depth within those qubits rather than breadth.
• Asynchronous resynthesis throws work away. When a resynthesis result is accepted, every rewrite applied while it was thinking is discarded, so some fraction of the cheap work is wasted by construction.
• Mapping and routing are excluded. Tools may freely change which qubits connect to which, and the interaction with hardware connectivity — which can undo optimisation gains — is out of scope.
• The objective may be shifting underneath. The paper notes recent work reducing the cost of the resource that makes one gate type expensive in error correction, and says the focus on minimising it alone may soon need recalibrating.
• Benchmarks run to 36 qubits, which is small against deployed machines, though the limit is inherent to what unitary synthesis can reach.

The evaluation

Check yourself

Sources

The paper is “Optimizing Quantum Circuits, Fast and Slow” by Amanda Xu, Abtin Molavi, Swamit Tannu and Aws Albarghouthi, published at ASPLOS 2025, pages 777-793, DOI 10.1145/3669940.3707240. The authors are at the University of Wisconsin-Madison.

This explainer is written from the full arXiv text, arXiv:2411.04104. Everything above comes from the paper’s own sections: the background on quantum circuits, rewrite rules and unitary synthesis with worked examples showing a case where rules reach an answer synthesis cannot and a case where the reverse holds, and the table contrasting the two on speed, what limits them, and whether they can approximate; the unifying framework defining a circuit transformation as a closed-box function with an associated tolerance, together with the theorem bounding accumulated approximation by the sum of individual tolerances; the statement of circuit optimisation as a constrained problem with a cost function as a soft objective and an error ceiling as a hard constraint, including the weighted-sum example for the fault-tolerant setting; the algorithm itself with its random transformation and subcircuit selection, its acceptance rule and temperature, and its error tracking, along with the correctness theorem; the implementation notes on weighting the sampling towards rewrite rules, growing subcircuits from a random node, and issuing resynthesis calls asynchronously; and the evaluation covering the five gate sets, the seven comparison tools and their approaches, the 247-circuit benchmark suite, the experimental allocations, the comparison against state of the art on two-qubit gate reduction and fidelity, the ablation isolating rules and resynthesis, the comparison against beam search and two split-phase orderings, the fault-tolerant experiments including the loss to a specialised optimiser and the analysis of why, and the composition experiment running the optimiser on that tool output.