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

Complexity separations for optimal matchgate-Clifford synthesis

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

quant-phcs.CCSubmitted Oct 5, 2026• Announced Oct 6, 2026• 0 citations
arXivHTMLPDF

Abstract

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.

AI Summary

The paper studies exact, minimum-gate synthesis in the matchgate–Clifford group, represented up to global phase by determinant-$+1$ signed permutations of $2n$ Majorana modes. Allowed gates are Majorana braids and their inverses along edges of a specified connectivity graph. For path and complete graphs, it gives closed-form optimal gate counts and explicit classical compilers running in $O(n^2)$ time. On a path, the optimum is $\operatorname{inv}(\pi)+2\nu(w)$, where $\nu$ counts negative leading-principal determinants at permutation cut points. With all-to-all connectivity, it is $2n-\kappa(\pi)+d_-(w)$, where $\kappa$ counts permutation cycles and $d_-$ counts cycles with negative determinant; the worst-case optimum is exactly $2n$. Proofs combine potentials giving lower bounds with sorting constructions that choose braid orientations to assign signs. When an arbitrary tree is supplied as input, gate-optimal and depth-optimal decision problems are NP-complete, via token-swapping reductions with a routing-independent sign assignment. A quadratic synthesis bound establishes NP membership, extending completeness to general connected input graphs. For path connectivity, minimum two-qubit count is $\mu(\pi)+2\nu_{\mathrm{even}}(w)$ and can coexist with minimum total count. Computing $\mu$ exactly remains open; constructive bounds $F\leq\mu\leq2F$ give a factor-two approximation. Benchmarks through 80 qubits report fitted total-gate reductions of $2.57\times$ versus Qiskit and $2.28\times$ versus pytket. These use nonuniform, length-$10n$ random-walk targets and optimize total count, not two-qubit count. All-to-all Majorana braids need not be local qubit gates; optimal synthesis for the full matchgate group remains unresolved.

Little sign of AI-generated textAI use disclosed
We acknowledge the use of ChatGPT 5.6 and Claude to prove the main results in the paper and help develop the code used to generate Fig.~\ref{fig:benchmark}.

Written by gpt-6.1-sol from the paper's full text. Automated: it can be wrong.

Comments
20 + 21 pages, 4 + 1 figures

Related papers

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•7 citations

(A Variant of) Clifford Circuit Synthesis is NP-Complete

Luna Lima Keller, Richard Kueng

Optimal circuit synthesis is the problem of finding the shortest-depth circuit representation of a given functionality with respect to a pre-specified elementary gate set. This is a central problem in both quantum and classical hardware design. While the classical version is very well understood -- both in terms of heuristics and rigorous hardness assertions -- much less is known about optimal quantum circuit synthesis. We focus on optimal Clifford circuit synthesis, for which various heuristics are known, e.g. via reduction to 3-SAT. Our main result supplies a matching hardness result: a variant of optimal Clifford synthesis is NP-hard. The proof proceeds in two parts: (i) reduce 3-edge colorability on 3-regular graphs to a circuit synthesis problem that only involves CZ gates, (ii) prove that the availability of additional elementary Clifford gates -- most notably: Hadamard, phase and CNOT -- cannot lead to further improvements of the optimal circuit depth. Our work sharpens the complexity-theoretic understanding of Clifford circuits: simulation and equivalence checking are in P, whereas deciding whether a Clifford unitary admits an implementation within a prescribed depth is NP-complete.

quant-pharXiv:2610.02029•Oct 2, 2026•2 citations

Clifford synthesis is NP-complete

Søren Fuglede Jørgensen

We show that the problem of synthesizing a quantum circuit for a given Clifford operator using at most a specified amount of resources is NP-complete for several resource models of practical interest. Specifically, we study synthesis of a given Clifford operator using single-qubit Clifford gates and two-qubit Clifford gates, with full qubit connectivity and no additional ancilla qubits. With single-qubit gates free and CNOT as the only two-qubit gate, we show that deciding whether a given target admits an implementation using at most a specified number of CNOT gates is NP-complete, and we show that the problem remains NP-complete when any two-qubit Clifford gate is allowed and the budget counts all such gates. Moreover, we show that both results continue to hold when SWAP gates may be inserted for free, and when single-qubit gates are also considered part of the budget. In each case, we build on recent work by Li and Guan and show that there are polynomial-time reductions from Hamiltonian path in grid graphs to these decision problems, using a number of qubits quadratic in the number of grid vertices.

