Complexity separations for optimal matchgate-Clifford synthesis

Berta Casas; Diego Garc\'ia-Mart\'in; Yuxuan Zhang

REVIEW

Complexity separations for optimal matchgate-Clifford synthesis

Berta Casas, Diego García-Martín, Yuxuan Zhang

Quantum Physics · Submitted 5 Oct 2026 · 88 references

Pith's verdict: A solid complexity separation for matchgate-Clifford synthesis: poly-time optimal compilers on path and all-to-all connectivity, NP-completeness on trees, with two minor presentation caveats in the benchmark claims and the two-qubit formula.

T0 · AI review

How this review was made: An AI referee (deepseek/deepseek-v4-flash) read the paper on October 6, 2026 and answered a fixed list of questions about it. T0 is the starting level every paper gets. The levels describe how deeply Pith has checked the paper, never the authors.

T0 AI review An AI read the paper and answered a fixed list of questions.
T1 Audit Automatic checks that the references and files the paper relies on exist and match.
T2 Compute The paper's code or calculations re-run with the same results.
T3 Formal statement The claims written out in a formal math language a computer can read.
T4 Proof Those claims proved, and the proof checked by computer.

How Pith checks papers →

· 7 minor · Ask about this paper · The compiled record · Read the full review →

Challenge this review Comment (0) Read on arXiv ↗

Cite ▾

arXiv ID2610.06768 (version 1)

Pith IDA3ZA7WBN, Pith's permanent record of this paper and its review

CitationBerta Casas, Diego Garc\'ia-Mart\'in, Yuxuan Zhang. "Complexity separations for optimal matchgate-Clifford synthesis." arXiv:2610.06768 (2026). https://pith.science/paper/A3ZA7WBN

Cite this reviewBibTeX for Pith's review of this paper

Claim paper

Why Pith says this

Highlight any text to comment on it.

Editor's note

read the letter

The headline result is a genuine first: closed-form word lengths for optimal matchgate-Clifford synthesis under Majorana-braid generators on a path (ℓ_R = inv(π) + 2ν(w)) and all-to-all connectivity (ℓ_all = 2n − κ(π) + d_(w)), each realized by an O(n²) optimal compiler, plus NP-completeness of the decision version on arbitrary trees via a reduction from token swapping. Matchgate synthesis complexity was open in [24], and the path/complete-versus-tree separation is new. Standard Coxeter length functions for types B and D use different generators and miss the sign-correction term, so these formulas are not derivative.

The proofs are honest potential-method arguments with matching lower and upper bounds, no fitted parameters. Lemma 1, the step that each generator changes Φ by ±1, is the delicate part and it holds: the analysis of when a cut appears or disappears at position a, ruling out the ±3 jump, is correct. The NP-hardness reduction leans on Lemma 7, the sign-placement lemma — for any swap sequence on a tree realizing π, you can orient braids to realize the signed permutation w*(π). I checked the parity argument on each π-invariant component and the F₂-span argument (path-telescoping of e_u + e_v); both go through, so the equality ℓ_T(w*(π)) = ℓ_T(π) that carries the reduction stands.

Two soft spots, both minor and both acknowledged in the text. First, the ×2.57 and ×2.28 benchmark factors are scoped to the non-uniform random-walk ensemble of Appendix B; the body states this explicitly, but the abstract reads as general. The abstract should carry the ensemble qualifier. Second, Theorem 2's two-qubit-optimal formula #2(w) = μ(π) + 2ν_even(w) is not yet fully constructive because computing μ(π) is left open; the factor-2 approximation is the constructive part, and the authors say so. That is a completeness note on a secondary theorem, not a flaw in the main separation. I found no load-bearing error. The paper also discloses AI assistance and states independent verification of all arguments, which matches the detail level of the proofs.

This is for people working on fermionic simulation, matchgate compilation, classical shadows, and signed-permutation combinatorics; the compiler itself is practically useful. It deserves a serious referee.

Referee report

Significance

The paper delivers a clean complexity separation: exact optimal matchgate-Clifford synthesis is polynomial-time with exact closed-form word lengths for path and complete connectivities, yet NP-complete on trees. The proofs combine potential-method lower bounds with matching constructive upper bounds and are unusually detailed; the NP-hardness reduction is answer-preserving through Lemma 7, whose two key steps (sign-defect vectors of even weight on every π-invariant component of the swap multigraph, and the F2-span realizability of such vectors) I verified. The closed forms also give exact diameters of the relevant Cayley graphs. The benchmark code and data are publicly available, which supports reproducibility of the empirical claims. I found no load-bearing errors: Lemma 1 (the potential change ±1, with new cut points only at position a) and Lemma 7 (orientation placement for arbitrary swap sequences) both hold as stated.

Minor objections (7)

[§3.1.2, Theorem 2] The formula #₂(w) = μ(π) + 2ν_even(w) is exact, but the main term μ(π) is not known to be efficiently computable, a point the authors acknowledge immediately after the theorem ('The exact evaluation of the routing term μ(π) and how to construct a word that achieves it remains open'). Since the paper's headline is O(n²) solvability, I recommend carrying a one-line caveat into the theorem statement itself so readers do not read Theorem 2 as an efficiently computable closed form.
[§3.1.1 and Fig. 3] The multiplicative ratios (2.57, 2.28, etc.) are computed from unweighted linear fits over means of 10, 10, 8, 8, 6, and 5 targets per size; with only 5 targets at n = 80, the 'constant factor' claim should be reported explicitly as a fit ratio, ideally with per-size ratios and confidence intervals. It would also help to state in the caption or main text that Qiskit and pytket do not exploit the signed-permutation structure, so part of the observed gap is structural rather than algorithmic.
[§3.1, Introduction] Reference [35] (Miltzow et al., on token swapping approximation) is cited to support 'well-known sorting algorithms for permutation matrices'; that reference does not appear to contain such an algorithm, and a standard sorting or inversion-distance reference would fit better.
[References] Reference [21] lists the author as 'A. Acuaviva, A. Acuaviva, and P. Acuaviva', which appears to be a transcription error; please correct the author list.
[Appendix C, Lemma 5] Minor typo: 'in the grap' should read 'in the graph'.
[Appendix B / Fig. 3 caption] The number of sampled targets per circuit size appears only in Appendix B; a brief note in the caption would help readers interpret the error bars and the fit-based ratios directly from the figure.
[§3.3] Because the reduction must construct the sign configuration w*(π) from the permutation alone, without prior knowledge of an optimal routing (a point the authors correctly emphasize), a small worked example of Lemma 7 on a short tree would substantially clarify the argument for readers.

How Pith checks papers → · Full audit of this paper →

The paper

The paper claims

Optimal synthesis of matchgate-Clifford circuits is easy on a line or all-to-all graph, but deciding it is NP-complete on arbitrary trees.

The reading

Matchgate-Clifford unitaries are a standard class of classically simulable quantum circuits, and their adjoint action on Majorana operators is exactly the group of unit-determinant signed permutations of $2n$ modes. This paper asks how many Majorana-braid gates are needed to realize a given such unitary, and shows the answer depends on which edges of the connectivity graph the braids may use. On a path and on the complete graph, the optimal word length has a closed-form expression and an optimal compiler runs in $O(n^2)$ time. On an arbitrary tree, the decision version of optimal synthesis is NP-complete, in both gate count and depth. The path-graph compiler beats Qiskit and Tket by constant factors on chains of up to 80 qubits.

