Challenges
Datasets
Workspaces
Papers
Discussions
Leaderboard
Log inSign up
Challenges
Datasets
Workspaces
Papers
Discussions
Leaderboard
Blog
Job Board
Q3AS

© 2026 Aqora Quantum S.A.S.

TermsPrivacyLegal Notice

arXiv:2503.20203 · Physical Review A

Synthesis of single-qutrit circuits from Clifford + R gates

Erik Gustafson, Henry Lamm, Diyi Liu, Edison M. Murairi, Shuchen Zhu

Published Nov 14, 2025• 1 citation
arXivHTMLPDF

Abstract

We present two deterministic compilation algorithms for single-qutrit unitaries with $O(log1/\ensuremath{\varepsilon})$ gate depth. Each algorithm selects a nearby approximation to the target unitary and then exactly synthesizes the approximation over the Clifford $+$ $\mathbf{R}$ basis. The first algorithm exhaustively searches over the group; while the second algorithm searches only for Householder reflections. The exhaustive search algorithm yields an average $\mathbf{R}$ count of $2.193(11)+8.621(7){log}_{10}(1/\ensuremath{\varepsilon})$, albeit with a time complexity of $O({\ensuremath{\varepsilon}}^{\ensuremath{-}4.4})$. The Householder search algorithm results in a larger average $\mathbf{R}$ count of $3.20(13)+10.77(3){log}_{10}(1/\ensuremath{\varepsilon})$ at a reduced time complexity of $O({\ensuremath{\varepsilon}}^{\ensuremath{-}0.42})$, greatly extending the reach in $\ensuremath{\varepsilon}$. These costs correspond asymptotically to 35% and 69% more non-Clifford gates compared with synthesizing the same unitary with two qubits. Such initial results are encouraging for using the $\mathbf{R}$ gate as the nontransversal gate for qutrit-based computation.

DOI
10.1103/98q1-3yv8

Related papers

Approximate synthesis of general single-qubit unitaries over the Clifford+$\sqrt{T}$ gate set

Mathias Weiden, Jae Won Kim, Justin Kalloor +2 more

For the standard Clifford+$T$ gate set, deterministic, ancilla-free synthesis now attains the minimal $T$-count for general single-qubit unitaries (Morisaki et al., arXiv:2510.05816). The $\sqrt{T}$ gate rotates by half the angle of $T$, generating a finer lattice of implementable operations. Access to this magic state is expected to lower the cost of deterministic and ancilla-free synthesis of general single-qubit unitaries (Kliuchnikov et al., arXiv:2203.10064), but no direct Clifford+$\sqrt{T}$ algorithm existed for this case. We provide one by extending the integer lattice-point enumeration method of Morisaki et al. We adopt a resource state cost model based on the magic-state catalysis approach of Gidney and Fowler (arXiv:1812.01238). On Haar-random targets synthesized to precisions ranging from $\varepsilon=10^{-3}$ to $10^{-8}$, the cost of Clifford+$\sqrt{T}$ circuits scales as $2.4\log_2(1/\varepsilon)$ compared to $3.0\log_2(1/\varepsilon)$ for $T$-count-optimal Clifford+$T$ circuits. Once a one-time catalyst state is amortized, the Clifford+$\sqrt{T}$ circuits are never costlier than their Clifford+$T$ counterparts.

quant-pharXiv:2609.16659•Sep 16, 2026•0 citations

Optimal ancilla-free Clifford+T synthesis for general single-qubit unitaries

Hayata Morisaki, Sano, Kaoru, Seiseki Akibue

