PaperlayerView exact revision on arXiv

Source-linked AI summary

Fast stabilizer state preparation via AI-optimized graph decimation

Michael Doherty, Matteo Puviani, Jasmine Brewer, Gabriel Matos, David Amaro, Ben Criger, David T. Stephen

arXiv:2603.17743v1quant-ph

TL;DR

Efficient stabilizer-state preparation requires reducing two-qubit resources under gate-error and decoherence constraints. The paper represents stabilizer states as graph states and uses graph decimation with heuristic search, reinforcement learning, and Monte Carlo tree search, including QuSynth. The methods reduce two-qubit gate counts substantially, including a factor-of-2.5 reduction for the 144-qubit Gross code while retaining low circuit depth.

  • Problem

    Stabilizer-state preparation must reduce two-qubit gate count and depth because gate errors and decoherence constrain quantum applications, while prior related AI synthesis methods were limited to about 20 qubits.

  • Method

    The paper converts stabilizer-state synthesis into graph decimation and selects two-qubit Clifford operations using heuristic search, reinforcement learning, and Monte Carlo tree search through QuSynth.

  • Results

    Up to a factor of 2.5 reduction in two-qubit gate count is achieved for the 144-qubit Gross code versus LC-optimization, while matching or improving prior results across the evaluated codes.

  • Takeaways & Limitations

    The approach provides a scalable route to low-gate-count stabilizer-state circuits, reaching code sizes up to 144 qubits beyond prior optimal synthesis access.

Abstract

from arXiv · show

We propose a general method for preparing stabilizer states with reduced two-qubit gate count and depth compared to the state of the art. The method starts from a graph state representation of the stabilizer state and iteratively reduces the number of edges in the graph using two-qubit Clifford gates to produce a unitary preparation circuit. We explore various heuristic search and AI-based approaches to optimally choose Clifford gates at each step, the most sophisticated of which is a combination of reinforcement learning and Monte Carlo tree search that we call QuSynth. We apply our method to synthesize code states of various quantum error correcting codes including the 23-qubit Golay code and the 144-qubit gross code, the latter of which is significantly beyond the qubit number that is accessible to prior optimal circuit synthesis methods. We demonstrate that our techniques are capable of reducing the required two-qubit gates by up to a factor of 2.5 compared to previous approaches while retaining low circuit depth.

I. INTRODUCTION

The paper frames efficient stabilizer-state preparation as a resource-critical problem and introduces graph-decimation methods that combine graph-state representations with heuristic and AI search. QuSynth uses reinforcement learning with Monte Carlo tree search and scales to large code states, including the 144-qubit Gross code.

  • Motivation: Stabilizer-state preparation supports quantum algorithms, networking, measurement-based computation, and quantum error correction, while gate count and depth constrain performance.The paper emphasizes these metrics because gate errors and decoherence impose resource constraints.
  • Research gap: Prior heuristic and reinforcement-learning approaches to related synthesis problems were generally restricted to systems of about 20 qubits.The stated comparison motivates methods that can handle substantially larger systems.
  • Graph-state reduction: Every stabilizer state is locally Clifford-equivalent to a graph state, allowing graph-state preparation methods to prepare arbitrary stabilizer states with the same two-qubit gate count and depth.Local Clifford decorators can be applied after preparing the corresponding graph state.
  • Graph-state reduction: Graph decimation converts circuit synthesis into sequential graph decisions, enabling best-first, beam, and Monte Carlo tree search.The approach iteratively changes graph representations while selecting two-qubit Clifford operations.
  • AI-based synthesis: QuSynth combines reinforcement learning with Monte Carlo tree search to seek low two-qubit gate count, depth, and scalability for stabilizer-state preparation.The paper also evaluates classical heuristic searches as faster alternatives with similar solution quality.

A. Graph state preparation circuits

The preparation circuit begins with a graph state and replaces edge-by-edge CZ construction with sequences of CX, CY, and CZ gates whose induced graph actions can reduce gate count and depth. Examples show fewer gates than LC-only optimization, while CX gates can also improve connectivity and scaling for suitable graphs.

  • Baseline preparation: A naïve graph-state circuit initializes qubits, applies Hadamards, applies CZ gates for every graph edge, and then applies local Clifford gates.Its two-qubit gate count equals the graph edge count |E|.
  • Baseline preparation: The baseline circuit has two-qubit depth at most δ+1, where δ is the graph’s maximum degree, because the CZ gates commute.The maximum degree equals the largest number of two-qubit gates acting on one qubit.
  • Two-qubit Clifford transformations: A CX gate can replace multiple CZ gates by complementing edges between its control and the target’s neighborhood.When the neighborhood contains multiple qubits, one CX can reduce the required two-qubit gate count relative to CZ-only construction.
  • Two-qubit Clifford transformations: CX, CY, and CZ sequences can synthesize graph states with fewer two-qubit gates than LC optimization alone.The method searches for gate sequences that generate the necessary edges while exploiting induced graph transformations.
  • Illustrative example: The example reaches 8 gates with CX and 7 gates with CY, versus a minimum LC-orbit edge count of 9.Both circuits prepare the same graph state shown in Figure 2.
  • Connectivity and depth: For star graphs, CX gates can use nearest-neighbor interactions or achieve logarithmic depth, improving connectivity and depth relative to CZ-only preparation.The star graph is locally Clifford-equivalent to a GHZ state.

