Clifford circuits play a foundational role in quantum computing, particularly due to their importance in quantum error correction and fault-tolerant logical synthesis. While these circuits can be efficiently simulated and represented as symplectic matrices, standard synthesis methods-such as the Aaronson-Gottesman algorithm-often yield sub-optimal circuits with excessively high gate counts. In this work, we introduce AlphaClifford, a model-based Reinforcement Learning framework powered by Monte Carlo Tree Search, designed to efficiently synthesize Clifford circuits from the fundamental gate set composed of H, S, and CNOT. By modeling the state space through the algebraic properties of the symplectic group, AlphaClifford effectively explores this combinatorial space to minimize overall circuit cost. For unconstrained Clifford optimization, our approach achieves a consistent reduction in both total and two-qubit (CNOT) gate counts compared to state-of-the-art synthesis heuristics, despite operating with a strictly less expressive gate set. Furthermore, we demonstrate the broad applicability of our framework on two additional tasks: hardware-constrained Clifford transpilation, where we outperform existing RL-based compilers, and as a post-synthesis optimization component within a full Clifford+T logical synthesis pipeline. Our results underscore that model-based RL is highly effective at addressing the combinatorial complexities of quantum compilation, offering a scalable pathway to mitigate hardware constraints in both near-term and future fault-tolerant quantum devices.
Figures & tables
Fig. 1 : a) We train our model to reproduce a target symplectic matrix. Each symplectic matrix is modelled as the node of a tree, where nodes are connected if the corresponding matrices can be reached with an operation from H, S, and CNOT. We train a MCTS-based model as a pair of value network (for nodes, e.g. lighter blue corresponds to a higher value) and policy network (for edges, e.g. wider arrows corresponds to higher probabilities). b) Given a target Clifford circuit Ctar , we utilize our model to synthesize a circuit C with the same symplectic matrix, i.e. P⋅C≡Ctar for a suitable Pauli P . We then compute the P from initial circuit, and we apply the corresponding gates to the obtained circuit. c) AlphaClifford can be applied to a variety of tasks, including general Clifford circuits optimization, Clifford transpilation to ensure compatibility with a given hardware connectivity map, and as a component in a pipeline for logical synthesis, from a general initial circuit, to the final approximated version in Clifford+T.
Fig. 2 : Overview of the Monte Carlo Tree Search (MCTS) phases for Clifford circuit synthesis. The search space is explored by iteratively executing four distinct stages: (a) Selection: The tree is traversed from the root (representing the target symplectic matrix C ) to a leaf node. Actions, corresponding to Clifford gates H,S, and CNOT , are chosen by balancing exploration and exploitation using the UCT formula. (b) Expansion: When reaching a leaf node, the tree is expanded by the addition of one or more child nodes, each representing the state resulting from a possible Clifford operation. (c) Simulation: A rollout is performed from the newly expanded node based on the policy network . A sequence of gates is sampled until a terminal state is reached, at which point the evaluation of the value network is computed based on the proximity to the identity matrix. (d) Backpropagation: The reward obtained during simulation is propagated upward to the root, updating the value estimates and visit counts for all nodes along the selected path to refine future selection steps.
Problem Size ( n )
Approach
3
4
5
6
7
Total Gates
Aaronson-Gottesman
19.99
25.89
38.05
51.37
65.61
Qiskit greedy
13.57
23.03
34.75
47.77
62.18
Stim
21.27
36.28
54.70
72.82
96.39
A* (with transv.)
12.97
19.56
26.54
35.04
43.15
TABLE I : Average number of total and 2-Qubit gates for different optimization methods over varying problem sizes. Best results for each n are highlighted in bold.
L Maps
T Maps
3L
4L
5L
4T
5T
6T
Approach
Tot.
CNOT
Tot.
CNOT
Tot.
CNOT
Tot.
CNOT
Tot.
CNOT
Tot.
CNOT
RL-Qiskit 1
14.52
4.91
26.80
10.51
36.95
16.78
26.38
9.60
33.63
15.15
50.85
24.41
RL-Qiskit 10
12.19
4.60
22.90
9.54
33.31
16.08
21.58
8.43
30.92
14.29
46.11
22.74
AlphaClifford 1
9.83
5.15
17.49
10.66
29.07
18.45
16.16
9.51
26.27
16.82
42.35
27.49
AlphaClifford 10
9.81
4.99
17.08
10.08
27.58
17.31
15.76
8.96
25.04
15.56
38.84
25.10
TABLE II: Performance of RL-Qiskit [ 41 ] and AlphaClifford for the transpilation task. Results report average total (Tot.) and CNOT gate counts for L and T connectivity maps. Best values for metric are reported in bold.
Fig. 3 : Hardware connectivity maps utilized for benchmarking: Line graphs (a-c) and T-shape graphs (d-f). Vertices represent physical qubits and edges represent available coupling map connections.
Initial Compiled
Qiskit Transpile
AlphaClifford
n
Clifford (k)
T-count (k)
Clifford (k)
%red
Clifford (k)
%red
Without Pre-compilation
5
1.24
0.76
1.23
0.36
1.21
2.44
10
5.17
3.14
5.16
0.13
5.05
2.39
15
10.27
6.23
10.26
0.09
10.01
2.53
20
20.26
12.28
20.24
0.14
19.76
2.50
TABLE III : Clifford synthesis performance: comparison of Clifford gate counts (in thousands) and reduction percentages relative to the original synthesized circuit. Results are grouped by whether pre-synthesis [ 34 ] was applied.
We consider the problem of synthesizing Clifford quantum circuits for devices with all-to-all qubit connectivity. We approach this task as a reinforcement learning problem in which an agent learns to discover a sequence of elementary Clifford gates that reduces a given symplectic matrix representation of a Clifford circuit to the identity. This formulation permits a simple learning curriculum based on random walks from the identity. We introduce a novel neural network architecture that is equivariant to qubit relabelings of the symplectic matrix representation, and which is size-agnostic, allowing a single learned policy to be applied across different qubit counts without circuit splicing or network reparameterization. On six-qubit Clifford circuits, the largest regime for which optimal references are available, our agent finds circuits within one two-qubit gate of optimality in milliseconds per instance, and finds optimal circuits in 99.2% of instances within seconds per instance. After continued training on ten-qubit instances, the agent scales to unseen Clifford tableaus with up to thirty qubits, including targets generated from circuits with over a thousand Clifford gates, where it achieves lower average two-qubit gate counts than Qiskit's Aaronson-Gottesman and greedy Clifford synthesizers.
Richie Yeung, Aleks Kissinger, Rob Cornish
Department of Computer Science, University of Oxford · Quantinuum · College of Computing and Data Science, Nanyang Technological University, Singapore
Quantum circuit optimization is a central task in Quantum Computing, as current Noisy Intermediate Scale Quantum devices suffer from error propagation that often scales with the number of operations. Among quantum operations, the CNOT gate is of fundamental importance, being the only 2-qubit gate in the universal Clifford+T set. The problem of CNOT gates minimization has been addressed by heuristic algorithms such as the well-known Patel-Markov-Hayes (PMH) for linear reversible synthesis (i.e., CNOT minimization with no topological constraints), and more recently by Reinforcement Learning (RL) based strategies in the more complex case of topology-aware synthesis, where each CNOT can act on a subset of all qubits pairs. In this work we introduce AlphaCNOT, a RL framework based on Monte Carlo Tree Search (MCTS) that address effectively the CNOT minimization problem by modeling it as a planning problem. In contrast to other RL- based solution, our method is model-based, i.e. it can leverage lookahead search to evaluate future trajectories, thus finding more efficient sequences of CNOTs. Our method achieves a reduction of up to 32% in CNOT gate count compared to PMH baseline on linear reversible synthesis, while in the constraint version we report a consistent gate count reduction on a variety of topologies with up to 8 qubits, with respect to state-of-the-art RL-based solutions. Our results suggest the combination of RL with search-based strategies can be applied to different circuit optimization tasks, such as Clifford minimization, thus fostering the transition toward the "quantum utility" era.
Quantum unitary synthesis addresses the problem of translating abstract quantum algorithms into sequences of hardware-executable quantum gates. Solving this task exactly is infeasible in general due to the exponential growth of the underlying combinatorial search space. Existing approaches suffer from misaligned optimization objectives, substantial training costs and limited generalization across different qubit counts. We mitigate these limitations by using supervised learning to approximate the minimum description length of residual unitaries and combining this estimate with stochastic beam search to identify near optimal gate sequences. Our method relies on a lightweight model with zero-shot generalization, substantially reducing training overhead compared to prior baselines. Across multiple benchmarks, we achieve faster wall-clock synthesis times while exceeding state-of-the-art methods in terms of success rate for complex circuits.
Lukas Theißinger, Thore Gerlach, David Berghaus +1
University of Bonn · European Space Agency, Advanced Concepts Team · Fraunhofer IAIS