We propose two Clifford+$T$ synthesis algorithms that are optimal with respect to $T$-count. The first algorithm, called deterministic synthesis, approximates any single-qubit unitary by a single-qubit Clifford+$T$ circuit with the minimum $T$-count. The second algorithm, called probabilistic synthesis, approximates any single-qubit unitary by a probabilistic mixture of single-qubit Clifford+$T$ circuits with the minimum $T$-count. For most of single-qubit unitaries, the runtimes of deterministic synthesis and probabilistic synthesis are $\varepsilon^{-1/2 - o(1)}$ and $\varepsilon^{-1/4 - o(1)}$, respectively, for an approximation error $\varepsilon$. Although this complexity is exponential in the input size, we demonstrate that our algorithms run in practical time at $\varepsilon \approx 10^{-15}$ and $\varepsilon \approx 10^{-22}$, respectively. Furthermore, we show that, for most single-qubit unitaries, the deterministic synthesis algorithm requires at most $3\log_2(1/\varepsilon) + o(\log_2(1/\varepsilon))$ $T$-gates, and the probabilistic synthesis algorithm requires at most $1.5\log_2(1/\varepsilon) + o(\log_2(1/\varepsilon))$ $T$-gates. Remarkably, complexity analyses in this work do not rely on any numerical or number-theoretic conjectures.

arXiv:2510.05816•Oct 7, 2025•0 citations

Unitary Synthesis of Clifford+T Circuits with Reinforcement Learning

Sebastian Rietsch, Abhishek Y. Dubey, Christian Ufrecht +4 more

This paper presents a deep reinforcement learning approach for synthesizing unitaries into quantum circuits. Unitary synthesis aims to identify a quantum circuit that represents a given unitary while minimizing circuit depth, total gate count, a specific gate count, or a combination of these factors. While past research has focused predominantly on continuous gate sets, synthesizing unitaries from the parameter-free Clifford+T gate set remains a challenge. Although the time complexity of this task will inevitably remain exponential in the number of qubits for general unitaries, reducing the runtime for simple problem instances still poses a significant challenge. In this study, we apply the tree-search method Gumbel AlphaZero to solve the problem for a subset of exactly synthesizable Clifford+T unitaries. Our method effectively synthesizes circuits for up to five qubits generated from randomized circuits with up to 60 gates, outperforming existing tools like QuantumCircuitOpt and MIN-T-SYNTH in terms of synthesis time for larger qubit counts. Furthermore, it surpasses Synthetiq in successfully synthesizing random, exactly synthesizable unitaries. These results establish a strong baseline for future unitary synthesis algorithms.

arXiv:2404.14865•IEEE International Conference on Quantum Computing and Engineering (QCE)•Sep 15, 2024•9 citations

Clifford+V synthesis for multi-qubit unitary gates

Soichiro Yamazaki, Seiseki Akibue

We developed a general framework for synthesizing target gates by using a finite set of basic gates, which is a crucial step in quantum compilation. When approximating a gate in SU($n$), a naive brute-force search requires a computational complexity of $O(1/\varepsilon^{(n^2 - 1)})$ to achieve an approximation with error $\varepsilon$. In contrast, by using our method, the complexity can be reduced to $O(-n^2 \log\varepsilon/\varepsilon^{((n^2 - 1)/2)})$. This method requires almost no assumptions and can be applied to a variety of gate sets, including Clifford+$T$ and Clifford+$V$. Further, we introduce a suboptimal but short run-time algorithm for synthesizing multi-qubit controlled gates. This approach highlights the role of subgroup structures in reducing synthesis complexity and opens a new direction of study on the compilation of multi-qubit gates. The framework is broadly applicable to different universal gate sets, and our analysis suggests that it can serve as a foundation for resource-efficient quantum compilation in near-term architectures.

arXiv:2510.08312•Oct 9, 2025•0 citations

Matchgate synthesis via Clifford matchgates and TTT gates

Berta Casas, Paolo Braccia, Élie Gouzien +2 more

