Verified Subroutine Libraries as the Action Space for Reinforcement Learning in Quantum Circuit Synthesis

Reinforcement learning agents that build quantum circuits one gate at a time do well on two-qubit toy targets and fail as soon as the target needs structure. On the qcd-gym benchmark, every standard agent stalls at about 0.3 similarity on the three-qubit Toffoli gate. Program-synthesis systems that learn reusable subroutines do the opposite: they discover SWAP and controlled-Z from scratch and solve almost every three-qubit target. But they rely on slow enumerative search that has not scaled past three qubits. We propose to join the two. A language-model policy is trained with verifiable rewards, meaning rewards computed by an exact checker rather than a learned judge. It writes circuits as small programs that call a library of subroutines. The library grows during training by compressing the policy's own verified successes into new named, parameterized functions. Each function is checked exactly once, and its verified behavior is cached, so later programs that call it are cheap to verify.

The two ideas help each other. The library shrinks the search the policy must do, because one call replaces dozens of gates. The same hierarchy makes the reward cheaper and more trustworthy, because verifying a program reduces to composing already-certified pieces instead of multiplying out a flat gate list. If this works, a policy trained on three- and four-qubit targets should produce correct circuits for five and six qubits by recombining certified subroutines. Neither flat reinforcement learning nor enumerative library learning has reached that regime.

Core Claim

Our claim is that on-policy reinforcement learning over a growing, exactly verified library solves structured unitary-synthesis targets that defeat both flat reinforcement learning and enumerative library learning at matched compute. The benefit comes specifically from the library being learned from the policy's own successes. A fixed, hand-chosen set of macro-gates should not give the same result.

The closest bridging work is GenCircuit-RL. It trains a language model with Group Relative Policy Optimization (GRPO, a policy-gradient method that scores each sample against others drawn for the same prompt), using a five-level reward in which each level counts only if all lower levels pass. That hierarchy lives in the reward, and the domain is genetic circuits. It motivates our use of gated rewards but differs from our proposal: its action space stays fixed, and it never learns subroutines. Porting its layered reward to quantum circuits is the obvious move at this intersection (Gap 1 in the file), and we treat that port as a baseline rather than as our contribution. HAVE places the hierarchy in agent coordination for multiplier design, not in the circuit representation. HIS learns a fixed two-layer symbolic tree that only filters an existing synthesis heuristic. Neither builds circuits constructively from learned abstractions.

Research Program

The method comes from Discovering Quantum Circuit Components with Program Synthesis. That work alternates between search over a domain-specific language and a compression step that turns recurring gate motifs into new library primitives. Starting from {H, T, T†, CNOT}, it reaches near 100% success on 1,000 target unitaries within 50 iterations. Its stated limits motivate our changes. Enumerative search times out, registers stay at three qubits or fewer, and library entries cannot take a register size as an argument. We keep the compression step and replace enumeration with a policy trained by reinforcement learning. The engineering trends in Squash 2 motivate the structural bet: keeping modules unflattened cut memory from 63 GB to 504 KB and gave a 1,608x mapping speedup on Grover's algorithm. BesiegeField similarly reports that tree-structured construction beat flat global coordinates for GRPO-trained design agents.

The policy is a code language model of moderate size. For each target unitary, given as its matrix together with a short structural description, it writes a program in a small Python-like language. The language has primitive gates, calls to library functions with qubit-list arguments, and loops over register indices. Library functions may be parameterized by register width, for example a multi-controlled X that recurses on the number of controls. This is what allows programs to reach sizes beyond the training range.

The reward is gated in the GenCircuit-RL style. The program must first parse. It must then respect qubit bounds and the target connectivity. Finally, it must implement the target exactly up to global phase. On success, the reward adds a penalty proportional to T-count and depth.

To avoid the floating-point underflow that Quasimodo documents for deep decision-diagram cascades, correctness is checked in exact arithmetic. Clifford+T matrices have entries in the ring generated by 1/√2 and i, so no rounding occurs. Beyond about six qubits, where exact dense matrices become impractical, programs are checked with the CFLOBDD backend in Quasimodo, which treats pieces of a decision diagram as reusable procedure calls. We also consider the reduction to classical Boolean equivalence in Symbolic Verification. Both representations fit a program that is itself built from calls.

Every K policy updates, the compression step runs over all verified successful programs collected so far and proposes abstractions that shorten the corpus. Each candidate is verified symbolically: parameterized entries are checked at several widths, and an entry is admitted only if it passes at every width tested. Admitted entries are added to the language with their certified matrices cached, and the prompt is updated. Because every library entry is exactly certified, the reward cannot pass a wrong program. This matters because the verifier-quality literature shows that policies exploit loose checkers quickly.

The analysis has three parts. We track what the library contains over training, checking whether it rediscovers SWAP, controlled-Z, and Toffoli ladders or finds cheaper non-textbook constructions. We measure verification cost per rollout with and without cached subroutines. We also test whether width-parameterized entries are what drive generalization to larger registers.

