⚛️ quantum physics

AG-CoT: Verified Algorithmic Traces for LLM Program Synthesis on Clifford Circuits

This paper demonstrates that training language models on verified Aaronson-Gottesman chain-of-thought traces, combined with verifier-filtered continuation training, significantly improves the accuracy of synthesizing correct Clifford circuits for quantum error correction compared to circuit-only baselines.

Original authors: Lu Wei, Yufeng Wang, Chenfeng Cao, Lu Pang, Haibin Ling

Published 2026-09-29

📖 4 min read🧠 Deep dive

CC BY 4.0

Original authors: Lu Wei, Yufeng Wang, Chenfeng Cao, Lu Pang, Haibin Ling

Original paper licensed under CC BY 4.0 (http://creativecommons.org/licenses/by/4.0/). ✨ This is an AI-generated explanation of the paper below. It is not written or endorsed by the authors. For technical accuracy, refer to the original paper. Read full disclaimer

In the emerging field of quantum computing, scientists are learning to build machines that operate on the strange rules of the subatomic world. To make these machines work, researchers must write software—called quantum circuits—that manipulates tiny units of information to reach a specific, desired outcome. Think of a quantum circuit as a set of instructions that guides a particle from a starting point to a precise destination. The challenge is that these instructions are incredibly fragile; a single wrong step can send the particle to the wrong place, rendering the entire calculation useless. For years, computer scientists have tried to teach artificial intelligence to write these circuits automatically, hoping that machines could learn to design the complex logic required for quantum experiments. However, a major hurdle has remained: an AI can often produce code that looks perfectly correct on the surface, follows all the grammatical rules of the programming language, and even runs without crashing, yet still fails to prepare the exact quantum state needed. The code is valid, but the result is wrong.

A new study tackles this specific problem by focusing on a particular type of quantum circuit known as a Clifford circuit. These circuits are special because they are powerful enough to be useful for error correction and other critical tasks, yet they possess a unique mathematical property that allows them to be checked with perfect precision on a standard computer. Unlike most quantum simulations, which require tracking an impossible number of possibilities, these circuits can be verified exactly and quickly. The researchers used this advantage to create a training system for large language models. Instead of simply asking the AI to guess the final code, they taught it to show its work. The system required the AI to generate a step-by-step logical trace—a chain of reasoning that explains how to transform the starting state into the target state—before it was allowed to write the final program. This trace was then checked by a strict verifier, a digital referee that confirmed whether the logic was sound and whether the resulting circuit actually prepared the correct quantum state. Only the examples where the AI got the logic right and the final result correct were kept to teach the model further.

The results of this approach were striking. When the researchers tested the AI on thousands of different quantum targets, the models that learned with these verified, step-by-step traces performed dramatically better than those trained only on the final code. For one of the models tested, the number of correct solutions jumped from a mere handful to over two hundred out of the same set of problems. In another model family, the success rate increased from less than two percent to nearly nine percent. The study found that simply showing the AI the final answer was not enough; the AI needed to understand the intermediate steps of the transformation to get it right. Furthermore, the researchers discovered that even when the AI produced code that was grammatically perfect and physically valid, it often still prepared the wrong quantum state. This gap between a valid program and a correct result is a critical insight, proving that checking the syntax of code is insufficient for quantum tasks. The most successful models were those that learned from the verified traces and were then further refined by being trained only on their own successful attempts, creating a cycle of improvement driven by exact verification.

The researchers also explored whether this method could scale to much larger, more powerful AI models. They found that while these larger models could almost perfectly write code that followed the rules and remained within the valid family of quantum circuits, they still struggled to hit the exact target state without the specific guidance of the trace-based training. Even with the most advanced models, the success rate for preparing the exact state remained relatively low, hovering around six percent for single attempts. However, when the researchers allowed the model to generate many different candidates for each problem and used the verifier to pick the best one, the coverage of correct solutions improved significantly. This suggests that while the AI is getting better at the mechanics of writing quantum code, the true difficulty lies in the deep semantic understanding required to ensure the code does exactly what is intended. The study concludes that for AI to become a reliable partner in designing quantum experiments, it must be trained not just to produce code, but to produce code that has been rigorously verified to be correct in its outcome, bridging the gap between a program that runs and a program that works.

Technical Summary: AG-COT: Verified Algorithmic Traces for LLM Program Synthesis on Clifford Circuits

1. Problem Statement

The paper addresses a critical gap in scientific code generation: the ability of Large Language Models (LLMs) to produce syntactically valid and executable programs that nonetheless fail to compute the intended scientific object. While execution-based benchmarks have shifted evaluation toward behavioral correctness, quantum program synthesis presents a unique challenge where a circuit can parse, execute, and remain physically valid (e.g., Clifford-valid) yet prepare the wrong quantum state.

The authors focus on Clifford circuits, which are constructed from Hadamard, phase, and CNOT gates. These circuits are significant because they:

Prepare stabilizer states, which are essential for quantum error correction and measurement-based quantum computation.
Admit exact classical verification via the Aaronson–Gottesman algorithm, allowing for efficient simulation without tracking $2^n$ amplitudes.
Serve as a controlled setting to test whether supervising the derivation process (algorithmic traces) and training on verified outputs improves semantic correctness beyond simple code generation.

Previous benchmarks, such as QCircuitBench, showed that even state-of-the-art models (including GPT-4o) achieved near-zero fidelity on Clifford state preparation tasks using standard prompting, highlighting the difficulty of the task.

2. Methodology

The proposed framework, AG-COT, integrates exact verification into the training loop through two primary mechanisms: Algorithmic Trace Supervision and Verifier-Filtered Continuation.

2.1 Target Representation and Verification

Instead of using full state vectors (which are exponentially large), targets are represented as compact signed stabilizer generators. This reduces prompt length significantly (e.g., from ~16K characters for a 12-qubit state vector to ~800 characters for the tableau).

The Verifier: An ordered decision chain checks:
1. Syntax Validity ( $P(y)$ ): Does the output parse as OpenQASM?
2. Clifford Validity ( $K(y)$ ): Can the parsed circuit be converted to a Qiskit Clifford object?
3. Exact Match:
  - Strict Label Match: Checks if the generated stabilizer labels match the target labels exactly.
  - State Equivalence ($StateEq$): Checks if the generated state is equivalent to the target state, ignoring generator basis differences.

2.2 Training Pipeline

The training process involves two distinct stages:

AG-CoT Supervision (Algorithmic Trace):
- Instead of training only on the final OpenQASM circuit, the model is supervised with Aaronson–Gottesman (AG) chain-of-thought traces.
- These traces consist of deterministic tableau-reduction steps that, when inverted, yield the correct preparation circuit.
- The training data pairs the target prompt with a <think> block containing the reduction trace, followed by the final OpenQASM program.
- Construction: For the 32B study, traces are derived from reference circuits. For the 3B/7B studies, traces are constructed directly from signed stabilizer generators by completing the tableau, applying reduction, inverting the steps, and compiling to the allowed gate set.
- Only pairs where the verifier accepts the final circuit are included in the training set.
Verifier-Filtered Continuation (Rejection Sampling Fine-Tuning - RFT):
- After initial AG-CoT training, the model generates its own outputs.
- The verifier filters these generations, retaining only those that pass the exact state equivalence check.
- The model undergoes further supervised fine-tuning on this filtered set of its own successful generations.

2.3 Experimental Setup

Models: Experiments were conducted on Qwen2.5-3B-Instruct, Mistral-7B-Instruct-v0.3, and Qwen2.5-Coder-32B-Instruct.
Baselines: Compared against Direct SFT (circuit-only supervision) and Zero-shot baselines.
Metrics: Evaluated on syntax validity, Clifford validity, strict label matching, state equivalence, and Pass@N (search coverage).

3. Key Contributions

Algorithmic Trace Supervision: The paper demonstrates that supervising models with verifier-checked AG-CoT traces significantly improves semantic correctness. This approach pairs the emitted circuit with the specific reduction steps that produced it, teaching the model the synthesis procedure rather than just the output format.
Verifier-Filtered Continuation: The authors show that continuing training on the model's own verifier-accepted outputs provides a consistent, albeit smaller, gain over the trace-supervised baseline.
Compact Target Representation: The work establishes a pipeline where targets are specified via signed stabilizer generators, enabling exact verification and reducing prompt overhead while maintaining full semantic precision.
Comprehensive Evaluation: The study separates syntax validity, Clifford validity, and state equivalence to demonstrate that valid quantum code often fails to prepare the correct state, confirming the necessity of exact verification.

4. Results

4.1 Controlled Comparisons (3B and 7B Models)

On a held-out set of 3,661 targets:

Qwen2.5-3B:
- Direct SFT achieved 0.90% task success (33/3,661).
- AG-CoT SFT increased success to 5.49% (201/3,661), a 4.59 percentage point gain.
- Verifier-filtered RFT versions achieved 5.74%–5.87% (210–215 successes).
Mistral-7B:
- Direct SFT achieved 1.94% (71/3,661).
- AG-CoT SFT increased success to 8.63% (316/3,661), a 6.69 percentage point gain.
- RFT achieved 8.80% (322/3,661).
Statistical Significance: McNemar tests confirmed that the gains from AG-CoT supervision over Direct SFT are highly statistically significant ( $p < 10^{-48}$ for Qwen, $p < 10^{-72}$ for Mistral). The gains from RFT were smaller and less uniformly significant.

4.2 32B Study

Syntax and Validity: Supervised models achieved near-perfect syntax and Clifford validity (~99.9%), whereas Zero-shot models struggled (<40%).
State Equivalence: Despite high validity, the strongest direct model (RFT-v1) achieved only 6.14% state equivalence.
Search Coverage: Using verifier-guided selection with 64 candidates per target (Best-of-64), the coverage for Basic AG-CoT rose to 10.07% under state equivalence, demonstrating that search can recover more correct circuits than single-output generation.
Error Analysis: Trace-trained models produced errors with lower "constraint deficits" (fewer missing independent target constraints) compared to circuit-only models, suggesting they retain more target information even when failing.

5. Significance and Claims

The paper claims that algorithmic trace supervision and verifier-filtered continuation are effective, complementary strategies for improving the semantic correctness of LLMs in scientific code synthesis.

Necessity of Exact Verification: The persistent gap between Clifford validity (syntax/physics) and state equivalence (semantic correctness) confirms that syntactic validity is insufficient. A circuit can be physically valid yet prepare the wrong state; therefore, exact verification is necessary for training signals.
Value of Derivation: Supervising the derivation (the AG-CoT trace) alongside the final output yields substantial gains over supervising the output alone. This suggests that LLMs benefit from learning the intermediate reasoning steps of the synthesis algorithm.
Scalability: The methods show consistent improvements across different model families (3B, 7B, 32B), though the absolute success rates remain modest (single digits), indicating that while the approach is effective, the task of quantum circuit synthesis remains challenging for current LLMs.

The authors conclude that these results support the use of algorithmic supervision and verifier-filtered data as a path toward more reliable scientific code generation, particularly in domains where exact verification is computationally feasible.