Optimizing the non-Clifford-count in unitary synthesis using Reinforcement Learning

David Kremer, Ali Javadi-Abhari, Priyanka Mukhopadhyay · 2025

Read Optimizing the non-Clifford-count in unitary synthesis using Reinforcement Learning by David Kremer, Ali Javadi-Abhari, Priyanka Mukhopadhyay (2025) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2509-21709.txt.

Introduction

Quantum circuit synthesis aims to use as few expensive non Clifford gates as possible. David Kremer and 2 co-authors apply reinforcement learning to that optimization in a 2025 paper. Unitaries exactly implementable by Clifford plus T, or Clifford plus CS, gate sets are the targets. Their system uses a channel representation of unitaries. Matrix steps then run fast with integers only.

Pruning heuristics and operator canonicalization reduce search complexity. Sharply larger unitaries are implemented in less time, with better success rates than previous work. Two qubit synthesis achieves close to optimal decompositions for up to a hundred T gates. That is far beyond earlier reinforcement learning results. Non Clifford count optimization matters because those gates dominate fault tolerant quantum computing costs.

Catalog record

CREATORDavid Kremer, Ali Javadi-Abhari, Priyanka Mukhopadhyay
YEAR2025
COLLECTIONPAPERS
FORMATTXT
FILE SIZE77 KB
VERSION1.0
LICENSEhttp://creativecommons.org/licenses/by/4.0/
RIGHTSCC BY
SOURCEarXiv

Source: https://arxiv.org/abs/2509-21709

Browse the full library · About the Tower of Babel

Full text

The opening of the work, from the library's hosted text:

Optimizing the non-Clifford-count in unitary synthesis using Reinforcement Learning David Kremer, Ali Javadi-Abhari, Priyanka Mukhopadhyay Abstract An efficient implementation of unitary operators is important in order to practically realize the computational advantages claimed by quantum algorithms over their classical counterparts. In this paper we study the potential of using reinforcement learning (RL) in order to synthesize quantum circuits, while optimizing the T-count and CS-count, of unitaries that are exactly implementable by the Clifford+T and Clifford+CS gate sets, respectively. In general, the complexity of existing algorithms depend exponentially on the number of qubits and the non-Clifford-count of unitaries. We have designed our RL framework to work with channel representation of unitaries, that enables us to perform matrix operations efficiently, using integers only. We have also incorporated pruning heuristics and a canonicalization of operators, in order to reduce the search complexity. As a result, compared to previous works, we are able to implement significantly larger unitaries, in less time, with much better success rate and improvement factor. Our results for Clifford+T synthesis on two qubits achieve close-to-optimal decompositions for up to 100 T gates, 5 times more than previous RL algorithms and to the best of our knowledge, the largest instances achieved with any method to date. Our RL algorithm is able to recover previously-known optimal linear complexity algorithm for T-count-optimal decomposition of 1 qubit unitaries. For 2-qubit Clifford+CS unitaries, our algorithm achieves a linear complexity, something that could only be accomplished by a previous algorithm using S ​ O ​ ( 6 ) SO(6) representation. 1 Introduction Quantum computers have shown significant potential to outperform classical computers in certain tasks and over the past few decades a lot of research has been done in order to probe the computational advantage of quantum computers in practically relevant problems like factoring [ Sho94 ] , unstructured database search [ Gro96 ] , etc. Efficient implementations of these quantum algorithms are an absolute necessity in order to realize the claimed theoretical advantages in practice. Analogous to its classical counterpart, quantum algorithms are popularly described and implemented with quantum circuits, which consist of a series of elementary operations or gates belonging to a universal set. Most of the known universal gate sets consist of Clifford group gates and at least one non-Clifford gate. Synthesis and optimization of these circuits are important components of quantum compilation process. For a fault-tolerant implementation it is important to optimize the number of non-Clifford gates like T, CS, Toffoli, etc, since their implementation in most error correction schemes incurs significant overhead in terms of the number of physical qubit requirements, ancilla, measurement operations, etc. Further, these extra components or operations, being themselves error-prone, have the probability of increasing the error rate of the overall encoded circuits. Additionally, the minimum number of non-Clifford gates required to implement certain unitaries is a quantifier of difficulty in many algorithms [ BG16 , BSS16 ] that try to classically simulate quantum computation. An n -qubit unitary W can be implemented with a “discrete finite” universal gate set (like Clifford+T, V-basis, Clifford+CS, Clifford+Toffoli), such that the unitary U implemented by the circuit is at most a certain distance from W [ Kit97 , DN06 ] . A unitary is called exactly implementable by a gate set if there exists a quantum circuit with these gates, that implements it (up to some global phase). Otherwise, it is approximately implementable. Unitary synthesis refers to the broad class of problems that aim to generate a quantum circuit for a given unitary, with additional constraints like optimizing the gate-count, depth, T-count, T-depth, etc. The complexity of any algorithm that synthesizes a quantum circuit for a given n -qubit unitary, cannot avoid an exponential dependence on n [ AM19 ] . If we impose additional constraints, like synthesizing a circuit with the minimum number of T gates, then the problem becomes harder. Every existing ”provable algorithm”, for such problems, has an exponential dependence on other factors, like the non-Clifford count i.e. the minimum number of non-Clifford gates required to implement the input unitary. By “provable algorithms” we refer to those algorithms that have rigorous proofs about the optimality of their solution and their complexity [ AMMR13 , GKMR14 , RS16 , MM21 , GMM22a , GMM22b , GRT21 , Muk24a ] . Exploiting some special properties of exactly implementable unitaries ”heuristic algorithms” have been developed [ MM21 , GMM22a , Muk24a ] that have a polynomial dependence on the T-count or CS-count. These are algorithms whose claimed optimality of the solutions and complexity depend on some conjectures that are based on certain observations. Nonetheless, with their significantly lower running time and space requirement, it is possible to implement fairly large unitaries on a personal laptop. There is an entirely different category of algorithms that also aim to optimize quantum circuits, but a crucial difference is the fact that their input is not a unitary, but an already synthesized circuit of the unitary. We refer to these as re-synthesis algorithms [ AMM14 , RLB+24 ] . The quality of their solution depends on the input circuit and no re-synthesis algorithm exists that guarantees an output circuit with the minimum number of T-gates. Their claimed complexity do not account for the cost of synthesizing the input unitary. If we refer to the results of existing papers on re-synthesis algorithms, then we will understand that though these algorithms can be applied to circuits of many qubits, it is practically impossible to synthesize a circuit for an equivalently large unitary by any existing algorithm. Usually, a quantum agorithm or a large unitary is decomposed into smaller unitaries which are synthesized and combined to give the circuit of the larger unitary. If we optimally synthesize these smaller unitaries then we can get better circuits for the larger untiaries. In fact, this can be input to a re-synthesis algorithm and much better overall optimization can be obtained. A small illustration of this fact has been shown in [ MM21 ] . In summary, non-Clifford-optimal quantum circuit synthesis of unitaries is important and of practical significance, especially from a fault-tolerant perspective. But most existing algorithms are constrained by an impractical running time and space requirement, that scales exponentially with n and the T-count. Hence we probe the usefulness of Artificial Intelligence (AI) in solving this problem. AI tools have been crucial in the advance of many scientific disciplines [ DB18 , SLG+19 , DSW+21 , JEP+21 , FBH+22 , MBS+23 , WFD+23 , TWL+24 ] . Recently, techniques of AI have been applied to quantum circuit synthesis and optimization problems [ ABI+19 , RO19 , AS21 , HLZ+21 , FNML21 , Loc21 , MPRP21 , AGO+22 , MZ22 , PSFA23 , QBW23 , FMGB24 , KVP+24 , RDU+24 , RLB+24 , VGS25 ] . Specifically, in this paper we apply reinforcement learning (RL) in order to synthesize quantum circuits for unitaries that are exactly implementable by the Clifford+T and Clifford+CS gate sets, with an aim to optimize the T-count and CS-count, respectively. Both these gate sets are universal, widely used and well-studied. Additionally, fault-tolerant implementations exist for the non-Clifford T, CS gates [ Got97 , CPM+98 , FSG09 , RDN+12 , PR13 , Yod17 , HH18b ,

Read the complete text