Complexity separations for optimal matchgate-Clifford synthesis

1 Introduction

• Matchgate-Clifford unitaries support randomized fermionic protocols and play a role in matchgate synthesis, since the group together with the T gate is universal for matchgates.The group forms a matchgate 3-design and is used in fermionic classical shadows, device benchmarking, and fermionic sampling.Source: §1 · p. 2
• Path and complete graphs admit classical optimal-synthesis algorithms, while arbitrary tree connectivity makes the decision problem NP-complete.For path graphs, the paper also bounds the minimum two-qubit-gate count and proves a circuit can attain that count while also minimizing total gates.Source: §1 · p. 3
• ×2.57 versus Qiskit and ×2.28 versus Tket in total gate count on chains up to n=80 qubits.The benchmark compares the path-graph optimal compiler with both standard compilers.Source: §1 · p. 3
• Under Jordan-Wigner, the path-graph generators correspond to single-qubit S gates and two-qubit Rxx rotations, making this case practically relevant for matchgate circuits.The authors note that fermionic devices could allow other Majorana connectivities, for which their results offer topology guidance.Source: §1 · p. 3
• A polynomial upper bound on braid count places synthesis on arbitrary connected graphs in NP; tree hardness then makes it NP-complete.The tree reduction is from token swapping on trees, with additional signs to account for in the Majorana setting.Source: §1 · p. 3

2.1 The matchgate group

• Matchgate dynamics correspond under Jordan-Wigner to free-fermionic unitaries in second quantization, and matchgates preserve parity.The cited mapping caveat is that this equivalence may not hold under a different fermion-to-qubit mapping.Source: §2.1 · pp. 3–4
• Matchgate unitaries are generated by single-qubit Z and nearest-neighbor XX rotations, and their adjoint action is represented by a 2n × 2n special orthogonal matrix.Using this representation avoids working with exponentially large matchgate matrices; under a different fermion-to-qubit mapping, the stated Jordan-Wigner equivalence may not hold.Source: §2.1 · pp. 3–4

2.2 The matchgate-Clifford group

• The matchgate-Clifford adjoint action is isomorphic to the group of 2n × 2n signed permutation matrices with determinant +1.A signed permutation has one ±1 entry in each row and column; determinant +1 requires the inversion number plus the number of negative entries to be even.Source: §2.2 · pp. 4–5

2.3 Optimal matchgate-Clifford synthesis

• For a generating set G and target w, optimal synthesis seeks a word of minimum length ℓG(w); the decision version asks whether such a word has length at most k.When ℓ is polynomial in n, a proposed word can be checked efficiently by multiplying its gate matrices, placing the decision problem in NP.Source: §2.3 · p. 5

3.1 Path graph

• On a path, an O(n^2)-time algorithm outputs an optimal synthesis of length ℓR(w) = inv(π) + 2ν(w), adding twice the number of negative defects to the inversion count.Here π is the underlying permutation and ν(w) counts negative defects.Source: §3.1 · pp. 7–8

3.1.1 Comparison against other compilers

• Through n=80 qubits, the optimal path compiler improves total gate count by ∼1.5 over matchgate-dedicated methods and up to ∼2.6 over general compilers.The benchmark also reports similar reductions in two-qubit gates, though the compiler does not guarantee optimality for that metric.Source: Figure 3 · p. 9, §3.1.1 · p. 9

3.1.2 Optimality in the number of two-qubit gates

• The minimum two-qubit gate count separates sign-correction cost 2νeven(w) from µ(π), and one word simultaneously attains this count and minimum total length.Efficiently computable bounds give a factor-2 approximation to µ(π); its exact computation remains open.Source: §3.1.2 · pp. 10–11

3.2 Complete graph

• For complete-graph connectivity, the paper establishes classical optimal synthesis and states a minimum-generator result for signed permutations.The result considers signed permutations with underlying permutation cycle structure; the number of defective cycles must be even.Source: §3.2 · pp. 11–12
• For complete connectivity, ℓ_all(w)=2n−κ(π)+d−(w), and an optimal word is computable in O(n^2) classical time.Here κ(π) is the number of cycles in π, and d−(w) is the number of defective cycles.Source: §3.2 · p. 12
• For complete connectivity, the Cayley-graph diameter is 2n, attained by −e, making the all-to-all synthesis bound tight.Source: §3.2 · p. 12

3.3 Tree graphs