B. Graph decimation

Graph decimation reframes stabilizer-state preparation as sequentially applying two-qubit gates until the graph is fully disconnected, then reversing the sequence to obtain a preparation circuit. Because gate effects depend nonlinearly on the evolving graph and exhaustive search is enormous, efficient search is essential.

  • Graph decimation: Graph decimation seeks a minimal gate sequence that disconnects a graph, whose reversed sequence prepares the target graph state from |+⟩ states.The terminal graph has no edges.
  • Sequential decision process: Each action applies a two-qubit gate that can disconnect or reconnect nodes, while edge count measures progress toward the terminal state.The graph representation also ranks possible gates at each step.
  • Algorithmic direction: Reversing graph decimation gives the algorithms powerful gates early, such as CX or CY gates targeting high-degree nodes.On a 4-cycle, an advantageous CX can remove two edges before remaining CZ gates clean up the graph.
  • Search challenge: Graph-decimation effects are highly nonlinear because each gate’s outcome depends on the current graph produced by earlier actions.A locally best edge-removing action can therefore be globally suboptimal.
  • Search challenge: The exhaustive action space scales as O(N_Q^2M), reaching approximately 10^136 possibilities for the 23-qubit Golay code.This makes efficient search and optimization necessary even for relatively small codes.

III. HEURISTIC SEARCH METHODS

The paper benchmarks heuristic search methods for graph decimation before introducing reinforcement-learning approaches. Best-first search greedily selects one state using a score, while its beam-search generalization retains multiple states to trade complexity for accuracy.

  • Motivation: Heuristic search is benchmarked because exhaustive optimization is infeasible even for small codes.The paper uses these methods as a baseline before presenting reinforcement learning.
  • Best-first search: Best-first search evaluates all possible actions and repeatedly selects the next state using a heuristic score.The score combines edges removed with a penalty when an action adds a circuit layer.
  • Best-first search: Because equal immediate scores can lead to different final gate counts, the heuristic must distinguish actions by their downstream possibilities.This motivates retaining alternatives rather than committing solely to the locally highest-scoring action.
  • Beam search: Beam search generalizes best-first search by retaining multiple states at each step, trading increased complexity for improved accuracy.Its beam width determines how many candidate states survive each iteration.

B. Beam search

Beam search preserves multiple graph-decimation trajectories, while Monte Carlo tree search expands promising states and propagates simulated values through a search tree. The methods support broader exploration of globally useful actions but incur computational or memory costs.

  • Beam search: Beam search retains the top N_S states, expands each with N_A sampled actions, and keeps the best N_S resulting states.The search therefore explores multiple trajectories rather than committing to one state per step.
  • Beam search: Beam search can explore locally suboptimal states that yield better cumulative solutions, while random action sampling can exclude locally optimal but globally suboptimal actions.These two mechanisms increase exploration of the state space.
  • Beam-search trade-offs: Beam search has memory complexity O(N_SN_A) and time complexity O(N_SN_AM) because it maintains many intermediate states.The implementation is nevertheless straightforward to parallelize.
  • Monte Carlo tree search: Monte Carlo tree search iterates through selection, expansion, simulation, and backup to focus computation on promising regions of the search space.Simulations estimate node values, and backup updates scores and visit counts along preceding paths.
  • Monte Carlo tree search: UCT balances exploitation of high-quality states against exploration of under-visited states using average reward, priors, visit counts, and a nonnegative coefficient c.Small c favors exploitation, whereas large c favors exploration.
  • Monte Carlo tree search: The implementation evaluates k promising states and m new actions in parallel, updating batches of k·m states for more efficient computation.This batching adapts the sequential tree-search procedure to GPU-oriented computation.

B. Reinforcement Learning framework