What carries the argument

The argument runs on the isomorphism between the adjoint action of the matchgate-Clifford group and the group $B_{2n} \cap SO(2n)$ of unit-determinant signed permutation matrices of the $2n$ Majorana modes. Two potentials carry the positive results: on the path, $\Phi(w) = \mathrm{inv}(\pi) + 2\nu(w)$, where $\nu(w)$ counts the negative defects, cuts $c$ where the leading $c\times c$ minor has determinant $-1$, and the proof uses the connectedness of the inversion graph of a cut-free permutation to flip signs at no extra gate cost; on the complete graph, $\Phi_{\mathrm{all}}(w) = 2n - \kappa(\pi) + d_-(w)$, with $d_-$ counting defective cycles. For the NP-hardness, the load-bearing object is a sign-placement lemma that assigns signs to cycles of the underlying permutation, negative on the smallest element of each even-length cycle, so that any swap routing on the tree can be oriented, in polynomial time, to realize that signed permutation without knowing the optimal routing.

Extended reading notes

Core claim

The paper's central claim is that optimal exact synthesis in the matchgate-Clifford group, from the generating set of Majorana braids, has a complexity that depends sharply on the connectivity graph. On an open path, the optimal word length is $\ell_R(w) = \mathrm{inv}(\pi) + 2\nu(w)$, the inversion number of the underlying permutation plus twice the number of negative defects, and a matching circuit is output in $O(n^2)$ time. On the complete graph, the optimal length is $\ell_{\mathrm{all}}(w) = 2n - \kappa(\pi) + d_-(w)$, where $\kappa$ counts the cycles of the permutation and $d_-$ counts the defective cycles, again constructible in $O(n^2)$ time. On an arbitrary tree, the decision version of gate-optimal and depth-optimal synthesis is NP-complete, via a reduction from token swapping on trees; the reduction is made to work by a lemma that places signs per cycle, negative on the smallest element of each even-length cycle, so that any routing of the underlying permutation can be oriented to realize the required signed permutation without knowing an optimal routing. A corollary extends NP-completeness to arbitrary connected graphs, and the closed-form path compiler yields constant-factor gate-count improvements over two production compilers in benchmarks on chains of up to 80 qubits.

Load-bearing premise

The load-bearing premise for the NP-hardness is Lemma 7, which asserts that for any swap sequence on a tree realizing a given permutation, the braid orientations can be chosen in polynomial time to realize the specific signed permutation whose signs are negative on the smallest element of each even-length cycle.

Editorial extensions

If this is right

Every matchgate-Clifford unitary can be synthesized with at most $2n$ all-to-all braids, and this bound is tight; on the path the exact optimal word length is $\mathrm{inv}(\pi) + 2\nu(w)$, with an explicit quadratic-time compiler.
On trees, and hence on general connected graphs, no polynomial-time algorithm for gate-optimal or depth-optimal synthesis exists unless P = NP.
On the path there is a single word that is simultaneously optimal in total gate count and in two-qubit gate count, with the two-qubit cost equal to $\mu(\pi) + 2\nu_{\mathrm{even}}(w)$; only a factor-2 approximation to $\mu(\pi)$ is known, and its exact computation is left open.
Benchmarks on chains of up to 80 qubits show the optimal path compiler reduces total gate counts by constant factors (up to about 2.6x) relative to Qiskit and Tket, and similar reductions in two-qubit gate count.

Reading between the lines

Editorial extensions of the paper, not claims the author makes directly.

Because the closed-form word lengths coincide with the Cayley-graph distances of the braid generating set, the results give exact diameters of those Cayley graphs, $2n$ on the all-to-all graph, which could be reused for sampling or benchmarking fermionic circuits.
The per-cycle sign placement used for the tree reduction may transfer to other signed-permutation groups where token-swapping hardness is known, potentially marking other braid-like gate sets as NP-hard to synthesize.
The NP-completeness on trees is a worst-case statement; typical instances may still admit practical heuristics, and the paper's own benchmark notes the sampled ensemble is not uniform on the group, so the reported constant-factor improvements describe typical random-walk targets rather than worst cases.
Since the two-qubit-optimal routing cost $\mu(\pi)$ remains open even with a factor-2 approximation, a natural next target is an exact polynomial algorithm for $\mu(\pi)$ or a hardness proof for it.

Original 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.

The compiled record

The paper's own sentences, arranged, kept beside the review and separate from it. Each label is drawn from a closed vocabulary; the number beside it is the probability the classifier gave that label. Numbers in the tables are the authors', checked by code. No sentence in this record was written by a model.

Compiled by classifier-1.13.0 via TypeSafe API, question bank abstract-p1-20260923, 2026-10-06: 1 request, 6,969 input tokens.

What the abstract itself states, as probabilities: claims first 0.04 · states limitation 0.41 · human participants 0.01 · controlled comparison 0.60 · randomized assignment 0.03 · states quantitative result 0.98 · compares with prior results 0.94 · mentions code or data availability 0.05.

The abstract, sentence by sentence

arXiv listing abstract v1. Results and the main claim are underlined; show every role.

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.

background contribution method result interpretation main claim

What the classifier reports for each sentence. The number is the probability it gave the label.
#	sentence	role	the authors' own work	states the main conclusion	strength
s0	Clifford and matchgate circuits are canonical families of classically simulable quantum circuits.	background 1.00	0.05	0.02	asserted 1.00
s1	Their intersection, the matchgate-Clifford group, plays an important role in randomized fermionic protocols and in matchgate synthesis.	background 1.00	0.08	0.02	asserted 1.00
s2	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.	background 0.50	0.48	0.05	asserted 1.00
s3	That is, given a target unitary and a gate set, output an $n$-qubit circuit implementing the target using the fewest operations.	background 0.77	0.17	0.03	asserted 0.72
s4	We show that the complexity of this problem strongly depends on the gate set.	result 0.94	0.89	0.40	asserted 1.00
s5	In particular, we study gate sets consisting of Majorana braids with different connectivity graphs.	contribution 0.63	0.68	0.04	asserted 0.88
s6	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.	result 0.96	0.96	0.19	asserted 1.00
s7	In addition, we prove that when the connectivity graph is a tree, the decision version of the optimal synthesis problem becomes NP-complete.	result 0.99	0.95	0.29	asserted 1.00
s8	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.	result 0.93	0.97	0.10	asserted 1.00

What kind of paper the classifier reports this is: theoretical result 0.92 · evidence from proof or derivation 1.00.

What was examined, and what was not

sources read

arXiv listing abstract v1

not examined

full text
figures and tables
references and citing sentences
relations to other papers

levels run

P abstract

not run

S sections
T body sentences
C citations
R cross-paper relations

Every quoted sentence on this record is the authors'. Every label is from Pith's closed vocabulary, with the probability shown beside it. Every number in the measurements table is the authors', checked by code. Record as JSON

Figures

**Figure 1.** Overview of our main results. We consider the problem of optimal unitary synthesis in the matchgate-Clifford group. Representing the target n-qubit unitary as a 2n × 2n signed permutation matrix with determinant +1, we ask for an optimal circuit with a minimum number of Majorana braids along the edges of a given connectivity graph. We show that for path and complete graphs, the problem can be solved efficiently on a classical computer by providing explicit algorithms that run in O