• On tree connectivity, gate-optimal decision synthesis is NP-complete via a sign-aware reduction from tree routing, with a polynomial length bound establishing membership in NP.For each permutation, the reduction efficiently chooses signs so the minimum braid-sequence length equals the minimum number of routing swaps.Source: §3.3 · pp. 13–14
• On tree connectivity, depth-optimal matchgate-Clifford synthesis is also NP-complete.The proof uses tree-routing results and the same approach to handle signs.Source: §3.3 · p. 14

3.4 Connected graphs

• With arbitrary connected graphs, both gate-optimal and depth-optimal synthesis decision problems are NP-complete.The result follows from tree connectivity and a polynomial upper bound on synthesis sequence length for signed permutations on any graph.Source: §3.4 · p. 14

4 Discussion

• The work gives closed-form optimal synthesis lengths and algorithms for path and complete graphs, benchmarks path synthesis up to n = 80 qubits, and proves tree-graph decision synthesis NP-complete.The path algorithm is compared with standard quantum compilers; the discussion does not state the benchmark’s numerical improvements.Source: §4 · p. 14
• The results distinguish total-gate synthesis from depth-focused approaches and leave open which fixed connectivities admit efficient optimal synthesis.The paper presents its gate-count perspective as complementary to prior depth results.Source: §4 · p. 14
• The authors identify circuit compression for fermionic simulation as a possible application of their results.Source: §4 · p. 14
• Optimal synthesis complexity for the full matchgate group, exact or approximate, remains unknown, motivating study of how algebraic structure, generating sets, and hardware connectivity interact.Source: §4 · p. 15
• Majorana-braid word lengths provide exact formulas for a physically motivated generating set, while standard Coxeter length functions miss the additional sign-correction term.The matchgate-Clifford adjoint action is isomorphic to the unit-determinant signed permutation group.Source: §4 · p. 15
• Source code, benchmark scripts, and plotted raw data for Fig. 3 are publicly available on GitHub.Source: §4 · p. 15

A Proof of Theorem 1

• The potential Φ(w) = inv(π) + 2ν(w) counts inversions and negative defects, and each generator changes it by exactly one, yielding a word-length lower bound.Here ν(w) is the number of negative defects.Source: A Proof of Theorem 1 · pp. 20, 22
• Every target has an O(n^2)-time compiler outputting a word of optimal length ℓR(w) = Φ(w).The construction matches the lower bound with a word of length exactly Φ(w).Source: A Proof of Theorem 1 · pp. 20, 25
• A permutation's inversion graph is connected exactly when it has no non-trivial cuts.This equivalence identifies the cut-free blocks used in the construction.Source: A Proof of Theorem 1 · pp. 22–23
• For a cut-free permutation, reorienting generators along inversion-graph paths can flip any chosen pair of Majorana signs without changing the permutation or word length.The intermediate sign changes along a path cancel in pairs.Source: A Proof of Theorem 1 · p. 24
• The construction synthesizes cut-free blocks internally, then corrects determinant parity at bad cuts using two generators per correction.The cut-free block words concatenate because there are no inversions between blocks.Source: A Proof of Theorem 1 · pp. 24–25

Details on numerical benchmarks

• Targets are random walks of length 10n, sampled at n = 10, 20, 30, 40, 60, and 80 with 5–10 targets per size.The ensemble is not uniform over signed permutations, and typical optimal gate count depends on the ensemble.Source: B Details on numerical benchmarks · p. 26
• The compiler greedily lowers Φ to obtain optimal total gate count, while its Rxx count only upper-bounds the minimum two-qubit count.When multiple descending generators are available, it uses a fixed ordering without preferring one- or two-qubit gates.Source: B Details on numerical benchmarks · p. 26
• The comparison includes sort-then-fix and Givens elimination alongside Qiskit and pytket; outputs are checked against the target tableau or signed permutation.Qiskit transpilation uses S, S†, and Rxx basis gates with a line coupling map; pytket applies two specified optimization passes.Source: B Details on numerical benchmarks · p. 26
• ×2.57 vs Qiskit and ×2.28 vs pytket are the total-gate fit-growth ratios; sort-then-fix and Givens elimination each have a 1.58 and 1.53 ratio, respectively.The ratios compare baseline to the optimal compiler across the sampled range.Source: B Details on numerical benchmarks · p. 27
• ×2.99 vs Qiskit, ×2.44 vs pytket, ×1.58 vs sort-then-fix, and ×1.50 vs Givens elimination are the Rxx-count fit-growth ratios.These are baseline-to-compiler ratios across the sampled range.Source: B Details on numerical benchmarks · p. 27

