When is optimal matchgate-Clifford synthesis efficiently solvable?

Connectivity of the gate set decides tractability

The paper asks a narrow, well-posed question: given a target matchgate-Clifford unitary and a gate set made of Majorana braids, can you output an n-qubit circuit using the fewest operations, and how hard is that problem? The answer depends on the connectivity graph of the braids. For path and complete graphs the problem is classically solvable in O(n^2) time, and the authors give explicit gate-optimal compilers. For an arbitrary tree connectivity graph, the decision version becomes NP-complete.

This is a complexity separation, not a single algorithm. The same target group and the same type of generator are used throughout; only the graph along whose edges braids are allowed changes. That is why the result is framed as a statement about how the generating set, and specifically its connectivity, enters the problem.

Why signed permutations replace the unitary matrices

Matchgate-Clifford unitaries are the intersection of the matchgate and Clifford groups. Their adjoint action on the 2n Majorana operators is isomorphic to the group of 2n x 2n signed permutation matrices with determinant +1, written B_2n ∩ SO(2n). Working in this representation avoids the exponential size of the unitary matrices, which is what makes a complexity analysis meaningful.

A gate in the generating set is a Majorana braid, which acts as a signed transposition between two Majoranas joined by an edge of the connectivity graph. The synthesis problem then becomes a word problem: express the target signed permutation as a shortest product of braids along the allowed edges. The decision version asks whether some word of length at most k exists, and it is in NP whenever the optimal length is polynomial in n, because a candidate word can be checked by multiplying matrices.

On a path, the optimal length has a closed form

For nearest-neighbor braids on an open path, the authors use generators built from the single-qubit phase gate S and the two-qubit R_xx(pi/2) gate, which generate the matchgate-Clifford group and are native on some neutral-atom and trapped-ion platforms. The optimal length is given by a potential Phi(w) = inv(pi) + 2 nu(w), where inv(pi) is the inversion number of the underlying permutation and nu(w) counts the negative defects, that is, cut points c with Delta_c(w) = -1.

The inversion term matches the known nearest-neighbor transposition length for unsigned permutations. The extra 2 nu(w) term is the sign-correction cost: because every generator has positive determinant, blocks with determinant -1 cannot be fixed from inside the block, so the algorithm places signs at block boundaries and applies r_c^2 across the cuts. The proof shows a single generator changes Phi(w) by at most one, giving the lower bound, and then supplies an algorithm matching it, giving l_R(w) = Phi(w) in O(n^2) time.

Benchmarks show constant-factor gate-count improvements

The path compiler is benchmarked against four alternatives: a sort-then-fix bubble-sort strategy, a Givens-elimination strategy, and the general-purpose compilers Qiskit and pytket. Targets are matchgate-Clifford circuits generated as random walks of length 10n over the generating set, compiled on chains up to n = 80 qubits.

In total gate count, the optimal compiler produces shorter circuits than all alternatives, with constant-factor improvements ranging from about 1.5 over matchgate-dedicated methods to about 2.6 over general compilers. Against Qiskit and Tket specifically, the abstract reports improvements of x2.57 and x2.28 in total gates. The paper also reports bounds on the minimum number of two-qubit gates and states that a circuit can simultaneously achieve that two-qubit count and the optimal total gate count. These are constant factors, not asymptotic gains, and they are measured on the path connectivity case.

Complete connectivity is also solvable in polynomial time

When the connectivity graph is complete, so that braids between any pair of Majoranas are allowed, the authors again prove classical solvability in O(n^2) time and give a closed-form expression for the optimal word length. The mechanism differs from the path case: the algorithm works by identifying defective cycles and sorting cycles and signs, each iteration increasing the distance to the identity by one. Since the Cayley-graph diameter is 2n, at most 2n such iterations are needed, which yields the O(n^2) bound.

Path and complete graphs therefore sit on the tractable side of the separation, but for different structural reasons. The paper presents them as two separate theorems rather than as one general result, and the closed-form lengths are specific to each connectivity.

Trees inherit hardness from token-swapping routing

For an arbitrary tree connectivity graph supplied as input, the decision version of gate-optimal matchgate-Clifford synthesis is NP-complete. The reduction comes from the routing problem on trees, which asks for the minimum number of swaps along tree edges needed to realize a prescribed permutation of tokens on the vertices and is itself NP-complete.

The gap between routing and synthesis is the signs introduced by Majorana braids. The authors show that for every permutation one can efficiently find a sign configuration such that the minimum braid-sequence length for the resulting signed permutation equals the minimum swap count of the original permutation. Crucially, the sign configuration must be determined from the permutation alone, without knowing an optimal routing. A polynomial upper bound on the synthesis length on trees then places the problem in NP, completing NP-completeness. The same reduction shows that depth-optimal synthesis on trees is NP-complete, and a corollary extends both results to general connected graphs.

What the separation does and does not cover

The tractability results are for exact optimal synthesis within the matchgate-Clifford group under specific fixed connectivities, and the benchmark covers the path case on chains up to n = 80 qubits. The NP-completeness results are for the decision version when the connectivity graph is part of the input, which is a different question from compiling a fixed hardware topology. The paper notes that identifying fixed connectivities admitting efficient optimal synthesis remains open.

The authors also state that the complexity of optimal synthesis for the full matchgate group, exact or approximate, remains unknown, so these results should not be read as settling matchgate compilation in general. The word-length formulas apply to the Majorana-braid generators studied here; standard Coxeter length functions for type B and D groups use different generating sets and do not capture the additional sign-correction term.

Where the practical priority sits

The most decision-relevant split in this paper is between fixed connectivity and input connectivity. If the braid connectivity is a path or complete graph, the optimal circuit can be found in O(n^2) time and beats Qiskit and Tket by constant factors of x2.57 and x2.28 in total gates on chains up to n = 80 qubits. If the connectivity is an arbitrary tree given as input, no worst-case polynomial-time algorithm exists unless P = NP.

For a reader choosing a fermionic architecture or a compilation strategy, the paper's own variables point to the same priority: the connectivity graph of the available braids, not the target unitary, is what determines whether gate-optimal synthesis is reachable. The path case is the one the authors single out as most relevant for matchgate circuits in practice, because its generators map to single-qubit S gates and two-qubit R_xx(pi/2) rotations under Jordan-Wigner.

Sources used in this answer