**Figure 2.** Example of an optimal synthesis with nearest-neighbor braids on an open path. The number of gates from the generating set R = r ±1 a 2n−1 a=1 required to synthesize w is ℓR(w), which splits into five inversions plus four gates to correct the sign defects captured by the number of bad cuts, ν(w). We first decompose the permutation matrix w into three subpermutation blocks w1, w2 and w3. We then identify the bad cuts c, for which ∆c = −1. We use the inversions to synthesize the sub-permutation blocks, leveraging the freedom in choosing ra or r −1 a to deposit the extra signs at the…

**Figure 3.** Performance of our optimal path synthesis algorithm. Randomly generated Clifford-matchgate circuits are compiled using different strategies: our optimal compiler, a Givens elimination strategy, sort then fix, pyket and Qiskit. In panel (a) we plot the average total gate count for different circuit sizes, and in panel (b) we plot the average number of two-qubit gates. Error bars represent the standard deviation. In both plots, we fit the data to straight lines and show the constant relative improvement achieved by our compiler over the other methods. 3.1.1 Comparison against other…

**Figure 4.** Example of an optimal synthesis with all-to-all braids. The underlying permutation π = |w˜| is decomposed into its cycle structure, with κ(π) = 3. Sorting these cycles requires 2n−κ(π) = 5 generators, as shown in green. The target contains d−(w) = 2 defective cycles, which require two additional generators for the sign correction. After the permutation has been sorted, the remaining sign defects are paired and removed by r 2 37, as shown in pink. This gives an optimal total length ℓall(w) = 7. For visual clarity, we use right multiplication convention. Finally an optimal synthesis…

**Figure 5.** Inversion graphs for two permutations in S6. (a) The permutation π has nontrivial cuts and its inversion graph is disconnected. (b) In contrast, σ has no non-trivial cuts, and its inversion graph is connected. Conversely, suppose that Γσ is disconnected. Consider the connected component containing the value 1, and let c be the maximum value in this component such that [c] is in the component. If c = m, then all vertices belong to the same connected component, in contradiction with the assumption that Γσ is disconnected. Therefore, c < m, and c+1 does not belong to the component.…

Figures reproduced from arXiv:2610.06768 by the authors.

References

Works cited (88)

[24]

B. Casas, P. Braccia, ´E. Gouzien, M. Cerezo, and D. Garc´ ıa-Mart´ ın, “Matchgate synthesis via clifford matchgates andTgates”, arXiv preprint arXiv:2602.05425 (2026)

View on Pith arXiv 2026
[1]

M. A. Nielsen and I. L. Chuang,Quantum computation and quantum information(Cambridge University Press, Cambridge, 2000)

View on Pith 2000
[2]

A. G. Fowler, M. Mariantoni, J. M. Martinis, and A. N. Cleland, “Surface codes: towards practical large-scale quantum computation”, Physical Review A86, 032324 (2012)

View on Pith 2012
[3]

D. Litinski, “A Game of Surface Codes: Large-Scale Quantum Computing with Lattice Surgery”, Quantum3, 128 (2019). 15

View on Pith 2019
[4]

J. van de Wetering and M. Amy, “Optimising quantum circuits is generally hard”, arXiv preprint arXiv:2310.05958 (2023)

View on Pith Pith review arXiv 2023
[5]

´E. Gouzien and N. Sangouard, “Provably optimal exact gate synthesis from a discrete gate set”, arXiv preprint arXiv:2503.15452 (2025)

View on Pith Pith review arXiv 2025
[6]

K. Matsumoto and K. Amano, “Representation of quantum circuits with clifford andπ/8 gates”, arXiv preprint arXiv:0806.3834 (2008)

View on Pith Pith review arXiv 2008
[7]

B. Giles and P. Selinger, “Remarks on matsumoto and amano’s normal form for single-qubit clifford+ t operators”, arXiv preprint arXiv:1312.6584 (2013)

View on Pith Pith review arXiv 2013
[8]

V. Kliuchnikov, D. Maslov, and M. Mosca, “Asymptotically optimal approximation of single qubit unitaries by clifford and t circuits using a constant number of ancillary qubits”, Physical Review Letters110, 190502 (2013)

View on Pith 2013
[9]

N. J. Ross and P. Selinger, “Optimal ancilla-free Clifford+T approximation of z-rotations”, Quantum Info. Comput.16, 901–953 (2016)

View on Pith 2016
[10]

P. Selinger,Exact and approximate synthesis of quantum circuits

View on Pith
[11]

V. Kliuchnikov, K. Lauter, R. Minko, A. Paetznick, and C. Petit, “Shorter quantum circuits via single-qubit gate approximation”, Quantum7, 1208 (2023)

View on Pith 2023
[12]

S. Yamamoto and N. Yoshioka, “Pygridsynth: a fast numerical tool for ancilla-free clifford+ t synthesis”, arXiv preprint arXiv:2604.21333 (2026)

View on Pith Pith review arXiv 2026
[13]

S. Yamamoto, H. Hamaguchi., and J. Lapeyre,Pygridsynth

View on Pith
[14]

H. Morisaki, K. Sano, and S. Akibue, “Optimal ancilla-free clifford+ t synthesis for general single-qubit unitaries”, arXiv preprint arXiv:2510.05816 (2025)

View on Pith arXiv 2025
[15]

D. Maslov, “Linear depth stabilizer and quantum fourier transformation circuits with no auxiliary qubits in finite-neighbor quantum architectures”, Physical Review A76, 052310 (2007)

View on Pith 2007
[16]

D. Maslov and M. Roetteler, “Shorter stabilizer circuits via bruhat decomposition and quan- tum circuit transformations”, IEEE Transactions on Information Theory64, 4729–4738 (2018)

View on Pith 2018
[17]

S. Bravyi, R. Shaydulin, S. Hu, and D. Maslov, “Clifford circuit optimization with templates and symbolic pauli gates”, Quantum5, 580 (2021)

View on Pith 2021
[18]

S. Bravyi and D. Maslov, “Hadamard-free circuits expose the structure of the clifford group”, IEEE Transactions on Information Theory67, 4546 (2021)

View on Pith 2021
[19]

S. Bravyi, J. A. Latone, and D. Maslov, “6-qubit optimal clifford circuits”, npj Quantum Information8, 79 (2022)

View on Pith 2022
[20]

T. Peham, N. Brandl, R. Kueng, R. Wille, and L. Burgholzer, “Depth-optimal synthesis of clif- ford circuits with sat solvers”, 2023 IEEE International Conference on Quantum Computing and Engineering (QCE)1, 802 (2023)

View on Pith 2023
[21]

A. Acuaviva, A. Acuaviva, and P. Acuaviva, “Cnot-distance is np-complete under all-to-all connectivity”, arXiv preprint arXiv:2608.03825 (2026)

View on Pith Pith review arXiv 2026
[22]

C. Li and J. Guan, “Vanilla exact synthesis of cnot circuits is np-hard”, arXiv preprint arXiv:2609.04160 (2026)

View on Pith Pith review arXiv 2026
[23]

L. L. Keller and R. K¨ ueng, “(a variant of) clifford circuit synthesis is np-complete”, arXiv preprint arXiv:2610.02029 (2026). 16

