Counterexample-Guided Synthesis of Trainable Quantum Circuit Families

Variational quantum algorithms train a parameterized quantum circuit, a sequence of gates whose rotation angles are tuned by a classical optimizer, so that the circuit's measured output minimizes an energy or a loss. They run into barren plateaus. A barren plateau is a training landscape so flat that gradients shrink exponentially with the number of qubits, so estimating them needs exponentially many measurements. The field knows a good deal about why this happens: circuits that are too expressive, measurements that involve every qubit at once, and hardware noise each cause it. Yet circuit designers still pick architectures by hand and find out whether they train by running them. We propose to automate this choice with counterexample-guided inductive synthesis (CEGIS), a loop from program synthesis in which a proposer suggests a candidate program and a checker either certifies it or returns a concrete input where it fails. The candidate is not a single circuit. It is a small program that outputs a circuit for every qubit count $n$, and the checker's counterexamples are of the form "at $n^*$ qubits, these specific generators combine to scramble the state" or "at $n^*$ qubits, this depth drowns in noise."

What would be new is matching the shape of the synthesis problem to the shape of the trainability problem. Barren plateaus are a statement about all system sizes, and CEGIS was built to handle "for all inputs" specifications using a few well-chosen inputs. Treating qubit count as the input lets us use an exact, cheap check on small sizes: we compute the Lie algebra generated by the circuit's Pauli-string generators, and stop as soon as it outgrows a polynomial budget. We then reserve expensive statistical checks for one final large-$n$ test. The checker also reports why a candidate failed, which no current automated method does. In particular, it separates scrambling caused by too much expressivity, which calls for removing structure, from concentration caused by noise, which calls for a hard limit on depth.

Core Claim

A CEGIS loop whose checker returns typed, size-indexed counterexamples will find circuit families that keep gradient variance polynomial and reach target energies on standard Hamiltonians. It will do so with fewer candidate evaluations than generate-and-test using the same checker. Under hardware noise, it will match or beat continuous architecture pruning, because its depth decisions come from a noise model rather than from gradients that may already have vanished.

Positioning Against Prior Work

The file finds no prior CEGIS loop applied to barren plateaus. Three nearby lines each supply one piece.

The barren-plateau theory supplies the specification. Barren Plateaus in Variational Quantum Computing reviews why the dimension of the dynamical Lie algebra matters. That algebra is the real span of the circuit's generators closed under commutators; if its dimension grows exponentially in $n$, the landscape concentrates, and if it grows polynomially, concentration can be avoided. Noise-Induced Barren Plateaus in Variational Quantum Algorithms proves that local Pauli noise drives gradients to $O(2^{-\alpha n})$ once depth grows linearly in $n$, and that neither initialization nor local cost functions can fix this. That result constrains our design: any certificate must include a depth budget tied to noise strength. Dynamic parameterized quantum circuits: expressive and barren-plateau free gives a second, non-Lie-algebraic certificate. If mid-circuit measurements and feedforward keep the distance from every qubit to the nearest past measurement (the feedforward distance $f$) constant, variance stays polynomial. That paper lays out its circuits by hand on regular lattices, and we automate the layout.

The synthesis literature supplies the method. CounterExample Guided Neural Synthesis pairs a statistical proposer with an exact checker and roughly doubles the number of benchmarks solved (21 versus 12 for one-shot generation). We reuse that proposer–checker split, applied to circuit families instead of bit-vector programs. Are There Good Mistakes? A Theoretical Analysis of CEGIS proves that a checker returning only the minimal counterexample loses no synthesis power. That justifies always returning the smallest failing $n$, which is also the cheapest to check. The same paper shows that restricted checkers can stall, returning nothing although the candidate is wrong. That is our main risk, since checking only small $n$ is such a restriction, and we address it with a final large-$n$ falsification step described below.

The closest automated architecture work is Escaping Barren Plateau: Co-Exploration of Quantum Circuit Parameters and Architectures (AntiBP). It attaches continuous on/off switches to gates and prunes them by gradient descent. It searches with gradients rather than counterexamples and gives no certificate, and its switch gradients can vanish if the starting circuit already sits on a plateau. Discovering Quantum Circuit Components with Program Synthesis runs DreamCoder-style search and library learning over discrete gates for 3-qubit unitaries. It has no continuous parameters and no notion of landscape geometry, and we borrow only its library-learning idea as an optional extension.

