arXiv:2610.06768
Complexity separations for optimal matchgate-Clifford synthesis
Berta Casas, Diego García-Martín, Yuxuan Zhang
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.
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