View on Pith Pith review arXiv 2026
[25]

M. Oszmaniec and Z. Zimboras, “Universal extensions of restricted classes of quantum oper- ations”, Physical Review Letters119, 220502 (2017)

View on Pith 2017
[26]

S. Bravyi and A. Kitaev, “Universal quantum computation with ideal clifford gates and noisy ancillas”, Phys. Rev. A71, 022316 (2005)

View on Pith 2005
[27]

K. Wan, W. J. Huggins, J. Lee, and R. Babbush, “Matchgate Shadows for Fermionic Quantum Simulation”, Communications in Mathematical Physics404, 629 (2023)

View on Pith 2023
[28]

V. Heyraud, H. Chomet, and J. Tilly, “Unified framework for matchgate classical shadows”, npj Quantum Information11, 65 (2025)

View on Pith 2025
[29]

M. West, M. Cerezo, and M. Larocca, “Particle-preserving fermionic shadows with mode- independent sample complexity”, arXiv preprint arXiv:2606.27254 (2026)

View on Pith Pith review arXiv 2026
[30]

J. Helsen, S. Nezami, M. Reagor, and M. Walter, “Matchgate benchmarking: scalable bench- marking of a continuous family of many-qubit gates”, Quantum6, 657 (2022)

View on Pith 2022
[31]

J. Carrasco, M. Langer, A. Neven, and B. Kraus, “Gaining confidence on the correct realiza- tion of arbitrary quantum computations”, Physical Review Research6, L032074 (2024)

View on Pith 2024
[32]

A. Portik, O. K´ alm´ an, T. Monz, and Z. Zimboras, “Clifford volume and free fermion volume: complementary scalable benchmarks for quantum computers”, arXiv preprint arXiv:2512.19413 (2025)

View on Pith Pith review arXiv 2025
[33]

M. Oszmaniec, N. Dangniam, M. E. Morales, and Z. Zimboras, “Fermion Sampling: A Robust Quantum Computational Advantage Scheme Using Fermionic Linear Optics and Magic Input States”, PRX Quantum3, 020328 (2022)

View on Pith 2022
[34]

R. C. Lyndon and P. E. Schupp,Combinatorial group theory(Springer, 2001)

View on Pith 2001
[35]

T. Miltzow, L. Narins, Y. Okamoto, G. Rote, A. Thomas, and T. Uno, “Approximation and hardness for token swapping”, Algorithms-ESA 2016, Proc. 24th Annual European Sympo- sium on Algorithms, Aarhus, 2016, Leibniz International Proceedings in Informatics (LIPIcs) (2016)

View on Pith 2016
[36]

A. Javadi-Abhari, M. Treinish, K. Krsulich, C. J. Wood, J. Lishman, J. Gacon, S. Martiel, P. D. Nation, L. S. Bishop, A. W. Cross, et al., “Quantum computing with qiskit”, arXiv preprint arXiv:2405.08810 (2024)

View on Pith Pith review arXiv 2024
[37]

Qiskit contributors,Qiskit: an open-source framework for quantum computing, 2023

View on Pith 2023
[38]

S. Sivarajah, S. Dilkes, A. Cowtan, W. Simmons, A. Edgington, and R. Duncan, “T|ket>: a retargetable compiler for NISQ devices”, Quantum Science and Technology6, 014003 (2020)

View on Pith 2020
[39]

S. B. Bravyi and A. Y. Kitaev, “Fermionic quantum computation”, Annals of Physics298, 210–226 (2002)

View on Pith 2002
[40]

F. Verstraete and J. I. Cirac, “Mapping local hamiltonians of fermions to local hamiltonians of spins”, Journal of Statistical Mechanics: Theory and Experiment2005, P09012–P09012 (2005)

View on Pith 2005
[41]

Z. Jiang, A. Kalev, W. Mruczkiewicz, and H. Neven, “Optimal fermion-to-qubit mapping via ternary trees with applications to reduced quantum states learning”, Quantum4, 276 (2020)

View on Pith 2020
[42]

J. Alicea, Y. Oreg, G. Refael, F. Von Oppen, and M. P. Fisher, “Non-abelian statistics and topological quantum information processing in 1d wire networks”, Nature Physics7, 412–417 (2011). 17

View on Pith 2011
[43]

O. Aichholzer, E. D. Demaine, M. Korman, J. Lynch, A. Lubiw, Z. Mas´ arov´ a, M. Rudoy, V. V. Williams, and N. Wein, “Hardness of token swapping on trees”, In 30th Annual European Symposium on Algorithms (ESA 2022). Leibniz International Proceedings in Informatics244, 3 (2022)

View on Pith 2022
[44]

E. Knill, “Fermionic Linear Optics and Matchgates”, arXiv preprint arXiv:quant-ph/0108033 (2001)

View on Pith Pith review arXiv 2001
[45]

B. M. Terhal and D. P. DiVincenzo, “Classical simulation of noninteracting-fermion quantum circuits”, Physical Review A65, 032325 (2002)

View on Pith 2002
[46]

D. P. DiVincenzo and B. M. Terhal, “Fermionic linear optics revisited”, Foundations of Physics 35, 1967 (2005)

View on Pith 2005
[47]

I. D. Kivlichan, J. McClean, N. Wiebe, C. Gidney, A. Aspuru-Guzik, G. K.-L. Chan, and R. Babbush, “Quantum simulation of electronic structure with linear depth and connectivity”, Physical Review Letters120, 110501 (2018)

View on Pith 2018
[48]

F. Arute, K. Arya, R. Babbush, D. Bacon, J. C. Bardin, R. Barends, S. Boixo, M. Broughton, B. B. Buckley, D. A. Buell, et al., “Hartree-fock on a superconducting qubit quantum com- puter”, Science369, 1084–1089 (2020)

View on Pith 2020
[49]

J. M. Arrazola, O. Di Matteo, N. Quesada, S. Jahangiri, A. Delgado, and N. Killoran, “Uni- versal quantum circuits for quantum chemistry”, Quantum6, 742 (2022)

View on Pith 2022
[50]

F. Verstraete, J. I. Cirac, and J. I. Latorre, “Quantum circuits for strongly correlated quantum systems”, Physical Review A79, 032316 (2009)

View on Pith 2009
[51]

B. Kraus, “Compressed quantum simulation of the ising model”, Physical Review Letters 107, 250503 (2011)

View on Pith 2011
[52]

A. Cervera-Lierta, “Exact ising model simulation on a quantum computer”, Quantum2, 114 (2018)

View on Pith 2018
[53]

Z. Jiang, K. J. Sung, K. Kechedzhi, V. N. Smelyanskiy, and S. Boixo, “Quantum algorithms to simulate many-body physics of correlated fermions”, Physical Review Applied9, 044036 (2018)

View on Pith 2018
[54]

P.-L. Dallaire-Demers, J. Romero, L. Veis, S. Sim, and A. Aspuru-Guzik, “Low-depth circuit ansatz for preparing correlated fermionic states on a quantum computer”, Quantum Science and Technology4, 045005 (2019)

View on Pith 2019
[55]

A. Sopena, M. H. Gordon, D. Garc´ ıa-Mart´ ın, G. Sierra, and E. L´ opez, “Algebraic Bethe Circuits”, Quantum6, 796 (2022)

View on Pith 2022
[56]