One paper cuts against the whole enterprise, and we address it directly. Does provable absence of barren plateaus imply classical simulability? argues that nearly every provably plateau-free architecture, including those with polynomial Lie algebras, lives in a small subspace that classical computers can simulate efficiently. The families our Lie-algebraic arm certifies will therefore likely be classically simulable. We treat this as a measured outcome rather than hiding it. Every synthesized family is run through a classical Lie-algebraic simulation attempt, and the result is reported. The feedforward-distance arm is the one place where certified families might fall outside known simulable classes. Whether they do is an open empirical question that this project will report on but does not promise to answer.

Research Program

The proposer searches a small domain-specific language of ansatz-family programs. A program takes $n$ and emits a layered circuit. Its constructs are Pauli-string generator templates with locality and connectivity patterns, layer counts expressed as functions of $n$ (constant, $\log n$, linear), measurement-and-reset placements for dynamic circuits, and a choice of which observable to measure. Search is enumerative, guided by a probabilistic grammar whose weights are updated from accumulated counterexamples. Each counterexample is turned into a blocking constraint over program fragments, the same way a counterexample in syntax-guided synthesis rules out a whole class of programs that evaluate identically on it.

The specification a family $P$ must satisfy, for all $n$ in a target range and for a given noise rate $p$ and accuracy target $\varepsilon$, has three parts. The first is a trainability certificate. Either $\dim \mathfrak{g}(P, n) \le c\, n^k$, where $\mathfrak{g}(P,n)$ is the Lie closure of $P$'s generators at size $n$ and $c, k$ are fixed budget constants, or the feedforward distance satisfies $f(P,n) \le f_{\max}$. The second is a noise budget: the depth $L(P,n)$ stays below the level at which the bound of Wang et al. predicts gradients under shot noise for $p$. The third is task accuracy: optimized energy error at most $\varepsilon$ on the target Hamiltonian at validation sizes.

The checker evaluates these in order of cost and returns one of three typed counterexamples. An algebraic counterexample gives the smallest $n^*$ at which Lie closure exceeds budget, together with the commutator chain that pushed it over. Closure of Pauli strings needs only exact bit operations, and because we stop at the budget, the check is cheapest on exactly the candidates that fail. A noise counterexample gives the smallest $n^*$ at which depth exceeds the noise budget. A task counterexample gives a Hamiltonian instance and size at which the energy error exceeds $\varepsilon$, a signal that the family is too restricted. The algebraic and task counterexamples push the search in opposite directions, and that tension is what keeps the loop from collapsing to trivial circuits.

Because certifying all $n$ from small-$n$ checks is not sound in general, any family that passes is sent to a final falsifier. This step estimates gradient variance by sampling at the largest size we can simulate and checks that the decay against $n$ fits a polynomial rather than an exponential. A failure there becomes a fourth, statistical counterexample type. How often that fires is a direct measurement of the blind-spot risk identified in the CEGIS theory.

Baselines

The naive reference point is a fixed hardware-efficient layered ansatz at the benchmark's depth with uniform random initialization. On the 66-layer Heisenberg circuit it is known to fail to learn at all (An initialization strategy for addressing barren plateaus in parametrized quantum circuits). It anchors every gradient-variance and energy plot.

The strongest existing automated method is AntiBP (Escaping Barren Plateau). It is the right main competitor because it is the only cited method that searches over architectures and is evaluated under noise. On 14-qubit H₂O at depth 80 under depolarizing noise, it reports a 45.97% energy-gap improvement over baseline VQE and prunes 2,240 gates to 867. We rerun it on our noise model, molecules, and simulator, with the same total number of circuit evaluations as our loop counted end to end. Beating it means a lower energy gap than AntiBP at matched evaluations on H₂O under noise, with at most comparable gate count. Matching it while also supplying a certificate and typed failure diagnoses is the weaker but still useful outcome.

