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:2602.05425

Matchgate synthesis via Clifford matchgates and TTT gates

Berta Casas, Paolo Braccia, Élie Gouzien, M. Cerezo, Diego García-Martín

quant-phSubmitted Feb 5, 2026• Announced Feb 6, 2026• 7 citations
arXivHTMLPDF

Abstract

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.

Comments
18+19 pages, 7 +1 figures

Related papers

Complexity separations for optimal matchgate-Clifford synthesis

Berta Casas, Diego García-Martín, Yuxuan Zhang

Clifford and matchgate circuits are canonical families of classically simulable quantum circuits. Their intersection, the matchgate-Clifford group, plays an important role in randomized fermionic protocols and in matchgate synthesis. Its adjoint action is isomorphic to the group of unit-determinant signed permutations of $2n$ Majorana modes, and we study optimal exact synthesis in this group. That is, given a target unitary and a gate set, output an $n$-qubit circuit implementing the target using the fewest operations. We show that the complexity of this problem strongly depends on the gate set. In particular, we study gate sets consisting of Majorana braids with different connectivity graphs. For path and complete graphs, we prove that the problem is classically solvable in $\mathcal{O}\left(n^2\right)$ time, and we provide explicit gate-optimal compilers. In addition, we prove that when the connectivity graph is a tree, the decision version of the optimal synthesis problem becomes NP-complete. Finally, we benchmark our optimal compiler on chains of up to $n=80$ qubits against those of \texttt{Qiskit} and \texttt{Tket}, obtaining circuits with constant factor improvements $\times2.57$ and $\times2.28$ in the total number of gates, respectively.

quant-pharXiv:2610.06768•Oct 6, 2026•0 citations

Exact synthesis of single-qubit unitaries over Clifford-cyclotomic gate sets

Simon Forest, David Gosset, Vadym Kliuchnikov +1 more

We generalize an efficient exact synthesis algorithm for single-qubit unitaries over the Clifford+T gate set which was presented by Kliuchnikov, Maslov, and Mosca [Quantum Inf. Comput. 13(7,8), 607–630 (2013)]. Their algorithm takes as input an exactly synthesizable single-qubit unitary—one which can be expressed without error as a product of Clifford and T gates—and outputs a sequence of gates which implements it. The algorithm is optimal in the sense that the length of the sequence, measured by the number of T gates, is smallest possible. In this paper, for each positive even integer n, we consider the “Clifford-cyclotomic” gate set consisting of the Clifford group plus a z-rotation by πn. We present an efficient exact synthesis algorithm which outputs a decomposition using the minimum number of πn z-rotations. For the Clifford+T case n = 4, the group of exactly synthesizable unitaries was shown to be equal to the group of unitaries with entries over the ring Z[eiπn,1/2]. We prove that this characterization holds for a handful of other small values of n but the fraction of positive even integers for which it fails to hold is 100%.

arXiv:1501.04944•Journal of Mathematical Physics•Aug 1, 2015•57 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•1 citation

Quantum Compiling Methods for Fault-Tolerant Gate Sets of Dimension Greater than Two

Andrew N. Glaudell