R. Ruiz, A. Sopena, M. H. Gordon, G. Sierra, and E. L´ opez, “The bethe ansatz as a quantum circuit”, Quantum8, 1356 (2024)

View on Pith 2024
[57]

R. Ruiz, A. Sopena, B. Pozsgay, and E. L´ opez, “Efficient eigenstate preparation in an inte- grable model with hilbert space fragmentation”, arXiv preprint arXiv:2411.15132 (2024)

View on Pith arXiv 2024
[58]

E. K¨ okc¨ u, T. Steckmann, Y. Wang, J. Freericks, E. F. Dumitrescu, and A. F. Kemper, “Fixed depth hamiltonian simulation via cartan decomposition”, Physical Review Letters 129, 070501 (2022)

View on Pith 2022
[59]

E. K¨ okc¨ u, D. Camps, L. B. Oftelie, J. K. Freericks, W. A. de Jong, R. Van Beeumen, and A. F. Kemper, “Algebraic compression of quantum circuits for hamiltonian evolution”, Physical Review A105, 032420 (2022). 18

View on Pith 2022
[60]

L. G. Valiant, “Quantum computers that can be simulated classically in polynomial time”, in Proceedings of the thirty-third annual acm symposium on theory of computing (2001), pp. 114–123

View on Pith 2001
[61]

S. Bravyi, “Lagrangian representation for fermionic linear optics”, Quantum Info. Comput. 5, 216–238 (2005)

View on Pith 2005
[62]

R. Jozsa and A. Miyake, “Matchgates and classical simulation of quantum circuits”, Proceed- ings of the Royal Society A: Mathematical, Physical and Engineering Sciences464, 3089–3106 (2008)

View on Pith 2008
[63]

R. Jozsa, B. Kraus, A. Miyake, and J. Watrous, “Matchgate and space-bounded quantum computations are equivalent”, Proceedings of the Royal Society A: Mathematical, Physical and Engineering Sciences466, 809 (2010)

View on Pith 2010
[64]

S. Ramelow, A. Fedrizzi, A. M. Steinberg, and A. White, “Matchgate quantum computing and non-local process analysis”, New Journal of Physics12, 083027 (2010)

View on Pith 2010
[65]

D. J. Brod and E. F. Galvao, “Extending matchgates into universal quantum computation”, Physical Review A84, 022310 (2011)

View on Pith 2011
[66]

D. J. Brod and A. M. Childs, “The computational power of matchgates and the xy interaction on arbitrary graphs”, Quantum Information and Computation14, 901 (2014)

View on Pith 2014
[67]

D. J. Brod, “Efficient classical simulation of matchgate circuits with generalized inputs and measurements”, Physical Review A93, 062332 (2016)

View on Pith 2016
[68]

A. Zhao, N. C. Rubin, and A. Miyake, “Fermionic Partial Tomography via Classical Shadows”, Physical Review Letters127, 110504 (2021)

View on Pith 2021
[69]

N. L. Diaz, D. Garc´ ıa-Mart´ ın, S. Kazi, M. Larocca, and M. Cerezo, “Showcasing a barren plateau theory beyond the dynamical lie algebra”, arXiv preprint arXiv:2310.11505 (2023)

View on Pith Pith review arXiv 2023
[70]

A. A. Mele and Y. Herasymenko, “Efficient Learning of Quantum States Prepared With Few Fermionic Non-Gaussian Gates”, PRX Quantum6, 010319 (2025)

View on Pith 2025
[71]

M. Stroeks, D. Lenterman, B. Terhal, and Y. Herasymenko, “Solving free fermion problems on a quantum computer”, arXiv preprint arXiv:2409.04550 (2024)

View on Pith arXiv 2024
[72]

P. Braccia, N. Diaz, M. Larocca, M. Cerezo, and D. Garc´ ıa-Mart´ ın, “Optimal haar random fermionic linear optics circuits”, arXiv preprint arXiv:2505.24212 (2025)

View on Pith Pith review arXiv 2025
[73]

P. Sierant, T. X., and P. S. Tarabunga, “Theory of the matchgate commutant”, arXiv preprint arXiv:2603.12392 (2026)

View on Pith arXiv 2026
[74]

P. Braccia, N. Diaz, M. Larocca, M. Cerezo, and D. Garc´ ıa-Mart´ ın, “The commutant of fermionic gaussian unitaries”, arXiv preprint arXiv:2603.19210 (2026)

View on Pith arXiv 2026
[75]

M. Lastres and S. Moudgalya, “Geometry of free fermion commutants”, arXiv preprint arXiv:2604.05031 (2026)

View on Pith Pith review arXiv 2026
[76]

M. West, S. Y. Chang, L. Coffman, M. Larocca, and M. Cerezo, “Practical fermionic shadows enabled by improved sample-complexity bounds”, arXiv preprint arXiv:2609.40173 (2026)

View on Pith Pith review arXiv 2026
[77]

M. West and M. Larocca, “Fermionic gaussianity can be tested with mode-independent sample-complexity”, arXiv preprint arXiv:2610.02050 (2026)

View on Pith Pith review arXiv 2026
[78]

T. Guaita, L. Hackl, and T. Quella, “Representation theory of gaussian unitary transforma- tions for bosonic and fermionic systems”, arXiv preprint arXiv:2409.11628 (2024). 19

View on Pith Pith review arXiv 2024
[79]

A. Mitra, M. J. Martin, G. W. Biedermann, A. M. Marino, P. M. Poggi, and I. H. Deutsch, “Robust mølmer-sørensen gate for neutral atoms using rapid adiabatic rydberg dressing”, Physical Review A101, 030301 (2020)

View on Pith 2020
[80]

R. Bl¨ umel, N. Grzesiak, N. Pisenti, K. Wright, and Y. Nam, “Power-optimal, stabilized en- tangling gate between trapped-ion qubits”, npj Quantum Information7, 147 (2021)

View on Pith 2021
[81]

A. Bjorner and F. Brenti,Combinatorics of coxeter groups(Springer, 2005)

View on Pith 2005
[82]

D. Gonz´ alez-Cuadra, D. Bluvstein, M. Kalinowski, R. Kaubruegger, N. Maskara, P. Naldesi, T. V. Zache, A. M. Kaufman, M. D. Lukin, H. Pichler, et al., “Fermionic quantum processing with programmable neutral atom arrays”, Proceedings of the National Academy of Sciences 120, e2304294120 (2023)

View on Pith 2023
[83]

P. Diaconis,Group representations in probability and statistics, Vol. 11 (Institute of mathe- matical statistics Hayward, CA, 1988)

View on Pith 1988
[84]

N. Maskara, M. Kalinowski, D. Gonzalez-Cuadra, and M. D. Lukin, “Fast simulation of fermions with reconfigurable qubits”, arXiv preprint arXiv:2509.08898 (2025)

View on Pith Pith review arXiv 2025
[85]

N. Constantinides, J. Yu, D. Devulapalli, A. Fahimniya, L. Schaeffer, A. M. Childs, M. J. Gullans, A. Schuckert, and A. V. Gorshkov, “Low-depth fermion routing without ancillas”, arXiv preprint arXiv:2510.05099 (2025)

View on Pith arXiv 2025
[86]

M. West, M. Cerezo, and M. Larocca, “Strong matchgate designs in nearly optimal depth”, arXiv preprint arXiv:2609.26677 (2026)

