Matchgate synthesis via Clifford matchgates and T gates

Abstract: Matchgate unitaries are fundamental to quantum computation due to their relation to non-interacting fermions and their utility in benchmarking quantum hardware. In fault-tolerant settings, general unitaries must be decomposed into discrete sets compatible with error-correction primitives, typically the Clifford+T gate set. Here, we propose an alternative paradigm: compiling matchgates using only matchgates. By leveraging the correspondence between n-qubit matchgate circuits and the standard representation of SO(2n), we reduce the compilation task from 2^n times 2^n unitaries to 2n times 2n matrices, achieving an exponential reduction in dimensionality. Our first result identifies a discrete gate set that densely generates the matchgate group. We then address approximate synthesis, rigorously showing that approximation errors in the SO(2n) representation propagate only linearly into the full unitary representation. Finally, we characterize exact synthesis, demonstrating that matchgates meeting specific algebraic conditions can be exactly synthesized without ancilla qubits. This allows us to frame optimal synthesis as a Boolean satisfiability (SAT) problem, enabling the construction of circuits with provable guarantees on depth.