Matchgate unitaries are ubiquitous in quantum computation due to their relation to non-interacting fermions and because they can be used to benchmark quantum computers. Implementing such unitaries on fault-tolerant devices requires first compiling them into a discrete universal gate set, typically Clifford$+T$. Here, we propose a different approach for their synthesis: compile matchgate unitaries using only matchgate gates. To this end, we first show that the matchgate-Clifford group (the intersection of the matchgate and Clifford groups) plus the $\overline{T}$ gate (a $T$ unitary up to a phase) is universal for the matchgate group. Our approach leverages the connection between $n$-qubit matchgate circuits and the standard representation of $\mathbb{SO}(2n)$, which reduces the compilation from $2^n\times 2^n$ unitaries to $2n\times2n$ ones, thus reducing exponentially the size of the target matrix. Moreover, we rigorously show that this scheme is efficient, as an approximation error $\varepsilon_{\mathbb{SO}(2n)}$ incurred in this smaller-dimensional representation translates at most into an $O(n \,\varepsilon_{\mathbb{SO}(2n)})$ error in the exponentially large unitary. In addition, we study the exact version of the matchgate synthesis problem, and we prove that all matchgate unitaries $U$ such that $U\otimes U^*$ has entries in the ring $\mathbb{Z}\big[1/\sqrt 2,i\big]$ can be exactly synthesized by a finite sequence of gates from the matchgate-Clifford$+\overline{T}$ set, without ancillas. We then use this insight to map optimal exact matchgate synthesis to Boolean satisfiability, and compile the circuits that diagonalize the free-fermionic $XX$ Hamiltonian on $n=4,\,8$ qubits.

quant-pharXiv:2602.05425•Feb 6, 2026•0 citations

High-Precision Multi-Qubit Clifford+T Synthesis by Unitary Diagonalization

Mathias Weiden, Justin Kalloor, John David Kubiatowicz +2 more

Resource-efficient and high-precision approximate synthesis of quantum circuits expressed in the Clifford+T gate set is vital for Fault-Tolerant quantum computing.Efficient optimal methods are known for single-qubit R Z unitaries, otherwise the problem is generally intractable.Search-based methods, like simulated annealing, empirically generate low resource cost approximate implementations of general multi-qubit unitaries so long as low precision (Hilbert-Schmidt distances of ε ≥ 10 -2 ) can be tolerated.These algorithms build up circuits that directly invert target unitaries.We instead leverage search-based methods to first approximately diagonalize a unitary, then perform the inversion analytically.This lets difficult continuous rotations be bypassed and handled in a postprocessing step.Our approach improves both the implementation precision and run time of synthesis algorithms by orders of magnitude when evaluated on unitaries from real quantum algorithms.On benchmarks previously synthesizable only with analytical techniques like the Quantum Shannon Decomposition, diagonalization uses an average of 95% fewer non-Clifford gates.