Two initialization baselines run on the same fixed ansatz. Identity blocks reached convergence on the 66-layer, 7-qubit Heisenberg model and trained a 132-layer, 10-qubit MNIST classifier, but they degraded H₂O under noise by 4.36% in the AntiBP comparison. Gaussian initialization with variance $O(1/L)$ (Escaping from the Barren Plateau via Gaussian Initializations) reached $10^{-4}$ energy error on LiH versus $10^{-1}$ for uniform initialization. For gradient variance on the 15-qubit Heisenberg model, the file gives no reported number, only qualitative curves. We therefore recompute that quantity ourselves for all methods.

The ablation that isolates the key ingredient is generate-and-test. It samples from the same grammar with the same checker, but discards failure information: the checker returns only pass or fail, with no $n^*$, no commutator chain, and no type. A second ablation strips the type but keeps $n^*$. If the full loop does not certify families in clearly fewer checker calls than generate-and-test, the counterexamples are not earning their place.

Why not just…?

Why not just use identity-block or Gaussian initialization on a standard ansatz? Both are cheap and work in noiseless settings, and we run both. They do not change the architecture, though, so they cannot help with noise-induced plateaus. Wang et al. prove that initialization cannot fix those, and the 4.36% degradation of identity blocks on noisy H₂O is consistent with this. Gaussian initialization also requires a nonzero gradient at the origin, which symmetric Hamiltonians can violate. If either method matches our loop on noisy H₂O and MaxCut, the synthesis machinery is not justified for those settings, and we will say so.

Why not just run AntiBP-style continuous pruning? This is the real threat. AntiBP already achieves large gains on noisy H₂O. Its weakness is that pruning decisions ride on gradients, which vanish if the starting circuit is on a plateau. The decisive experiment starts both methods from deeper, wider over-parameterized circuits, where plateaus are stronger. Our prediction is that AntiBP's switch gradients collapse while the counterexample loop, which never differentiates through the circuit to make structural choices, does not. If AntiBP holds up there too, our advantage reduces to certificates and diagnoses.

Why not just filter random architectures by Lie-algebra dimension, without the loop? This is generate-and-test, and it is our main ablation. It may be competitive when the grammar is small. We expect the gap to widen as the grammar grows, because a commutator-chain counterexample rules out every program containing that fragment, not just one candidate.

Why not just pick a known plateau-free family, or simulate classically? For Lie-algebraic certificates this criticism largely stands, given Cerezo et al. Our answer is partial. The value of that arm is automatic, noise-aware design for a given Hamiltonian, and the feedforward-distance arm explores certified dynamic circuits whose simulability status is unknown. We report classical-simulation outcomes for every output rather than claiming quantum advantage.

Proposed Experiments

We use the benchmarks from the cited work: the 1D Heisenberg model at 7 and 15 qubits, LiH at 4 and 12 qubits, H₂O at 14 qubits under depolarizing noise, the transverse-field Ising and XY models with dynamic circuits (where the original dynamic-circuit work reports infidelity near $10^{-4}$), and QAOA on random-graph MaxCut under an IBM-style noise model. On hardware, Wang et al. found gradients hit the shot-noise floor near $n=9$, which gives a concrete point at which the noise budget should bind.

Metrics are final energy error, gradient variance as a function of $n$ with the fitted decay form, gate count and depth, and the number of checker calls and wall-clock time to the first certified family. For each output we also record its classical-simulation status and how often the large-$n$ falsifier overturns a small-$n$ certificate.

Three checks decide the outcome. First, on noisy H₂O and noisy MaxCut, the loop must beat AntiBP's energy gap at matched evaluations, or fall short of it, which would answer the main question either way. Second, the full loop must certify families with substantially fewer checker calls than the untyped and information-free ablations. Third, on MaxCut with increasing noise rate, the loop should switch from algebraic counterexamples to noise counterexamples and produce shallower families as noise grows. That switch would be the first automated separation of expressivity-driven plateaus from noise-driven ones. If the falsifier frequently overturns small-$n$ certificates, the soundness of size-indexed CEGIS for this problem is in doubt, and that negative result is itself worth publishing.