quant-pharXiv:2610.40886•Nov 2, 2026•0 citations

Link-middle-cut lower bounds for Clifford circuit synthesis

Søren Fuglede Jørgensen

Minimizing the number of CNOT gates required to synthesize a Clifford operator is a central problem in quantum circuit optimization. We extend the link--middle--cut (LMC) framework for linear reversible circuits to Clifford operators represented by binary symplectic tableaux. By introducing block-support connectivity graphs and determinantal invariants, we obtain efficiently computable lower bounds on ancilla-free CNOT complexity. We prove that these bounds are tight for qubit permutations: a permutation of $n$ qubits with $k$ cycles requires exactly $3(n-k)$ CNOT gates, even when arbitrary one-qubit Clifford gates are available. We also derive efficiently computable bounds for synthesis up to a permutation of the output qubits, corresponding to free qubit relabeling. Finally, we further demonstrate the utility of the bound by using it as an admissible heuristic for $A^*$-based Clifford synthesis and show that, on benchmark instances, the resulting search can prove optimality beyond what was possible with earlier SAT-based methods, and that it may be used in combination with earlier $A^*$ heuristics to improve the CNOT counts obtained through heuristic search.

quant-pharXiv:2609.16208•Sep 16, 2026•1 citation

Theory of the Matchgate Commutant

Piotr Sierant, Xhek Turkeshi, Poetri Sonya Tarabunga

In quantum information theory and statistical physics, symmetries of multiple copies, or replicas, of a system play a pivotal role. For unitary ensembles, these symmetries are encoded in the replicated commutant: the algebra of operators commuting with the ensemble across $k$ replicas. Determining the commutant is straightforward for the full unitary group, but remains a major obstacle for structured, computationally relevant circuit families. We solve this problem for matchgate circuits, which prepare fermionic Gaussian states on $n$ qubits. Using a Majorana fermion representation, we show that operators coupling different system copies generate the orthogonal Lie algebra $\mathfrak{so}(k)$, endowing the space of invariants with rich and tractable structure. This underlying symmetry decomposes the matchgate commutant into irreducible sectors, which we completely resolve via a Gelfand--Tsetlin construction. We provide an explicit orthonormal basis of the matchgate commutant for all $k$ and $n$, together with a formula for its dimension that grows polynomially in $n$. Furthermore, we characterize the commutant of the Clifford--matchgate subgroup, showing that restricting to signed permutations of Majorana modes yields a commutant that qualitatively diverges from the matchgate case for $k \geq 4$ replicas. Ultimately, our orthonormal basis turns algebraic classification into a working toolbox. Using it, we derive closed-form expressions for matchgate twirling channels and a fermionic analogue of Weingarten calculus, the projector encoding all moments of the Gaussian state orbit, state and unitary frame potentials, the average nonstabilizerness of fermionic Gaussian states, a systematic hierarchy of non-Gaussianity measures, and a fermionic de Finetti theorem.

quant-pharXiv:2603.12392•Mar 16, 2026•34 citations

Matchgate hierarchy: A Clifford-like hierarchy for deterministic gate teleportation in matchgate circuits

Angelos Bampounis, Rui Soares Barbosa, Nadish de Silva

