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.