C Proof of Theorem 2

• The minimum two-qubit gate count is μ(π) + 2ν_even(w), where μ(π) is the minimum number of even-indexed generators in a reduced word for π.Here ν_even(w) counts bad even cuts; the upper-bound construction uses μ(π) generators plus two for each such cut.Source: C Proof of Theorem 2 · pp. 27–29
• Every realizing word requires at least μ(π) even-indexed generators plus two additional ones for each bad even cut.A bad even cut requires at least two occurrences of its generator, which is absent from every reduced word for π.Source: C Proof of Theorem 2 · pp. 27–28
• The constructive upper bound corrects each bad even cut with two gates, while remaining sign mismatches can be corrected without adding two-qubit gates.Within each cut-free block, sign defects have even parity and can be paired using paths in its connected inversion graph.Source: C Proof of Theorem 2 · pp. 28–29
• One word simultaneously achieves the minimum total length from Theorem 1 and the minimum two-qubit gate count.The construction starts with a reduced word containing exactly μ(π) even-indexed transpositions and adds two generators per bad cut; sign corrections preserve both counts.Source: C Proof of Theorem 2 · pp. 27, 29, 30
• The exact evaluation of μ(π) remains open, but polynomial-time computable bounds are available, including a constructive upper bound that gives a factor-2 approximation.The bounds use the net Majorana flow across boundaries and the pairing number.Source: C Proof of Theorem 2 · pp. 27, 30
• A constructive factor-2 approximation to µ(π) follows by combining the routing upper bound with the matching-based lower bound.The proof bounds the matching quantity by F(π), yielding the lower bound used in the approximation.Source: C Proof of Theorem 2 · pp. 33–34
• F(π) can be computed in polynomial time by summing the boundary flows Fβ from the Majoranas’ source and target positions.The proof bounds the flow across each physical-mode boundary using the numbers of starting and target positions on either side.Source: C Proof of Theorem 2 · p. 34
• The routing upper bound is constructive: it uses at most 2F(π) inter-mode exchanges, and F(π) is polynomially bounded in n.At each step, the procedure chooses a productive exchange when available or otherwise selects the rightmost right-moving Majorana.Source: C Proof of Theorem 2 · p. 34
• The lower-bound quantity ξ(π) is a degree-constrained bipartite matching on a graph with at most 2n vertices and O(n^2) edges, solvable in polynomial time via maximum flow.Its vertex capacities are |t_i − s_i|, and each edge has capacity one.Source: C Proof of Theorem 2 · pp. 33–34

• Theorem 3 characterizes the minimum braid count using the underlying permutation’s cycle count and the number of defective cycles.Source: D Proof of Theorem 3 · p. 34
• A potential provides a lower bound on synthesis length, and the proof constructs a word attaining that bound.Source: D Proof of Theorem 3 · pp. 35–36
• From every nonidentity target, the algorithm selects a generator that decreases the potential by exactly one, then reverses the resulting sorting word.Source: D Proof of Theorem 3 · p. 37
• O(n^2) classical time suffices: each of at most O(n) generator choices takes O(n) work.Source: D Proof of Theorem 3 · p. 37

• The decision versions of both gate-optimal and depth-optimal synthesis with tree Majorana braids are NP-complete.Source: E Proof of Theorems 4 and 5 · pp. 38, 40
• The gate-count reduction encodes a token permutation as a signed permutation, assigning a negative sign to the smallest element of each even-length cycle.Source: E Proof of Theorems 4 and 5 · p. 38
• For a routed permutation, braid orientations can realize the target signs in polynomial time, enabling the reduction from tree token swapping to gate-optimal synthesis.Source: E Proof of Theorems 4 and 5 · pp. 38–39
• The depth-hardness proof uses parallel-round token swapping, while a polynomial gate-count bound on trees supplies membership in NP.Source: E Proof of Theorems 4 and 5 · p. 40

• A polynomial upper bound on braid count for connected graphs supports membership in NP when extending the tree hardness results.Source: F Proof of Corollary 1 · pp. 40–41
• Every connected graph contains a spanning tree, so its allowed generators include those of a tree on the same vertices.Source: F Proof of Corollary 1 · p. 41
• Gate-optimal and depth-optimal synthesis with Majorana braids on general connectivity graphs are NP-complete.Source: F Proof of Corollary 1 · p. 41