Fault-tolerant gate sets whose generators belong to the Clifford hierarchy form the basis of many protocols for scalable quantum computing architectures. At the beginning of the decade, number-theoretic techniques were employed to analyze circuits over these gate sets on single qubits, providing the basis for a number of state-of-the-art quantum compiling algorithms. In this dissertation, I further this program by employing number-theoretic techniques for higher-dimensional gate sets on both qudit and multi-qubit circuits. First, I introduce canonical forms for single qutrit Clifford+T circuits and prove that every single-qutrit Clifford+T operator admits a unique such canonical form. I show that these canonical forms are T-optimal and describe an algorithm which takes as input a Clifford+T circuit and outputs the canonical form for that operator. The algorithm runs in time linear in the number of gates of the circuit. Our results provide a higher-dimensional generalization of prior work by Matsumoto and Amano who introduced similar canonical forms for single-qubit Clifford+T circuits. Finally, we show that a similar extension of these normal forms to higher dimensions exists, but do not establish uniqueness. Moving to multi-qubit circuits, I provide number-theoretic characterizations for certain restricted Clifford+T circuits by considering unitary matrices over subrings of Z[1/√2, i]. We focus on the subrings Z[1/2], Z[1/√2], Z[1/√−2], and Z[1/2, i], and we prove that unitary matrices with entries in these rings correspond to circuits over well-known universal gate sets. In each case, the desired gate set is obtained by extending the set of classical reversible gates {X, CX, CCX} with an analogue of the Hadamard gate and an optional phase gate. I then establish the existence and uniqueness of a normal form for one of these gate sets, the two-qubit gate set of Clifford+Controlled Phase gate CS. This normal form is optimal in the number of CS gates, making it the first normal form that is non-Clifford optimal for a fault tolerant universal multi-qubit gate set. We provide a synthesis algorithm that runs in a time linear in the gate count and outputs the equivalent normal form. In proving the existence and uniqueness of the normal form, we likewise establish the generators and relations for the two-qubit Clifford+CS group. Finally, we demonstrate that a lower bound of 5 log2 (1/ε) + O(1) CS gates are required to ε-approximate any 4 × 4 unitary matrix. Lastly, using the characterization of circuits over the Clifford+CS gate set and the existence of an optimal normal form, I provide an ancilla-free inexact synthesis algorithm for two-qubit unitaries using the Clifford+SC gate set for Pauli-rotations. These operators require 6 log2 (1/ε) + O(1) CS gates to synthesize in the typical case and 8 log2 (1/ε) + O(1) in the worst case.

•Jan 1, 2019•2 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•9 citations

Synthesis of unitaries with Clifford+T circuits

Vadym Kliuchnikov

We describe a new method for approximating an arbitrary $n$ qubit unitary with precision $\varepsilon$ using a Clifford and T circuit with $O(4^{n}n(\log(1/\varepsilon)+n))$ gates. The method is based on rounding off a unitary to a unitary over the ring $\mathbb{Z}[i,1/\sqrt{2}]$ and employing exact synthesis. We also show that any $n$ qubit unitary over the ring $\mathbb{Z}[i,1/\sqrt{2}]$ with entries of the form $(a+b\sqrt{2}+ic+id\sqrt{2})/2^{k}$ can be exactly synthesized using $O(4^{n}nk)$ Clifford and T gates using two ancillary qubits. This new exact synthesis algorithm is an improvement over the best known exact synthesis method by B. Giles and P. Selinger requiring $O(3^{2^{n}}nk)$ elementary gates.

