Complexity separations for optimal matchgate-Clifford synthesis
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 𝒪(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=80 qubits against those of \texttt{Qiskit} and \texttt{Tket}, obtaining circuits with constant factor improvements ×2.57 and ×2.28 in the total number of gates, respectively.
Related
- Near-Optimal Separations of Certificate Complexity from Randomized and Quantum Query Complexity
- Exact Operator Complexity Measures from Random Matchgate Unitaries
- Improved Separations between Quantum and Classical Communication Complexity of Total Functions
- Strong matchgate designs in nearly optimal depth
- EFI Pairs Without One-Way Puzzles: Oracle Separations from Communication Complexity
BibTeX
@misc{casas2026complexity,
title = {{Complexity separations for optimal matchgate-Clifford synthesis}},
author = {Berta Casas and Diego García-Martín and Yuxuan Zhang},
howpublished = {arXiv},
year = {2026},
month = oct,
doi = {10.48550/arxiv.2610.06768},
eprint = {2610.06768},
archivePrefix = {arXiv},
url = {https://arxiv.org/abs/2610.06768},
}
RIS
TY - UNPB
TI - Complexity separations for optimal matchgate-Clifford synthesis
AU - Berta Casas
AU - Diego García-Martín
AU - Yuxuan Zhang
PY - 2026
DA - 2026/10/05
PB - arXiv
DO - 10.48550/arxiv.2610.06768
UR - https://arxiv.org/abs/2610.06768
AB - 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 𝒪(n^2) 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 ×2.57 and ×2.28 in the total number of gates, respectively.
ER -