Verifying a quantum program that contains a loop, such as a repeat-until-success circuit or a Grover search driven by weak measurements, needs a loop invariant: a description of every quantum state the loop can be in each time it returns to its head. The strongest automated verifier for such programs, AutoQ 2.0, checks these invariants quickly even at 100 qubits, but a human has to write them. On the theory side, quantum Markov chains (state machines whose transitions are quantum operations instead of probabilities) come with exact algorithms that compute the reachable state space, which is the tightest invariant. Those algorithms only work in finite dimensions, and their cost grows with a high power of the dimension, which itself doubles with every qubit. They are therefore usable on 3 to 6 qubits and useless at 50.
We propose to use the exact algorithm as a teacher where it can run, and a language model as a generalizer where it cannot. For each parameterized family of quantum loop programs, exact quantum Markov chain analysis on small instances produces verified reachable-space invariants. A language model is trained on these examples to write symbolic invariants for any instance size, and AutoQ 2.0 checks them at large sizes. The second ingredient, borrowed from data selection for instruction tuning, is a perplexity-based score of how hard an invariant is for the model given the program. We test whether this score predicts which candidate invariants the solver will accept quickly, and use it both to order the training curriculum and to rank candidates before expensive solver calls. In two sentences: exact finite-dimensional analysis supplies correct invariants for small quantum loops, a language model learns to extend them to large instances, and a relative-loss difficulty score decides what the model trains on first and which proposals the solver sees first.
Core Claim
Automated invariant generation for quantum loop programs is an open problem. AutoQ 2.0 verifies OpenQASM 3.0 programs with loops and measurements by representing sets of states as level-synchronized tree automata (compact graph-like encodings of families of state vectors) and discharging checks to Z3, but it leaves invariant generation to the user. Its reported scale, weak-measurement Grover at 100 qubits in about 20 minutes with all repeat-until-success programs verified instantly, assumes a correct human-written invariant. Quokka / InvBench shows that language models proposing invariants inside a "prove-then-use" loop, where a verifier checks each candidate's validity and usefulness in parallel, can speed up classical C verification. It reports a 1.2x speedup on 81 and a 2.0x speedup on 51 of 866 SV-COMP instances. That work is classical only, and it identifies solver timeouts on proposed invariants as the main failure mode.
Our claim is that the gap between the two is not missing language-model capability. It is missing supervision and a sense of which candidates are tractable. Exact quantum Markov chain analysis can supply the supervision on small instances. Reachability Probabilities of Quantum Markov Chains decomposes a finite-dimensional state space into bottom strongly connected components (subspaces the dynamics can enter but never leave) and a transient part, and it computes reachability in $O(n^8)$ for dimension $n$. Termination of nondeterministic quantum programs characterizes termination through reachable spaces and a zero-one law. We claim that a model trained on these exact small-instance invariants, with a difficulty-ordered curriculum, will write invariants that AutoQ 2.0 accepts on instances far beyond the size the teacher can handle.
Research Program
The work has three parts.
Teacher. We implement the reachable-subspace and bottom-component decomposition algorithms for loop programs compiled to quantum Markov chains. We run them on instances of each program family at 2 to 6 qubits, where $n \le 64$ keeps the $O(n^8)$ cost manageable. Each computed reachable subspace is turned into a symbolic description: amplitude patterns over computational basis states with the qubit count as a parameter. We then check that description back against the exact subspace at every small size we computed. Here the finite-dimensional constraint acts as a boundary condition. Everything the teacher certifies depends on compactness and finite matrices, so the training signal exists only in that regime. We explicitly exclude continuous-variable programs, whose invariant theory needs von Neumann algebras, as Jianxin Chen et al. discuss.
Generator. A code language model is fine-tuned on pairs of (program text with size parameter, symbolic invariant written in AutoQ 2.0's automaton specification language). At test time it proposes invariants for unseen sizes and unseen families. Every proposal goes to AutoQ 2.0, using a quantum version of Quokka's prove-then-use loop. Soundness therefore never depends on the model.
Difficulty score. Following the instruction-following difficulty idea of From Quantity to Quality, we score an invariant $I$ for program $P$ as
$$D(I \mid P) = \frac{\mathcal{L}(I \mid P)}{\mathcal{L}(I)},$$
where $\mathcal{L}(I \mid P)$ is the model's average per-token loss on the invariant given the program, and $\mathcal{L}(I)$ is its loss on the invariant alone. A low ratio means the program makes the invariant easy to predict. A ratio near 1 means the program barely helps, so the invariant's structure is not grounded in the program. Following Superfiltering, which found that weak models' relative perplexities transfer to strong ones, we compute $D$ with a small model so scoring is cheap.
$D$ is used twice. During training, examples are ordered from low to high $D$. We cap the hardest examples, because Principled Data Selection for Alignment warns that examples beyond the model's capacity can hurt. At inference, candidates are submitted to the solver in increasing order of $D$.
We treat one cited result as a direct threat. The original IFD paper reports that its pruning degrades in math and code, where models need more data to learn syntax. We therefore do not use $D$ to throw data away. We use it only to order data and candidates, and we test whether it carries information beyond raw likelihood.
Benchmark. We build 30 to 40 parameterized loop-program families in OpenQASM 3.0. They extend AutoQ 2.0's repeat-until-success and weak-measurement Grover programs with quantum walks, amplitude-amplification variants and measurement-controlled loops, each of which can be instantiated at any qubit count. Families are split so that some are never seen during training.
Baselines
Manual invariants. The reference point is AutoQ 2.0 run with the hand-written invariants from its own paper. It sets the best achievable verification time at 100 qubits.
Do-nothing baseline. AutoQ 2.0 is given a trivial invariant (all states). This measures how often a weak invariant already suffices.
Strongest existing method. No reported result was found on Lacuna for automated invariant synthesis on quantum loop programs. The closest competitor is therefore Quokka's method ported directly: a frontier model prompted with the program, AutoQ 2.0's specification grammar and a few examples, with best-of-N sampling and prove-then-use checking. Quokka reports a 22% gain in accelerated instances from best-of-N on SV-COMP. The ported baseline gets the same number of solver calls, the same wall-clock budget per instance, and the same examples, shown in its prompt rather than used for fine-tuning. We beat it if, at matched solver-call budgets, we fully automatically verify substantially more held-out instances at 20 qubits and above.
Symbolic extrapolation. This baseline reads the teacher's exact invariants at 2 to 6 qubits and fits a parameterized template by anti-unification, that is, matching the invariant descriptions across sizes and replacing the parts that differ with the qubit count. It requires no language model. It is the honest test of whether the model adds anything.
Ablations isolating the difficulty score. We replace $D$ with three alternatives: the raw conditional log-probability $\mathcal{L}(I \mid P)$; static program features (qubit count, loop count, non-Clifford gate count) fed to a regression model; and random order.
Why not just…?
Why not just run the exact quantum Markov chain algorithm at full size? Its $O(n^8)$ cost with $n = 2^k$ for $k$ qubits rules this out beyond a handful of qubits. Image Computation for Quantum Transition Systems shows that even tensor-decision-diagram reachability (a compressed tensor-network encoding of states) struggles beyond 20 qubits for Grover, quantum Fourier transform and quantum-walk circuits without careful partition tuning. We will report the teacher's runtime curve directly, so the crossover point is measured rather than asserted.
Why not just prompt a strong model, as Quokka does? This is a real threat. If the prompted model matches the fine-tuned one on held-out families, the teacher is unnecessary. The main comparison settles this at matched budgets. Our expectation of a gap rests on two observations. AutoQ 2.0's specification language is rare in pretraining text. And Quokka's own failures are weak or solver-unfriendly invariants, which exact supervision targets directly.
Why not just extrapolate the small invariants symbolically? For regular families such as GHZ-like or Grover-like loops, template fitting may well work as well as the model. We would report that honestly. The model is justified only if it wins on families whose reachable spaces change shape with size, or on families never seen in training. The experiment is broken out by family type so the answer is visible.
Why not just rank candidates by static program features or raw likelihood? The SilVer results argue against static features. In Automated Verification of Silq Quantum Programs using SMT Solvers, GHZ verified to 8 qubits and Bernstein-Vazirani to 7, but Deutsch-Jozsa timed out at 5. Qubit count did not predict difficulty. For raw likelihood, Mixture-of-Skills argues it confuses surface complexity with real difficulty. The ablations measure both directly. If raw log-probability ranks candidates as well as $D$, we drop $D$.
Proposed Experiments
Experiment 1: the decisive check on the score. We collect all candidate invariants generated during evaluation, each labeled with whether AutoQ 2.0 accepted it and how long that took. We measure how well $D$, raw log-probability and static features each predict acceptance within a fixed timeout, using AUROC, and their rank correlation with solver time. If $D$ does not beat raw log-probability, the perplexity component is cut.
Experiment 2: end-to-end verification. We measure the fraction of held-out instances at 10, 20, 50 and 100 qubits verified with no human input, the median number of solver calls to the first accepted invariant, and wall-clock time relative to AutoQ 2.0 with manual invariants. Results are reported separately for seen families at new sizes and for unseen families.
Experiment 3: curriculum. We fine-tune with three data orderings: by $D$, random, and with the hardest examples first. We measure held-out acceptance rate to check whether the warning from Principled Data Selection for Alignment about overly hard examples applies to formal invariants.
Success criterion. The project succeeds if at least one family class without regular structure is verified automatically at 50 or more qubits, beyond what both the prompted baseline and the symbolic-extrapolation baseline achieve at equal budget.
References
- AutoQ 2.0: From Verification of Quantum Circuits to Verification of Quantum Programs
- InvBench: Can LLMs Accelerate Program Verification with Invariant Synthesis?
- Reachability Probabilities of Quantum Markov Chains
- Termination of nondeterministic quantum programs
- Commutativity of quantum weakest preconditions
- From Quantity to Quality: Boosting LLM Performance with Self-Guided Data Selection for Instruction Tuning
- Superfiltering: Weak-to-Strong Data Filtering for Fast Instruction-Tuning
- Principled Data Selection for Alignment: The Hidden Risks of Difficult Examples
- Image Computation for Quantum Transition Systems
- Automated Verification of Silq Quantum Programs using SMT Solvers
- Mixture-of-Skills: Learning to Optimize Data Usage for Fine-Tuning Large Language Models