Matchgate circuits describe classically tractable dynamics in a physically relevant setting while nonetheless exhibiting features characteristic of complex quantum systems, such as high amounts of magic. This invites the broader question: to what extent are typical complexity measures saturated under trivial dynamics? Here, we address this by studying the behaviour of different Heisenberg-picture complexity measures in random matchgate ensembles. Our main technical contribution is a tractable and generalisible free-fermionic unitary Weingarten calculus formulated entirely in the Majorana basis. This method is tailored to computing moments of operators, and simplifies to a combinatorics problem which depends on the boundary conditions prescribed by a given operator functional. Using this framework, we derive closed-form expressions for the typical local-operator entanglement, operator stabiliser entropy, and higher-order out-of-time-ordered correlators. For extensive initial Majorana strings, both operator entanglement and stabiliser entropy obey volume laws, even though the underlying circuits remain classically simulable. Out-of-time-ordered correlators can likewise become exponentially small, showing that their late-time saturation value alone does not witness computational hardness and constituting a classically tractable example of emergent free independence. Finally, we relate these separations to operator resource theories, showing how operator entanglement beyond the Gaussian baseline lower-bounds the number of non-Gaussian gates in doped matchgate circuits. Our results present a practical toolbox for computing exact averages over random matchgates, while clarifying the distinction between quantum resources versus simulation complexity, and their dependence on the representation being exploited.
AI Summary
The paper asks how large Heisenberg-picture complexity measures can become under classically simulable free-fermionic dynamics. It studies Haar-random matchgate conjugation of a Majorana string of length $L$ on $N$ qubits, computing operator entanglement, operator stabiliser entropy, and an eight-point out-of-time-ordered correlator (OTOC).
The technical construction expresses replicated Majorana averages using orthogonal Weingarten calculus. Input symmetry and output antisymmetry select a single rectangular representation for any even replica number, reducing coefficients to signed counts of binary contingency tables. These counts are evaluated explicitly for four replicas; observable-specific boundary contractions then give exact finite-size formulas.
For extensive strings, the annealed Rényi-2 operator entanglement obeys a volume law. At the half-chain cut its largest density occurs at $L=N$, giving $2N\log_2(4-2\sqrt2)\simeq0.457N$, versus the maximum $N$. The operator stabiliser entropy approaches its sector maximum $\log_2\binom{2N}{L}$ within an $O(\log N)$ deficit. For fixed $L$, operator entanglement is bounded by $L$, whereas stabiliser entropy grows as $L\log_2N$. When both OTOC strings have length $N$, the averaged eight-point correlator decays on the scale $2^{-N}$, despite efficient sample-wise evaluation. A further bound, $\mathrm{LOE}^{(k)}\leq L+\kappa(\theta)t$, lower-bounds quartic non-Gaussian gate counts from excess entanglement.
The results concern global ensemble averages, not spatially resolved dynamics or equilibration times. Entropies are annealed lower bounds on mean entropies; concentration is not established. Explicit higher-replica evaluations, full free independence beyond the eight-point diagnostic, and particle-number-conserving ensembles remain open.
No sign of AI-generated textAI use disclosedOverclaims
AI tools were used to assist in simplifying final closed-form expressions, developing the proofs of the asymptotic formulas for the applications, and generating the plots visualising the analytic results.
Error found: The exact entropy expressions are annealed quantities, and although their volume-law scaling implies high-probability volume-law lower bounds, the paper does not establish that their precise values or LOE coefficients describe typical entropies.
Exponential decay of an ensemble-averaged eight-point OTOC alone does not establish emergent free independence, which requires additional moment conditions and, for a typical-sample interpretation, control of fluctuations.
Written by gpt-6.1-sol from the paper's full text. Automated: it can be wrong.
Comments
19 pages main + 16 pages appendix; many figures. Comments welcome!
Matchgate circuits describe classically tractable dynamics in a physically relevant setting while nonetheless exhibiting features characteristic of complex quantum systems, such as high amounts of magic. This invites the broader question: to what extent are typical complexity measures saturated under trivial dynamics? Here, we address this by studying the behaviour of different Heisenberg-picture complexity measures in random matchgate ensembles. Our main technical contribution is a tractable and generalisible free-fermionic unitary Weingarten calculus formulated entirely in the Majorana basis. This method is tailored to computing moments of operators, and simplifies to a combinatorics problem which depends on the boundary conditions prescribed by a given operator functional. Using this framework, we derive closed-form expressions for the typical local-operator entanglement, operator stabiliser entropy, and higher-order out-of-time-ordered correlators. For extensive initial Majorana strings, both operator entanglement and stabiliser entropy obey volume laws, even though the underlying circuits remain classically simulable. Out-of-time-ordered correlators can likewise become exponentially small, showing that their late-time saturation value alone does not witness computational hardness and constituting a classically tractable example of emergent free independence. Finally, we relate these separations to operator resource theories, showing how operator entanglement beyond the Gaussian baseline lower-bounds the number of non-Gaussian gates in doped matchgate circuits. Our results present a practical toolbox for computing exact averages over random matchgates, while clarifying the distinction between quantum resources versus simulation complexity, and their dependence on the representation being exploited.
The paper asks how large Heisenberg-picture complexity measures can become under classically simulable free-fermionic dynamics. It studies Haar-random matchgate conjugation of a Majorana string of length L on N qubits, computing operator entanglement, operator stabiliser entropy, and an eight-point out-of-time-ordered correlator (OTOC).
The technical construction expresses replicated Majorana averages using orthogonal Weingarten calculus. Input symmetry and output antisymmetry select a single rectangular representation for any even replica number, reducing coefficients to signed counts of binary contingency tables. These counts are evaluated explicitly for four replicas; observable-specific boundary contractions then give exact finite-size formulas.
For extensive strings, the annealed Rényi-2 operator entanglement obeys a volume law. At the half-chain cut its largest density occurs at L=N, giving 2Nlog2(4−22)≃0.457N, versus the maximum N. The operator stabiliser entropy approaches its sector maximum log2(L2N) within an O(logN) deficit. For fixed L, operator entanglement is bounded by L, whereas stabiliser entropy grows as Llog2N. When both OTOC strings have length N, the averaged eight-point correlator decays on the scale 2−N, despite efficient sample-wise evaluation. A further bound, LOE(k)≤L+κ(θ)t, lower-bounds quartic non-Gaussian gate counts from excess entanglement.
The results concern global ensemble averages, not spatially resolved dynamics or equilibration times. Entropies are annealed lower bounds on mean entropies; concentration is not established. Explicit higher-replica evaluations, full free independence beyond the eight-point diagnostic, and particle-number-conserving ensembles remain open.
Matchgate circuits realize free-fermion dynamics: they are efficiently classically simulable, yet cannot on their own generate the generic randomness required for universal computation or unitary design formation. We study a controlled route beyond this integrable limit by doping matchgate circuits with non-Gaussian gates-physically, the injection of fermionic interactions into an otherwise free system. Using the matchgate commutant framework, we obtain analytic control over unitary 2-design formation. For globally scrambled dynamics, the design problem maps exactly onto a classical birth-death Markov chain with an Ornstein-Uhlenbeck continuum limit, recasting the emergence of quantum randomness in terms of spectral gaps and mixing times and yielding rigorous bounds on the number of non-Gaussian gates needed for approximate 2-designs. These bounds hold for a broad class of parity-preserving non-Gaussian gates, independently of microscopic details, with numerics indicating that the same mechanism governs higher-order designs. Used as local building blocks in a glued-circuit architecture, they yield approximate parity-preserving 2-designs in polylogarithmic depth with a sparse non-Gaussian gate count, with implications for Page-like entanglement growth and fermionic classical-shadow protocols. Finally, locality reshapes this picture: in local brickwork dynamics, design formation is diffusion-limited and far slower. Our results establish doped matchgate circuits as a controlled, analytically tractable route from free fermions to interaction-generated quantum designs.
In quantum information theory and statistical physics, symmetries of multiple copies, or replicas, of a system play a pivotal role. For unitary ensembles, these symmetries are encoded in the replicated commutant: the algebra of operators commuting with the ensemble across k replicas. Determining the commutant is straightforward for the full unitary group, but remains a major obstacle for structured, computationally relevant circuit families. We solve this problem for matchgate circuits, which prepare fermionic Gaussian states on n qubits. Using a Majorana fermion representation, we show that operators coupling different system copies generate the orthogonal Lie algebra so(k), endowing the space of invariants with rich and tractable structure. This underlying symmetry decomposes the matchgate commutant into irreducible sectors, which we completely resolve via a Gelfand--Tsetlin construction. We provide an explicit orthonormal basis of the matchgate commutant for all k and n, together with a formula for its dimension that grows polynomially in n. Furthermore, we characterize the commutant of the Clifford--matchgate subgroup, showing that restricting to signed permutations of Majorana modes yields a commutant that qualitatively diverges from the matchgate case for k≥4 replicas. Ultimately, our orthonormal basis turns algebraic classification into a working toolbox. Using it, we derive closed-form expressions for matchgate twirling channels and a fermionic analogue of Weingarten calculus, the projector encoding all moments of the Gaussian state orbit, state and unitary frame potentials, the average nonstabilizerness of fermionic Gaussian states, a systematic hierarchy of non-Gaussianity measures, and a fermionic de Finetti theorem.
Free fermionic Gaussian, also known as matchgate, random circuits exhibit atypical behavior compared to generic interacting systems. They produce anomalously slow entanglement growth, characterized by diffusive scaling S(t)∼sqrt[t], and evolve into volume-law entangled states at late times, S∼N, which are highly unstable under measurements. Here, we investigate how doping such circuits with non-Gaussian resources (gates) restores entanglement structures of typical dynamics. We demonstrate that ballistic entanglement growth S(t)∼t is recovered after injecting an extensive total amount of non-Gaussian gates, which also restores Kardar-Parisi-Zhang fluctuations. When the evolution is perturbed with measurements, we uncover a measurement-induced phase transition between an area-law and a power-law entangled phase, S∼N^{α}, with α controlled by the doping. A genuine volume-law entangled phase is recovered only when non-Gaussian gates are injected at an extensive rate. Our findings bridge the dynamics of free and interacting fermionic systems, identifying non-Gaussianity as a key resource driving the emergence of nonintegrable behavior.
The local-operator entanglement (LOE) measures the classical simulability of a Heisenberg operator and is conjectured to witness many-body chaos in locally interacting systems. Using tools from free probability, we analytically compute its asymptotic value for Haar random dynamics for all Rényi indices. We find that to the first two orders in large dimension, for traceless operators it exactly reproduces the Page curve for random states. In contrast to higher-order out-of-time-ordered correlators (OTOCs), which depend on more complex operator correlations via free cumulants, the leading-order LOE is independent of the initial operator. \add{We detail exactly how these higher-order correlations are encoded in the coefficients of the finite-size corrections. Therefore, guided by our Haar result, we argue that the long-time value of the LOE entropies in chaotic systems is robust: they depend only on a simple sub-sector of the hierarchy of correlations encoded by the full Eigenstate Thermalization Hypothesis. Our results therefore provide a conceptual boundary between operator simulability and higher-order scrambling diagnostics.
Quantum resource theories have proved to be a systematic framework to characterize the classical simulation complexity of quantum systems. The original motivation of this thesis is to better understand two such resources, entanglement and fermionic non-Gaussianity, by characterizing their interplay in the Heisenberg picture. We start from the recent result that the entanglement of a unitarily evolved operator is always upper bounded by its non-stabilizerness, and we show that no analogous bound holds for non-Gaussianity. From our proof, the main lesson we learn is that, unlike Clifford unitaries, Gaussian unitaries can generate operator entanglement from an initial product operator. This suggests the main question of the present work: how much operator-space entanglement is generated, on average, by a random Gaussian unitary? We first show that, through the fermionic Choi–Jamiolkowski isomorphism, our problem can be reformulated in terms of Gaussian states alone. Building on this simplification, we characterize the average von Neumann operator-space entanglement entropy in two independent ways: numerically, by sampling Haar-random Gaussian evolutions, and analytically, by showing that the relevant spectrum follows a real Jacobi ensemble and solving it exactly in the thermodynamic limit with a Coulomb gas approach. The two results agree. The entropy grows extensively with the system size, and we summarize its behaviour in a family of Gaussian Page curves.
Claims of quantum advantage rest on the classical hardness of simulating quantum circuits. Magic, operator scrambling, anticoncentration, and non-Gaussianity for fermionic circuits are standard diagnostics of complex quantum dynamics. For pure states, some of these have been rigorously connected to classical simulability. Whether these diagnostics reliably track the limits of efficient classical simulation under noise remains unclear. Here, we show that in noisy Clifford+T and nearest-neighbour matchgate+SWAP circuits, dynamical diagnostics and classical simulability can separate in both directions. In particular, the diagnostics can remain nontrivial after classical simulation becomes efficient, or become trivial before known efficient classical algorithms apply. We trace this mismatch to the different statistical properties they probe: magic and scrambling depend on fourth-order statistics of the Pauli spectrum, whereas the simulation algorithms depend primarily on second-order moments, which local noise suppresses at different rates. Thus, dynamical diagnostics measured on a noisy quantum device do not by themselves constitute evidence for classical hardness.