arXiv:1306.3200•Jun 13, 2013•60 citations
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.
Clifford and matchgate circuits are canonical families of classically simulable quantum circuits. Their intersection, the matchgate-Clifford group, plays an important role in randomized fermionic protocols and in matchgate synthesis. Its adjoint action is isomorphic to the group of unit-determinant signed permutations of 2n2n2n Majorana modes, and we study optimal exact synthesis in this group. That is, given a target unitary and a gate set, output an nnn-qubit circuit implementing the target using the fewest operations. We show that the complexity of this problem strongly depends on the gate set. In particular, we study gate sets consisting of Majorana braids with different connectivity graphs. For path and complete graphs, we prove that the problem is classically solvable in O(n2)\mathcal{O}\left(n^2\right)O(n2) time, and we provide explicit gate-optimal compilers. In addition, we prove that when the connectivity graph is a tree, the decision version of the optimal synthesis problem becomes NP-complete. Finally, we benchmark our optimal compiler on chains of up to n=80n=80n=80 qubits against those of \texttt{Qiskit} and \texttt{Tket}, obtaining circuits with constant factor improvements ×2.57\times2.57×2.57 and ×2.28\times2.28×2.28 in the total number of gates, respectively.
We generalize an efficient exact synthesis algorithm for single-qubit unitaries over the Clifford+T gate set which was presented by Kliuchnikov, Maslov, and Mosca [Quantum Inf. Comput. 13(7,8), 607–630 (2013)]. Their algorithm takes as input an exactly synthesizable single-qubit unitary—one which can be expressed without error as a product of Clifford and T gates—and outputs a sequence of gates which implements it. The algorithm is optimal in the sense that the length of the sequence, measured by the number of T gates, is smallest possible. In this paper, for each positive even integer n, we consider the “Clifford-cyclotomic” gate set consisting of the Clifford group plus a z-rotation by πn. We present an efficient exact synthesis algorithm which outputs a decomposition using the minimum number of πn z-rotations. For the Clifford+T case n = 4, the group of exactly synthesizable unitaries was shown to be equal to the group of unitaries with entries over the ring Z[eiπn,1/2]. We prove that this characterization holds for a handful of other small values of n but the fraction of positive even integers for which it fails to hold is 100%.
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.
Fault-tolerant gate sets whose generators belong to the Clifford hierarchy form the basis of many protocols for scalable quantum computing architectures. At the beginning of the decade, number-theoretic techniques were employed to analyze circuits over these gate sets on single qubits, providing the basis for a number of state-of-the-art quantum compiling algorithms. In this dissertation, I further this program by employing number-theoretic techniques for higher-dimensional gate sets on both qudit and multi-qubit circuits. First, I introduce canonical forms for single qutrit Clifford+T circuits and prove that every single-qutrit Clifford+T operator admits a unique such canonical form. I show that these canonical forms are T-optimal and describe an algorithm which takes as input a Clifford+T circuit and outputs the canonical form for that operator. The algorithm runs in time linear in the number of gates of the circuit. Our results provide a higher-dimensional generalization of prior work by Matsumoto and Amano who introduced similar canonical forms for single-qubit Clifford+T circuits. Finally, we show that a similar extension of these normal forms to higher dimensions exists, but do not establish uniqueness. Moving to multi-qubit circuits, I provide number-theoretic characterizations for certain restricted Clifford+T circuits by considering unitary matrices over subrings of Z[1/√2, i]. We focus on the subrings Z[1/2], Z[1/√2], Z[1/√−2], and Z[1/2, i], and we prove that unitary matrices with entries in these rings correspond to circuits over well-known universal gate sets. In each case, the desired gate set is obtained by extending the set of classical reversible gates {X, CX, CCX} with an analogue of the Hadamard gate and an optional phase gate. I then establish the existence and uniqueness of a normal form for one of these gate sets, the two-qubit gate set of Clifford+Controlled Phase gate CS. This normal form is optimal in the number of CS gates, making it the first normal form that is non-Clifford optimal for a fault tolerant universal multi-qubit gate set. We provide a synthesis algorithm that runs in a time linear in the gate count and outputs the equivalent normal form. In proving the existence and uniqueness of the normal form, we likewise establish the generators and relations for the two-qubit Clifford+CS group. Finally, we demonstrate that a lower bound of 5 log2 (1/ε) + O(1) CS gates are required to ε-approximate any 4 × 4 unitary matrix. Lastly, using the characterization of circuits over the Clifford+CS gate set and the existence of an optimal normal form, I provide an ancilla-free inexact synthesis algorithm for two-qubit unitaries using the Clifford+SC gate set for Pauli-rotations. These operators require 6 log2 (1/ε) + O(1) CS gates to synthesize in the typical case and 8 log2 (1/ε) + O(1) in the worst case.
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.
We describe a new method for approximating an arbitrary nnn qubit unitary with precision ε\varepsilonε using a Clifford and T circuit with O(4nn(log⁡(1/ε)+n))O(4^{n}n(\log(1/\varepsilon)+n))O(4nn(log(1/ε)+n)) gates. The method is based on rounding off a unitary to a unitary over the ring Z[i,1/2]\mathbb{Z}[i,1/\sqrt{2}]Z[i,1/2​] and employing exact synthesis. We also show that any nnn qubit unitary over the ring Z[i,1/2]\mathbb{Z}[i,1/\sqrt{2}]Z[i,1/2​] with entries of the form (a+b2+ic+id2)/2k(a+b\sqrt{2}+ic+id\sqrt{2})/2^{k}(a+b2​+ic+id2​)/2k can be exactly synthesized using O(4nnk)O(4^{n}nk)O(4nnk) Clifford and T gates using two ancillary qubits. This new exact synthesis algorithm is an improvement over the best known exact synthesis method by B. Giles and P. Selinger requiring O(32nnk)O(3^{2^{n}}nk)O(32nnk) elementary gates.