View on Pith Pith review arXiv 2026
[87]

F. Brenti, V. Reiner, and Y. Roichman, “Alternating subgroups of coxeter groups”, arXiv preprint math/0702177 (2007)

View on Pith Pith review arXiv 2007
[88]

A. Schrijver,Combinatorial optimization: polyhedra and efficiency, Vol. 24 (Springer Science & Business Media, 2003). A Proof of Theorem 1 In this section, we present a proof of Theorem 1, which we restate here for clarity. Theorem 1.Consider the generating setR= ra,r−1 a 2n−1 a=1 and the potential Φ(w) = inv(π) + 2ν(w), ν(w) = #{c∈[2n−1] : ∆ c(w) =−1},(4...

View on Pith 2003

Discussion

Disagree with the review, or know something it missed? Leave a comment, highlight any passage above to comment on it, or challenge this review formally.

[1] [24]

B. Casas, P. Braccia, ´E. Gouzien, M. Cerezo, and D. Garc´ ıa-Mart´ ın, “Matchgate synthesis via clifford matchgates andTgates”, arXiv preprint arXiv:2602.05425 (2026)

View on Pith arXiv 2026

[2] [1]

M. A. Nielsen and I. L. Chuang,Quantum computation and quantum information(Cambridge University Press, Cambridge, 2000)

View on Pith 2000

[3] [2]

A. G. Fowler, M. Mariantoni, J. M. Martinis, and A. N. Cleland, “Surface codes: towards practical large-scale quantum computation”, Physical Review A86, 032324 (2012)

View on Pith 2012

[4] [3]

D. Litinski, “A Game of Surface Codes: Large-Scale Quantum Computing with Lattice Surgery”, Quantum3, 128 (2019). 15

View on Pith 2019

[5] [4]

J. van de Wetering and M. Amy, “Optimising quantum circuits is generally hard”, arXiv preprint arXiv:2310.05958 (2023)

View on Pith Pith review arXiv 2023

[6] [5]

´E. Gouzien and N. Sangouard, “Provably optimal exact gate synthesis from a discrete gate set”, arXiv preprint arXiv:2503.15452 (2025)

View on Pith Pith review arXiv 2025

[7] [6]

K. Matsumoto and K. Amano, “Representation of quantum circuits with clifford andπ/8 gates”, arXiv preprint arXiv:0806.3834 (2008)

View on Pith Pith review arXiv 2008

[8] [7]

B. Giles and P. Selinger, “Remarks on matsumoto and amano’s normal form for single-qubit clifford+ t operators”, arXiv preprint arXiv:1312.6584 (2013)

View on Pith Pith review arXiv 2013

[9] [8]

V. Kliuchnikov, D. Maslov, and M. Mosca, “Asymptotically optimal approximation of single qubit unitaries by clifford and t circuits using a constant number of ancillary qubits”, Physical Review Letters110, 190502 (2013)

View on Pith 2013

[10] [9]

N. J. Ross and P. Selinger, “Optimal ancilla-free Clifford+T approximation of z-rotations”, Quantum Info. Comput.16, 901–953 (2016)

View on Pith 2016

[11] [10]

P. Selinger,Exact and approximate synthesis of quantum circuits

View on Pith

[12] [11]

V. Kliuchnikov, K. Lauter, R. Minko, A. Paetznick, and C. Petit, “Shorter quantum circuits via single-qubit gate approximation”, Quantum7, 1208 (2023)

View on Pith 2023

[13] [12]

S. Yamamoto and N. Yoshioka, “Pygridsynth: a fast numerical tool for ancilla-free clifford+ t synthesis”, arXiv preprint arXiv:2604.21333 (2026)

View on Pith Pith review arXiv 2026

[14] [13]

S. Yamamoto, H. Hamaguchi., and J. Lapeyre,Pygridsynth

View on Pith

[15] [14]

H. Morisaki, K. Sano, and S. Akibue, “Optimal ancilla-free clifford+ t synthesis for general single-qubit unitaries”, arXiv preprint arXiv:2510.05816 (2025)

View on Pith arXiv 2025

[16] [15]

D. Maslov, “Linear depth stabilizer and quantum fourier transformation circuits with no auxiliary qubits in finite-neighbor quantum architectures”, Physical Review A76, 052310 (2007)

View on Pith 2007

[17] [16]

D. Maslov and M. Roetteler, “Shorter stabilizer circuits via bruhat decomposition and quan- tum circuit transformations”, IEEE Transactions on Information Theory64, 4729–4738 (2018)

View on Pith 2018

[18] [17]

S. Bravyi, R. Shaydulin, S. Hu, and D. Maslov, “Clifford circuit optimization with templates and symbolic pauli gates”, Quantum5, 580 (2021)

View on Pith 2021

[19] [18]

S. Bravyi and D. Maslov, “Hadamard-free circuits expose the structure of the clifford group”, IEEE Transactions on Information Theory67, 4546 (2021)

View on Pith 2021

[20] [19]

S. Bravyi, J. A. Latone, and D. Maslov, “6-qubit optimal clifford circuits”, npj Quantum Information8, 79 (2022)

View on Pith 2022

[21] [20]

T. Peham, N. Brandl, R. Kueng, R. Wille, and L. Burgholzer, “Depth-optimal synthesis of clif- ford circuits with sat solvers”, 2023 IEEE International Conference on Quantum Computing and Engineering (QCE)1, 802 (2023)

View on Pith 2023

[22] [21]

A. Acuaviva, A. Acuaviva, and P. Acuaviva, “Cnot-distance is np-complete under all-to-all connectivity”, arXiv preprint arXiv:2608.03825 (2026)

View on Pith Pith review arXiv 2026

[23] [22]

C. Li and J. Guan, “Vanilla exact synthesis of cnot circuits is np-hard”, arXiv preprint arXiv:2609.04160 (2026)

View on Pith Pith review arXiv 2026

[24] [23]

L. L. Keller and R. K¨ ueng, “(a variant of) clifford circuit synthesis is np-complete”, arXiv preprint arXiv:2610.02029 (2026). 16

View on Pith Pith review arXiv 2026

[25] [25]

M. Oszmaniec and Z. Zimboras, “Universal extensions of restricted classes of quantum oper- ations”, Physical Review Letters119, 220502 (2017)

View on Pith 2017

[26] [26]

S. Bravyi and A. Kitaev, “Universal quantum computation with ideal clifford gates and noisy ancillas”, Phys. Rev. A71, 022316 (2005)

View on Pith 2005

[27] [27]

K. Wan, W. J. Huggins, J. Lee, and R. Babbush, “Matchgate Shadows for Fermionic Quantum Simulation”, Communications in Mathematical Physics404, 629 (2023)

View on Pith 2023

[28] [28]

V. Heyraud, H. Chomet, and J. Tilly, “Unified framework for matchgate classical shadows”, npj Quantum Information11, 65 (2025)

View on Pith 2025

[29] [29]

M. West, M. Cerezo, and M. Larocca, “Particle-preserving fermionic shadows with mode- independent sample complexity”, arXiv preprint arXiv:2606.27254 (2026)

View on Pith Pith review arXiv 2026

[30] [30]

J. Helsen, S. Nezami, M. Reagor, and M. Walter, “Matchgate benchmarking: scalable bench- marking of a continuous family of many-qubit gates”, Quantum6, 657 (2022)