arXiv:2409.00433•Electronic Proceedings in Theoretical Computer Science•Aug 19, 2025•1 citation
We present two deterministic compilation algorithms for single-qutrit unitaries with O(log1/\ensuremathε)O(log1/\ensuremath{\varepsilon})O(log1/\ensuremathε) gate depth. Each algorithm selects a nearby approximation to the target unitary and then exactly synthesizes the approximation over the Clifford +++ R\mathbf{R}R basis. The first algorithm exhaustively searches over the group; while the second algorithm searches only for Householder reflections. The exhaustive search algorithm yields an average R\mathbf{R}R count of 2.193(11)+8.621(7)log10(1/\ensuremathε)2.193(11)+8.621(7){log}_{10}(1/\ensuremath{\varepsilon})2.193(11)+8.621(7)log10​(1/\ensuremathε), albeit with a time complexity of O(\ensuremathε\ensuremath−4.4)O({\ensuremath{\varepsilon}}^{\ensuremath{-}4.4})O(\ensuremathε\ensuremath−4.4). The Householder search algorithm results in a larger average R\mathbf{R}R count of 3.20(13)+10.77(3)log10(1/\ensuremathε)3.20(13)+10.77(3){log}_{10}(1/\ensuremath{\varepsilon})3.20(13)+10.77(3)log10​(1/\ensuremathε) at a reduced time complexity of O(\ensuremathε\ensuremath−0.42)O({\ensuremath{\varepsilon}}^{\ensuremath{-}0.42})O(\ensuremathε\ensuremath−0.42), greatly extending the reach in \ensuremathε\ensuremath{\varepsilon}\ensuremathε. These costs correspond asymptotically to 35% and 69% more non-Clifford gates compared with synthesizing the same unitary with two qubits. Such initial results are encouraging for using the R\mathbf{R}R gate as the nontransversal gate for qutrit-based computation.
Approximate synthesis of general single-qubit unitaries over the Clifford+T\sqrt{T}T​ gate set
For the standard Clifford+TTT gate set, deterministic, ancilla-free synthesis now attains the minimal TTT-count for general single-qubit unitaries (Morisaki et al., arXiv:2510.05816). The T\sqrt{T}T​ gate rotates by half the angle of TTT, generating a finer lattice of implementable operations. Access to this magic state is expected to lower the cost of deterministic and ancilla-free synthesis of general single-qubit unitaries (Kliuchnikov et al., arXiv:2203.10064), but no direct Clifford+T\sqrt{T}T​ algorithm existed for this case. We provide one by extending the integer lattice-point enumeration method of Morisaki et al. We adopt a resource state cost model based on the magic-state catalysis approach of Gidney and Fowler (arXiv:1812.01238). On Haar-random targets synthesized to precisions ranging from ε=10−3\varepsilon=10^{-3}ε=10−3 to 10−810^{-8}10−8, the cost of Clifford+T\sqrt{T}T​ circuits scales as 2.4log⁡2(1/ε)2.4\log_2(1/\varepsilon)2.4log2​(1/ε) compared to 3.0log⁡2(1/ε)3.0\log_2(1/\varepsilon)3.0log2​(1/ε) for TTT-count-optimal Clifford+TTT circuits. Once a one-time catalyst state is amortized, the Clifford+T\sqrt{T}T​ circuits are never costlier than their Clifford+TTT counterparts.
We propose two Clifford+TTT synthesis algorithms that are optimal with respect to TTT-count. The first algorithm, called deterministic synthesis, approximates any single-qubit unitary by a single-qubit Clifford+TTT circuit with the minimum TTT-count. The second algorithm, called probabilistic synthesis, approximates any single-qubit unitary by a probabilistic mixture of single-qubit Clifford+TTT circuits with the minimum TTT-count. For most of single-qubit unitaries, the runtimes of deterministic synthesis and probabilistic synthesis are ε−1/2−o(1)\varepsilon^{-1/2 - o(1)}ε−1/2−o(1) and ε−1/4−o(1)\varepsilon^{-1/4 - o(1)}ε−1/4−o(1), respectively, for an approximation error ε\varepsilonε. Although this complexity is exponential in the input size, we demonstrate that our algorithms run in practical time at ε≈10−15\varepsilon \approx 10^{-15}ε≈10−15 and ε≈10−22\varepsilon \approx 10^{-22}ε≈10−22, respectively. Furthermore, we show that, for most single-qubit unitaries, the deterministic synthesis algorithm requires at most 3log⁡2(1/ε)+o(log⁡2(1/ε))3\log_2(1/\varepsilon) + o(\log_2(1/\varepsilon))3log2​(1/ε)+o(log2​(1/ε)) TTT-gates, and the probabilistic synthesis algorithm requires at most 1.5log⁡2(1/ε)+o(log⁡2(1/ε))1.5\log_2(1/\varepsilon) + o(\log_2(1/\varepsilon))1.5log2​(1/ε)+o(log2​(1/ε)) TTT-gates. Remarkably, complexity analyses in this work do not rely on any numerical or number-theoretic conjectures.
This paper presents a deep reinforcement learning approach for synthesizing unitaries into quantum circuits. Unitary synthesis aims to identify a quantum circuit that represents a given unitary while minimizing circuit depth, total gate count, a specific gate count, or a combination of these factors. While past research has focused predominantly on continuous gate sets, synthesizing unitaries from the parameter-free Clifford+T gate set remains a challenge. Although the time complexity of this task will inevitably remain exponential in the number of qubits for general unitaries, reducing the runtime for simple problem instances still poses a significant challenge. In this study, we apply the tree-search method Gumbel AlphaZero to solve the problem for a subset of exactly synthesizable Clifford+T unitaries. Our method effectively synthesizes circuits for up to five qubits generated from randomized circuits with up to 60 gates, outperforming existing tools like QuantumCircuitOpt and MIN-T-SYNTH in terms of synthesis time for larger qubit counts. Furthermore, it surpasses Synthetiq in successfully synthesizing random, exactly synthesizable unitaries. These results establish a strong baseline for future unitary synthesis algorithms.
We developed a general framework for synthesizing target gates by using a finite set of basic gates, which is a crucial step in quantum compilation. When approximating a gate in SU(nnn), a naive brute-force search requires a computational complexity of O(1/ε(n2−1))O(1/\varepsilon^{(n^2 - 1)})O(1/ε(n2−1)) to achieve an approximation with error ε\varepsilonε. In contrast, by using our method, the complexity can be reduced to O(−n2log⁡ε/ε((n2−1)/2))O(-n^2 \log\varepsilon/\varepsilon^{((n^2 - 1)/2)})O(−n2logε/ε((n2−1)/2)). This method requires almost no assumptions and can be applied to a variety of gate sets, including Clifford+TTT and Clifford+VVV. Further, we introduce a suboptimal but short run-time algorithm for synthesizing multi-qubit controlled gates. This approach highlights the role of subgroup structures in reducing synthesis complexity and opens a new direction of study on the compilation of multi-qubit gates. The framework is broadly applicable to different universal gate sets, and our analysis suggests that it can serve as a foundation for resource-efficient quantum compilation in near-term architectures.
Matchgate unitaries are ubiquitous in quantum computation due to their relation to non-interacting fermions and because they can be used to benchmark quantum computers. Implementing such unitaries on fault-tolerant devices requires first compiling them into a discrete universal gate set, typically Clifford+T+T+T. Here, we propose a different approach for their synthesis: compile matchgate unitaries using only matchgate gates. To this end, we first show that the matchgate-Clifford group (the intersection of the matchgate and Clifford groups) plus the T‾\overline{T}T gate (a TTT unitary up to a phase) is universal for the matchgate group. Our approach leverages the connection between nnn-qubit matchgate circuits and the standard representation of SO(2n)\mathbb{SO}(2n)SO(2n), which reduces the compilation from 2n×2n2^n\times 2^n2n×2n unitaries to 2n×2n2n\times2n2n×2n ones, thus reducing exponentially the size of the target matrix. Moreover, we rigorously show that this scheme is efficient, as an approximation error εSO(2n)\varepsilon_{\mathbb{SO}(2n)}εSO(2n)​ incurred in this smaller-dimensional representation translates at most into an O(n εSO(2n))O(n \,\varepsilon_{\mathbb{SO}(2n)})O(nεSO(2n)​) error in the exponentially large unitary. In addition, we study the exact version of the matchgate synthesis problem, and we prove that all matchgate unitaries UUU such that U⊗U∗U\otimes U^*U⊗U∗ has entries in the ring Z[1/2,i]\mathbb{Z}\big[1/\sqrt 2,i\big]Z[1/2​,i] can be exactly synthesized by a finite sequence of gates from the matchgate-Clifford+T‾+\overline{T}+T set, without ancillas. We then use this insight to map optimal exact matchgate synthesis to Boolean satisfiability, and compile the circuits that diagonalize the free-fermionic XXXXXX Hamiltonian on n=4, 8n=4,\,8n=4,8 qubits.
Resource-efficient and high-precision approximate synthesis of quantum circuits expressed in the Clifford+T gate set is vital for Fault-Tolerant quantum computing.Efficient optimal methods are known for single-qubit R Z unitaries, otherwise the problem is generally intractable.Search-based methods, like simulated annealing, empirically generate low resource cost approximate implementations of general multi-qubit unitaries so long as low precision (Hilbert-Schmidt distances of ε ≥ 10 -2 ) can be tolerated.These algorithms build up circuits that directly invert target unitaries.We instead leverage search-based methods to first approximately diagonalize a unitary, then perform the inversion analytically.This lets difficult continuous rotations be bypassed and handled in a postprocessing step.Our approach improves both the implementation precision and run time of synthesis algorithms by orders of magnitude when evaluated on unitaries from real quantum algorithms.On benchmarks previously synthesizable only with analytical techniques like the Quantum Shannon Decomposition, diagonalization uses an average of 95% fewer non-Clifford gates.