The reinforcement-learning framework treats graph decimation as sequential decision-making, learning action choices from graph observations and rewards. QuSynth adds tree-search planning, generally improving solution optimality but requiring substantially more computation than model-free reinforcement learning.

  • RL formulation: Reinforcement learning learns a policy that selects actions from state observations to maximize future rewards.The agent also predicts intermediate-state values before the terminal result is known.
  • State observations: The agents observe the adjacency matrix and additional action-related features that differ between model-free and MCTS-guided reinforcement learning.Model-free RL includes current-layer qubits, whereas MCTS-guided RL includes edges removed by actions.
  • Action space: Action masking removes choices that do not remove at least one edge, reducing the action space and ensuring that episodes terminate.The reduction is nearly an order of magnitude for some codes.
  • RL trade-off: MCTS-guided reinforcement learning generally finds more optimal solutions than model-free reinforcement learning but uses substantially more computational resources.Model-free RL benefits from JAX-based GPU parallelization, whereas MCTS provides more lookahead but is less amenable to massive parallelization.

1. Model-free reinforcement learning

The paper develops model-free reinforcement learning and QuSynth, which combines reinforcement learning with Monte Carlo tree search to choose graph-state actions. These methods train agents from graph observations, rewards, predicted scores, and search policies.

  • Model-free reinforcement learning: Model-free reinforcement learning agents observe graph states, choose actions, update the states, and use rewards for training.The training loop treats graph-state evolution as sequential decision making.
  • Model-free reinforcement learning: PPO trains the model-free agent using value, policy, and entropy losses.The value loss fits empirical returns, the policy loss favors advantageous actions, and entropy encourages exploration.
  • QuSynth: QuSynth uses agent predictions to guide Monte Carlo tree search, selects the most visited action, and repeats until the final graph state.Unlike traditional MCTS, the agent predicts new-state values and action priors, removing the random simulation phase.
  • Limitations: The RL approach requires training a separate agent for each code, while behavior-cloned generalist agents did not generalize to unseen codes.The generalist agent nevertheless provides a basis for future work.
  • QuSynth: At episode termination, intermediate states receive scores based on remaining actions, while the agent learns state scores and MCTS policies.Its loss combines mean-squared-error, cross-entropy, and KL-divergence terms, with the reference policy stabilizing updates.

V. RESULTS

The study evaluates graph decimation and QuSynth for preparing logical stabilizer states across codes from 9 to 144 qubits. The methods match or improve prior results, with especially strong gains for the Golay and Gross codes, while exposing tradeoffs between solution quality, depth, and computational cost.

  • Evaluation scope: The evaluation covers CSS and non-CSS error-correcting codes ranging from 9 to 144 qubits, using graph states generated from arbitrary stabilizer states.For CSS states, the initial graphs are bipartite, allowing the resulting circuits to be rewritten with CX gates on initial |0⟩ and |+⟩ states.
  • Gate-count and depth results: All methods match or significantly improve existing state-of-the-art results across the evaluated codes.For smaller codes, the comparison uses optimal SAT circuits when available; larger-code baselines use LC-optimized Stim graphs.
  • Gate-count and depth results: 11 gates (∼20%) are removed from the best-known Golay-code count by beam search and model-free RL, while preserving circuit depth; QuSynth removes one additional gate.The comparison is against the cited state-of-the-art Golay circuit.
  • Gate-count and depth results: A factor of 2.5 reduction is achieved for the 144-qubit Gross code relative to LC-optimization, or a factor of 5 relative to the Stim graph representative.The larger-code circuits were optimized for two-qubit gate count, and more aggressive depth constraints may reduce depth at the cost of additional gates.
  • Search behavior: QuSynth finds better large-code solutions by using tree search and multi-step returns to consider longer-horizon effects than greedy search.Beam search can temporarily increase edge count and still reach the target in fewer steps, whereas QuSynth finds an overall better sequence without increasing edges in the illustrated J36, 8, 6K case.
  • Pre-processing: LC-optimization substantially improves larger-code results and can support scaling by reducing the initial number of graph edges.The improvement is smaller for small codes and more significant for larger ones.
  • Computational cost: Method choice involves a quality–resource tradeoff: BeFS is fast for smaller codes, whereas QuSynth is slower per iteration but more sample efficient.Beam search reaches its best solution fastest overall, while reinforcement-learning approaches require longer runtimes.
  • Further applications: Graph decimation also applies to measurement-based quantum computation, Pauli-rotation synthesis, and Clifford circuits and isometries.The Pauli-rotation application uses graph decimation for the Clifford circuit that simultaneously diagonalizes commuting Pauli operators; circuit extraction can likewise be optimized.

B. Fault tolerance

