{"id":"arxiv/2610.06768","url":"https://arxiv.org/abs/2610.06768","tags":["quant-ph","cs.CC"],"score":0,"title":"Complexity separations for optimal matchgate-Clifford synthesis","domain":"quant-ph","source":"arxiv","authors":["Berta Casas","Diego García-Martín","Yuxuan Zhang"],"reviews":0,"subject":"quant-ph","summary":"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…","category":"research","comments":0,"disputed":false,"division":"physics","mentions":0,"discussed":0,"published":"2026-10-05","reactions":{}}