View on Pith 2022

[31] [31]

J. Carrasco, M. Langer, A. Neven, and B. Kraus, “Gaining confidence on the correct realiza- tion of arbitrary quantum computations”, Physical Review Research6, L032074 (2024)

View on Pith 2024

[32] [32]

A. Portik, O. K´ alm´ an, T. Monz, and Z. Zimboras, “Clifford volume and free fermion volume: complementary scalable benchmarks for quantum computers”, arXiv preprint arXiv:2512.19413 (2025)

View on Pith Pith review arXiv 2025

[33] [33]

M. Oszmaniec, N. Dangniam, M. E. Morales, and Z. Zimboras, “Fermion Sampling: A Robust Quantum Computational Advantage Scheme Using Fermionic Linear Optics and Magic Input States”, PRX Quantum3, 020328 (2022)

View on Pith 2022

[34] [34]

R. C. Lyndon and P. E. Schupp,Combinatorial group theory(Springer, 2001)

View on Pith 2001

[35] [35]

T. Miltzow, L. Narins, Y. Okamoto, G. Rote, A. Thomas, and T. Uno, “Approximation and hardness for token swapping”, Algorithms-ESA 2016, Proc. 24th Annual European Sympo- sium on Algorithms, Aarhus, 2016, Leibniz International Proceedings in Informatics (LIPIcs) (2016)

View on Pith 2016

[36] [36]

A. Javadi-Abhari, M. Treinish, K. Krsulich, C. J. Wood, J. Lishman, J. Gacon, S. Martiel, P. D. Nation, L. S. Bishop, A. W. Cross, et al., “Quantum computing with qiskit”, arXiv preprint arXiv:2405.08810 (2024)

View on Pith Pith review arXiv 2024

[37] [37]

Qiskit contributors,Qiskit: an open-source framework for quantum computing, 2023

View on Pith 2023

[38] [38]

S. Sivarajah, S. Dilkes, A. Cowtan, W. Simmons, A. Edgington, and R. Duncan, “T|ket>: a retargetable compiler for NISQ devices”, Quantum Science and Technology6, 014003 (2020)

View on Pith 2020

[39] [39]

S. B. Bravyi and A. Y. Kitaev, “Fermionic quantum computation”, Annals of Physics298, 210–226 (2002)

View on Pith 2002

[40] [40]

F. Verstraete and J. I. Cirac, “Mapping local hamiltonians of fermions to local hamiltonians of spins”, Journal of Statistical Mechanics: Theory and Experiment2005, P09012–P09012 (2005)

View on Pith 2005

[41] [41]

Z. Jiang, A. Kalev, W. Mruczkiewicz, and H. Neven, “Optimal fermion-to-qubit mapping via ternary trees with applications to reduced quantum states learning”, Quantum4, 276 (2020)

View on Pith 2020

[42] [42]

J. Alicea, Y. Oreg, G. Refael, F. Von Oppen, and M. P. Fisher, “Non-abelian statistics and topological quantum information processing in 1d wire networks”, Nature Physics7, 412–417 (2011). 17

View on Pith 2011

[43] [43]

O. Aichholzer, E. D. Demaine, M. Korman, J. Lynch, A. Lubiw, Z. Mas´ arov´ a, M. Rudoy, V. V. Williams, and N. Wein, “Hardness of token swapping on trees”, In 30th Annual European Symposium on Algorithms (ESA 2022). Leibniz International Proceedings in Informatics244, 3 (2022)

View on Pith 2022

[44] [44]

E. Knill, “Fermionic Linear Optics and Matchgates”, arXiv preprint arXiv:quant-ph/0108033 (2001)

View on Pith Pith review arXiv 2001

[45] [45]

B. M. Terhal and D. P. DiVincenzo, “Classical simulation of noninteracting-fermion quantum circuits”, Physical Review A65, 032325 (2002)

View on Pith 2002

[46] [46]

D. P. DiVincenzo and B. M. Terhal, “Fermionic linear optics revisited”, Foundations of Physics 35, 1967 (2005)

View on Pith 2005

[47] [47]

I. D. Kivlichan, J. McClean, N. Wiebe, C. Gidney, A. Aspuru-Guzik, G. K.-L. Chan, and R. Babbush, “Quantum simulation of electronic structure with linear depth and connectivity”, Physical Review Letters120, 110501 (2018)

View on Pith 2018

[48] [48]

F. Arute, K. Arya, R. Babbush, D. Bacon, J. C. Bardin, R. Barends, S. Boixo, M. Broughton, B. B. Buckley, D. A. Buell, et al., “Hartree-fock on a superconducting qubit quantum com- puter”, Science369, 1084–1089 (2020)

View on Pith 2020

[49] [49]

J. M. Arrazola, O. Di Matteo, N. Quesada, S. Jahangiri, A. Delgado, and N. Killoran, “Uni- versal quantum circuits for quantum chemistry”, Quantum6, 742 (2022)

View on Pith 2022

[50] [50]

F. Verstraete, J. I. Cirac, and J. I. Latorre, “Quantum circuits for strongly correlated quantum systems”, Physical Review A79, 032316 (2009)

View on Pith 2009

[51] [51]

B. Kraus, “Compressed quantum simulation of the ising model”, Physical Review Letters 107, 250503 (2011)

View on Pith 2011

[52] [52]

A. Cervera-Lierta, “Exact ising model simulation on a quantum computer”, Quantum2, 114 (2018)

View on Pith 2018

[53] [53]

Z. Jiang, K. J. Sung, K. Kechedzhi, V. N. Smelyanskiy, and S. Boixo, “Quantum algorithms to simulate many-body physics of correlated fermions”, Physical Review Applied9, 044036 (2018)

View on Pith 2018

[54] [54]

P.-L. Dallaire-Demers, J. Romero, L. Veis, S. Sim, and A. Aspuru-Guzik, “Low-depth circuit ansatz for preparing correlated fermionic states on a quantum computer”, Quantum Science and Technology4, 045005 (2019)

View on Pith 2019

[55] [55]

A. Sopena, M. H. Gordon, D. Garc´ ıa-Mart´ ın, G. Sierra, and E. L´ opez, “Algebraic Bethe Circuits”, Quantum6, 796 (2022)

View on Pith 2022

[56] [56]

R. Ruiz, A. Sopena, M. H. Gordon, G. Sierra, and E. L´ opez, “The bethe ansatz as a quantum circuit”, Quantum8, 1356 (2024)

View on Pith 2024

[57] [57]

R. Ruiz, A. Sopena, B. Pozsgay, and E. L´ opez, “Efficient eigenstate preparation in an inte- grable model with hilbert space fragmentation”, arXiv preprint arXiv:2411.15132 (2024)

View on Pith arXiv 2024

[58] [58]

E. K¨ okc¨ u, T. Steckmann, Y. Wang, J. Freericks, E. F. Dumitrescu, and A. F. Kemper, “Fixed depth hamiltonian simulation via cartan decomposition”, Physical Review Letters 129, 070501 (2022)

View on Pith 2022

[59] [59]

E. K¨ okc¨ u, D. Camps, L. B. Oftelie, J. K. Freericks, W. A. de Jong, R. Van Beeumen, and A. F. Kemper, “Algebraic compression of quantum circuits for hamiltonian evolution”, Physical Review A105, 032420 (2022). 18