Baselines

The naive reference point is flat GRPO. The same model, data, and exact verifier are used, but the model writes flat gate lists over the primitive gate set, gets only the terminal correctness reward and cost penalty, and has no library. It isolates what the hierarchy adds. For context we also report the qcd-gym agents as published in Challenges for Reinforcement Learning in Quantum Circuit Design. On Toffoli composition they report a mean similarity of only 0.3, and SAC reaches about 0.7 mean fidelity on GHZ state preparation. We also report the PPO results of the directed synthesis environment: 96–100% success on two-qubit Bell states, with degradation beyond two qubits.

The second baseline ports GenCircuit-RL to quantum circuits. It uses flat programs with a multi-level gated reward whose levels are parse, connectivity, a light-cone local consistency check following Scalable Equivalence Checking of Shallow Quantum Circuits, and full equivalence. It asks whether denser reward alone closes the gap. GenCircuit-RL reports a 14–16 percentage-point gain over binary rewards on SynBio-Reason. We have no reported quantum result for this configuration, so we will produce it ourselves.

The strongest existing method is the DreamCoder-style synthesizer of Sarra, Ellis, and Marquardt. It reports near 100% success on 1,000 three-qubit target unitaries within 50 iterations and a 17-order-of-magnitude gain in discovery probability. We rerun it on our target suite with the same wall-clock budget and the same verifier. Beating it means two things: matching its three-qubit solve rate at equal or lower compute, and clearly exceeding it at four to six qubits. It is reported not to reach that range, so no reported result was found for it at those widths.

Two ablations isolate the key ingredient. In the first, the library is hand-specified and fixed: SWAP, CZ, Toffoli, and textbook multi-controlled ladders are added as primitives at the start, and nothing is learned. In the second, the library is learned but not cached, so every program is expanded and verified flat; this measures the verification-cost claim separately from the search claim. Every arm uses the same base model, the same target distribution, the same number of rollouts, and the same hyperparameter search budget, with three seeds each.

Why not just…?

Why not just give the flat agent a denser, layered reward? This is the GenCircuit-RL recipe, and it is the most natural alternative. Its value in synthetic biology came from catching syntax and structure errors early. In unitary synthesis, parsing and connectivity are easy, and the hard step is the last one: finding a composition that implements the target. The Toffoli failure in qcd-gym happened under a well-defined dense similarity signal. That suggests the bottleneck is how much the agent must search, not how sparse the reward is. The layered-reward baseline tests this directly. If it matches our method at four to six qubits, the library is not needed and we would say so.

Why not just hand the agent a fixed macro-gate library? This is the real threat. On textbook targets such as multi-controlled gates, a hand library may do as well as a learned one. We address it with the fixed-library ablation. We also add held-out target families built from QASMBench-derived circuits and random compositions of non-textbook motifs, where hand-picked macros offer no obvious shortcut. If the fixed library matches ours everywhere, the contribution narrows to cheaper verification, and we would report it that way.

Why not just fine-tune on compiled circuits? Supervised fine-tuning can learn the surface form of decompositions, but nothing checks that its outputs are correct. The solver-grounded RL results in SIRL show the gap is large: the instruct model scored 16.6% on OptMATH, and verifier-trained RL scored 45.8%. We include a supervised arm trained on synthesized textbook decompositions of the training targets, and we also use it as a warm start for all RL arms. This keeps the comparison about exploration and abstraction, not about starting from different initial models.

Why not just give DreamCoder more compute? Its limits at three qubits come from exponential enumeration, so extra compute buys little per added qubit. Running it at matched and at 4x wall-clock budget will show whether its solve rate at four to six qubits keeps rising or levels off.

Proposed Experiments

The target suite has three tiers. The first reproduces the three-qubit protocol of Sarra et al., with 1,000 targets over {H, T, T†, CNOT}. The second covers the qcd-gym unitary-composition targets, with Toffoli as the headline case. The third consists of held-out four- to six-qubit targets: multi-controlled gates, reversible adders, and small QASMBench circuits from QASMBench, converted to target unitaries. Training uses tiers one and two plus four-qubit instances only.

The metrics are exact solve rate, T-count relative to the best known decomposition, verifier seconds per rollout, and library size and reuse. For extrapolation, we take width-parameterized programs and check them symbolically at 8 to 64 qubits with CFLOBDDs.

The decisive checks are as follows. The first is whether our method beats the layered-reward flat baseline and matched-compute DreamCoder on six-qubit solve rate. The second is whether the learned library beats the fixed hand library on the non-textbook held-out family. The third is whether caching cuts verification time per rollout by a large factor without changing correctness, which we will spot-check against flat exact verification. A negative result on the second check, with a positive result on the first, would still establish that hierarchy in the action space helps, though not that learning the library does.