The Clifford hierarchy, introduced by Gottesman and Chuang in 1999, is an increasing sequence of sets of quantum gates crucial to the gate teleportation model for fault-tolerant quantum computation. Gates in the hierarchy can be deterministically implemented, with increasing complexity, via gate teleportation using (adaptive) Clifford circuits with access to magic states. We propose an analogous gate teleportation protocol and a related hierarchy in the context of matchgate circuits, another restricted class of quantum circuits that can be efficiently classically simulated but are promoted to quantum universality via access to `matchgate-magic' states. The protocol deterministically implements any $n$-qubit gate in the hierarchy using adaptive matchgate circuits with magic states, with the level in the hierarchy indicating the required depth of adaptivity and thus number of magic states consumed. It also provides a whole family of novel deterministic matchgate-magic states. We completely characterise the gates in the matchgate hierarchy for two qubits, with the consequence that, in this case, the required number of resource states grows linearly with the target gate's level in the hierarchy. For an arbitrary number of qubits, we propose a characterisation of the matchgate hierarchy by leveraging the fermionic Stone$\unicode{x2013}$von Neumann theorem. It places a polynomial upper bound on the space requirements for representing gates at each level.

arXiv:2410.01887•Oct 2, 2024•4 citations
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.
The paper studies exact, minimum-gate synthesis in the matchgate–Clifford group, represented up to global phase by determinant-+1+1+1 signed permutations of 2n2n2n Majorana modes. Allowed gates are Majorana braids and their inverses along edges of a specified connectivity graph.
For path and complete graphs, it gives closed-form optimal gate counts and explicit classical compilers running in O(n2)O(n^2)O(n2) time. On a path, the optimum is inv⁡(π)+2ν(w)\operatorname{inv}(\pi)+2\nu(w)inv(π)+2ν(w), where ν\nuν counts negative leading-principal determinants at permutation cut points. With all-to-all connectivity, it is 2n−κ(π)+d−(w)2n-\kappa(\pi)+d_-(w)2n−κ(π)+d−​(w), where κ\kappaκ counts permutation cycles and d−d_-d−​ counts cycles with negative determinant; the worst-case optimum is exactly 2n2n2n. Proofs combine potentials giving lower bounds with sorting constructions that choose braid orientations to assign signs.
When an arbitrary tree is supplied as input, gate-optimal and depth-optimal decision problems are NP-complete, via token-swapping reductions with a routing-independent sign assignment. A quadratic synthesis bound establishes NP membership, extending completeness to general connected input graphs.
For path connectivity, minimum two-qubit count is μ(π)+2νeven(w)\mu(\pi)+2\nu_{\mathrm{even}}(w)μ(π)+2νeven​(w) and can coexist with minimum total count. Computing μ\muμ exactly remains open; constructive bounds F≤μ≤2FF\leq\mu\leq2FF≤μ≤2F give a factor-two approximation. Benchmarks through 80 qubits report fitted total-gate reductions of 2.57×2.57\times2.57× versus Qiskit and 2.28×2.28\times2.28× versus pytket. These use nonuniform, length-10n10n10n random-walk targets and optimize total count, not two-qubit count. All-to-all Majorana braids need not be local qubit gates; optimal synthesis for the full matchgate group remains unresolved.
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.
Optimal circuit synthesis is the problem of finding the shortest-depth circuit representation of a given functionality with respect to a pre-specified elementary gate set. This is a central problem in both quantum and classical hardware design. While the classical version is very well understood -- both in terms of heuristics and rigorous hardness assertions -- much less is known about optimal quantum circuit synthesis. We focus on optimal Clifford circuit synthesis, for which various heuristics are known, e.g. via reduction to 3-SAT. Our main result supplies a matching hardness result: a variant of optimal Clifford synthesis is NP-hard. The proof proceeds in two parts: (i) reduce 3-edge colorability on 3-regular graphs to a circuit synthesis problem that only involves CZ gates, (ii) prove that the availability of additional elementary Clifford gates -- most notably: Hadamard, phase and CNOT -- cannot lead to further improvements of the optimal circuit depth. Our work sharpens the complexity-theoretic understanding of Clifford circuits: simulation and equivalence checking are in P, whereas deciding whether a Clifford unitary admits an implementation within a prescribed depth is NP-complete.
We show that the problem of synthesizing a quantum circuit for a given Clifford operator using at most a specified amount of resources is NP-complete for several resource models of practical interest. Specifically, we study synthesis of a given Clifford operator using single-qubit Clifford gates and two-qubit Clifford gates, with full qubit connectivity and no additional ancilla qubits. With single-qubit gates free and CNOT as the only two-qubit gate, we show that deciding whether a given target admits an implementation using at most a specified number of CNOT gates is NP-complete, and we show that the problem remains NP-complete when any two-qubit Clifford gate is allowed and the budget counts all such gates. Moreover, we show that both results continue to hold when SWAP gates may be inserted for free, and when single-qubit gates are also considered part of the budget. In each case, we build on recent work by Li and Guan and show that there are polynomial-time reductions from Hamiltonian path in grid graphs to these decision problems, using a number of qubits quadratic in the number of grid vertices.
Minimizing the number of CNOT gates required to synthesize a Clifford operator is a central problem in quantum circuit optimization. We extend the link--middle--cut (LMC) framework for linear reversible circuits to Clifford operators represented by binary symplectic tableaux. By introducing block-support connectivity graphs and determinantal invariants, we obtain efficiently computable lower bounds on ancilla-free CNOT complexity. We prove that these bounds are tight for qubit permutations: a permutation of nnn qubits with kkk cycles requires exactly 3(n−k)3(n-k)3(n−k) CNOT gates, even when arbitrary one-qubit Clifford gates are available. We also derive efficiently computable bounds for synthesis up to a permutation of the output qubits, corresponding to free qubit relabeling. Finally, we further demonstrate the utility of the bound by using it as an admissible heuristic for A∗A^*A∗-based Clifford synthesis and show that, on benchmark instances, the resulting search can prove optimality beyond what was possible with earlier SAT-based methods, and that it may be used in combination with earlier A∗A^*A∗ heuristics to improve the CNOT counts obtained through heuristic search.
In quantum information theory and statistical physics, symmetries of multiple copies, or replicas, of a system play a pivotal role. For unitary ensembles, these symmetries are encoded in the replicated commutant: the algebra of operators commuting with the ensemble across kkk replicas. Determining the commutant is straightforward for the full unitary group, but remains a major obstacle for structured, computationally relevant circuit families. We solve this problem for matchgate circuits, which prepare fermionic Gaussian states on nnn qubits. Using a Majorana fermion representation, we show that operators coupling different system copies generate the orthogonal Lie algebra so(k)\mathfrak{so}(k)so(k), endowing the space of invariants with rich and tractable structure. This underlying symmetry decomposes the matchgate commutant into irreducible sectors, which we completely resolve via a Gelfand--Tsetlin construction. We provide an explicit orthonormal basis of the matchgate commutant for all kkk and nnn, together with a formula for its dimension that grows polynomially in nnn. Furthermore, we characterize the commutant of the Clifford--matchgate subgroup, showing that restricting to signed permutations of Majorana modes yields a commutant that qualitatively diverges from the matchgate case for k≥4k \geq 4k≥4 replicas. Ultimately, our orthonormal basis turns algebraic classification into a working toolbox. Using it, we derive closed-form expressions for matchgate twirling channels and a fermionic analogue of Weingarten calculus, the projector encoding all moments of the Gaussian state orbit, state and unitary frame potentials, the average nonstabilizerness of fermionic Gaussian states, a systematic hierarchy of non-Gaussianity measures, and a fermionic de Finetti theorem.
The Clifford hierarchy, introduced by Gottesman and Chuang in 1999, is an increasing sequence of sets of quantum gates crucial to the gate teleportation model for fault-tolerant quantum computation. Gates in the hierarchy can be deterministically implemented, with increasing complexity, via gate teleportation using (adaptive) Clifford circuits with access to magic states. We propose an analogous gate teleportation protocol and a related hierarchy in the context of matchgate circuits, another restricted class of quantum circuits that can be efficiently classically simulated but are promoted to quantum universality via access to `matchgate-magic' states. The protocol deterministically implements any nnn-qubit gate in the hierarchy using adaptive matchgate circuits with magic states, with the level in the hierarchy indicating the required depth of adaptivity and thus number of magic states consumed. It also provides a whole family of novel deterministic matchgate-magic states. We completely characterise the gates in the matchgate hierarchy for two qubits, with the consequence that, in this case, the required number of resource states grows linearly with the target gate's level in the hierarchy. For an arbitrary number of qubits, we propose a characterisation of the matchgate hierarchy by leveraging the fermionic Stone$\unicode{x2013}$von Neumann theorem. It places a polynomial upper bound on the space requirements for representing gates at each level.