The generated state-preparation circuits are not fault-tolerant because gate faults can spread low-weight errors into high-weight errors. The paper outlines verification, flagging, and entanglement-purification routes for incorporating these circuits into fault-tolerant protocols.

  • Limitation: The generated preparation circuits are not fault-tolerant because faulty gates can spread low-weight errors into high-weight errors.They can nevertheless serve as an initial step in synthesizing fault-tolerant circuits.
  • Verification circuits: Verification circuits detect high-weight errors after preparation through stabilizer checks, enabling postselection or active corrections.The checks are designed by analyzing errors arising from individual two-qubit gate faults.
  • Flagging gadgets: Flagging extends verification by checking for errors during preparation with ancillary qubits before they become undetectable or uncorrectable.This provides intermediate checks rather than only post-preparation checks.
  • Entanglement purification: Entanglement purification can combine several noisy prepared states into one noiseless copy, but correlated errors between copies must be avoided.For the Golay code, permutation symmetries were used to permute qubits of the final prepared state.

Appendix A: Graph State Decimation for CSS States

For CSS states, bipartite graph structure lets greedy decimation produce circuits recast using only CX gates, while action-space restrictions and post-hoc compilation improve tractability and circuit length.

  • CSS graph structure: The greedy circuit for a bipartite graph can be transformed into Hadamard-endpoint circuits containing only CX gates.CZ gates connect the two subsets, while CX gates act within a subset; conjugating one subset by Hadamards yields CX-only form.
  • Search-space reduction: Exhaustive search over M actions is infeasible because the number of circuit combinations scales as N_Q^2M.
  • Search-space reduction: Restricting valid actions to those removing at least one edge substantially reduces the action space.Figure 10 reports possible actions and initial edge counts for stabilizer codes with different physical-qubit requirements.
  • Circuit optimization: Post-hoc compilation replaces selected gate sequences with shorter ones, followed by greedy gate reordering to reduce circuit depth under commutativity constraints.

Appendix D: Solution time comparisons

The appendix compares search and learning methods by throughput, solution time, and generalization. Search methods are faster, while Transformer behavior cloning reproduces demonstrations but does not generalize to unseen codes.

  • Search and RL performance: Beam-search throughput exceeds 60M environment steps per second at its peak but decreases to 4M for the gross code as beam width is reduced for memory.Action masking lowers beam-search throughput by approximately 50% for smaller codes and relatively less for larger codes.
  • Search and RL performance: RL throughput decreases with code size, from over 2M SPS for Golay to 60k SPS for the gross code.
  • Solution time: BeFS finds a Golay solution in less than one second and a gross-code solution in less than 100 seconds, while beam search completes the gross-code search within 300 seconds.RL takes significantly longer than the other methods under the stated hyperparameters.
  • Hybrid search: Policy-guided beam search replaces random action sampling with sampling from a trained RL policy distribution to improve action-sampling efficiency.
  • Transformer generalization: A single Transformer cloned all demonstrations but failed to generalize to unseen codes, with held-out-code circuits equivalent to random guessing.Training on 12/13 demonstrations reduced training loss to zero, while node-label permutation augmentation did not improve evaluation.

Appendix G: Hyperparameters and training dynamics

Beam-search performance depends strongly on beam width, action sampling, and masking, while RL training exhibits characteristic PPO loss dynamics during circuit optimization.

  • Beam-search parameters: Beam search uses beam width NS and per-step action fraction NA, tested across NS from 10 to 10000 and NA from 2% to 100%.
  • Beam-search parameters: 45 gates is the best Golay beam-search solution; using all actions at every iteration never finds it, whereas action masking permits discovery with NA of 2% at sufficient beam width.The search can require locally suboptimal actions to reach a globally better solution.
  • RL training dynamics: RL training begins with value loss dominating, followed by decreasing entropy magnitude as the policy becomes more deterministic.The total loss later becomes negative under entropy dominance, then rises slightly as the policy converges while value loss approaches zero.
  • RL training dynamics: Figure 14 tracks RL loss components and two-qubit gate-count progression for the J64, 12, 8K code.

Appendix H: Example quantum circuits

The appendix gives example stabilizer-code preparation circuits produced by BeFS, beam search, and QuSynth, identifying their entangling-gate types and selected gate counts or depths.

  • BeFS circuits: The smallest-code examples use BeFS and contain Hadamard, CZ, and CX gates, with ending Hadamards movable to the circuit beginning so all two-qubit gates become CX gates.
  • Beam-search circuit: The J19, 1, 5K color-code preparation circuit is obtained with beam search and uses Hadamard, CZ, and CX gates.
  • QuSynth circuits: QuSynth prepares the J23, 1, 7K logical-zero state with 44 two-qubit gates and two-qubit depth 8.
  • QuSynth circuits: QuSynth prepares the J36, 8, 6K logical-zero state with 77 two-qubit gates and total circuit depth 11.
Loading 2603.17743v1…