View on Pith 2022

[60] [60]

L. G. Valiant, “Quantum computers that can be simulated classically in polynomial time”, in Proceedings of the thirty-third annual acm symposium on theory of computing (2001), pp. 114–123

View on Pith 2001

[61] [61]

S. Bravyi, “Lagrangian representation for fermionic linear optics”, Quantum Info. Comput. 5, 216–238 (2005)

View on Pith 2005

[62] [62]

R. Jozsa and A. Miyake, “Matchgates and classical simulation of quantum circuits”, Proceed- ings of the Royal Society A: Mathematical, Physical and Engineering Sciences464, 3089–3106 (2008)

View on Pith 2008

[63] [63]

R. Jozsa, B. Kraus, A. Miyake, and J. Watrous, “Matchgate and space-bounded quantum computations are equivalent”, Proceedings of the Royal Society A: Mathematical, Physical and Engineering Sciences466, 809 (2010)

View on Pith 2010

[64] [64]

S. Ramelow, A. Fedrizzi, A. M. Steinberg, and A. White, “Matchgate quantum computing and non-local process analysis”, New Journal of Physics12, 083027 (2010)

View on Pith 2010

[65] [65]

D. J. Brod and E. F. Galvao, “Extending matchgates into universal quantum computation”, Physical Review A84, 022310 (2011)

View on Pith 2011

[66] [66]

D. J. Brod and A. M. Childs, “The computational power of matchgates and the xy interaction on arbitrary graphs”, Quantum Information and Computation14, 901 (2014)

View on Pith 2014

[67] [67]

D. J. Brod, “Efficient classical simulation of matchgate circuits with generalized inputs and measurements”, Physical Review A93, 062332 (2016)

View on Pith 2016

[68] [68]

A. Zhao, N. C. Rubin, and A. Miyake, “Fermionic Partial Tomography via Classical Shadows”, Physical Review Letters127, 110504 (2021)

View on Pith 2021

[69] [69]

N. L. Diaz, D. Garc´ ıa-Mart´ ın, S. Kazi, M. Larocca, and M. Cerezo, “Showcasing a barren plateau theory beyond the dynamical lie algebra”, arXiv preprint arXiv:2310.11505 (2023)

View on Pith Pith review arXiv 2023

[70] [70]

A. A. Mele and Y. Herasymenko, “Efficient Learning of Quantum States Prepared With Few Fermionic Non-Gaussian Gates”, PRX Quantum6, 010319 (2025)

View on Pith 2025

[71] [71]

M. Stroeks, D. Lenterman, B. Terhal, and Y. Herasymenko, “Solving free fermion problems on a quantum computer”, arXiv preprint arXiv:2409.04550 (2024)

View on Pith arXiv 2024

[72] [72]

P. Braccia, N. Diaz, M. Larocca, M. Cerezo, and D. Garc´ ıa-Mart´ ın, “Optimal haar random fermionic linear optics circuits”, arXiv preprint arXiv:2505.24212 (2025)

View on Pith Pith review arXiv 2025

[73] [73]

P. Sierant, T. X., and P. S. Tarabunga, “Theory of the matchgate commutant”, arXiv preprint arXiv:2603.12392 (2026)

View on Pith arXiv 2026

[74] [74]

P. Braccia, N. Diaz, M. Larocca, M. Cerezo, and D. Garc´ ıa-Mart´ ın, “The commutant of fermionic gaussian unitaries”, arXiv preprint arXiv:2603.19210 (2026)

View on Pith arXiv 2026

[75] [75]

M. Lastres and S. Moudgalya, “Geometry of free fermion commutants”, arXiv preprint arXiv:2604.05031 (2026)

View on Pith Pith review arXiv 2026

[76] [76]

M. West, S. Y. Chang, L. Coffman, M. Larocca, and M. Cerezo, “Practical fermionic shadows enabled by improved sample-complexity bounds”, arXiv preprint arXiv:2609.40173 (2026)

View on Pith Pith review arXiv 2026

[77] [77]

M. West and M. Larocca, “Fermionic gaussianity can be tested with mode-independent sample-complexity”, arXiv preprint arXiv:2610.02050 (2026)

View on Pith Pith review arXiv 2026

[78] [78]

T. Guaita, L. Hackl, and T. Quella, “Representation theory of gaussian unitary transforma- tions for bosonic and fermionic systems”, arXiv preprint arXiv:2409.11628 (2024). 19

View on Pith Pith review arXiv 2024

[79] [79]

A. Mitra, M. J. Martin, G. W. Biedermann, A. M. Marino, P. M. Poggi, and I. H. Deutsch, “Robust mølmer-sørensen gate for neutral atoms using rapid adiabatic rydberg dressing”, Physical Review A101, 030301 (2020)

View on Pith 2020

[80] [80]

R. Bl¨ umel, N. Grzesiak, N. Pisenti, K. Wright, and Y. Nam, “Power-optimal, stabilized en- tangling gate between trapped-ion qubits”, npj Quantum Information7, 147 (2021)

View on Pith 2021

[81] [81]

A. Bjorner and F. Brenti,Combinatorics of coxeter groups(Springer, 2005)

View on Pith 2005

[82] [82]

D. Gonz´ alez-Cuadra, D. Bluvstein, M. Kalinowski, R. Kaubruegger, N. Maskara, P. Naldesi, T. V. Zache, A. M. Kaufman, M. D. Lukin, H. Pichler, et al., “Fermionic quantum processing with programmable neutral atom arrays”, Proceedings of the National Academy of Sciences 120, e2304294120 (2023)

View on Pith 2023

[83] [83]

P. Diaconis,Group representations in probability and statistics, Vol. 11 (Institute of mathe- matical statistics Hayward, CA, 1988)

View on Pith 1988

[84] [84]

N. Maskara, M. Kalinowski, D. Gonzalez-Cuadra, and M. D. Lukin, “Fast simulation of fermions with reconfigurable qubits”, arXiv preprint arXiv:2509.08898 (2025)

View on Pith Pith review arXiv 2025

[85] [85]

N. Constantinides, J. Yu, D. Devulapalli, A. Fahimniya, L. Schaeffer, A. M. Childs, M. J. Gullans, A. Schuckert, and A. V. Gorshkov, “Low-depth fermion routing without ancillas”, arXiv preprint arXiv:2510.05099 (2025)

View on Pith arXiv 2025

[86] [86]

M. West, M. Cerezo, and M. Larocca, “Strong matchgate designs in nearly optimal depth”, arXiv preprint arXiv:2609.26677 (2026)

View on Pith Pith review arXiv 2026

[87] [87]

F. Brenti, V. Reiner, and Y. Roichman, “Alternating subgroups of coxeter groups”, arXiv preprint math/0702177 (2007)

View on Pith Pith review arXiv 2007

[88] [88]

A. Schrijver,Combinatorial optimization: polyhedra and efficiency, Vol. 24 (Springer Science & Business Media, 2003). A Proof of Theorem 1 In this section, we present a proof of Theorem 1, which we restate here for clarity. Theorem 1.Consider the generating setR= ra,r−1 a 2n−1 a=1 and the potential Φ(w) = inv(π) + 2ν(w), ν(w) = #{c∈[2n−1] : ∆ c(w) =−1},(4...

View on Pith 2003