Fermionic Gaussian states (FGSs) and the associated matchgate circuits play a central role in quantum information theory and condensed matter physics. Despite being possibly highly entangled, they can still be efficiently simulated on classical computers. We address the question of how to optimally create such states when using matchgate circuits acting on product states. To this end, we derive lower bounds on the number of gates required to prepare an arbitrary pure FGS: We establish both an asymptotic bound on the minimal gate count over general nearest-neighbor gate sets and an exact bound for circuits composed solely of matchgates. We present explicit algorithms whose constructions saturate these bounds, thereby proving their optimality. We furthermore determine when an FGS can be prepared with a circuit of any given depth, and derive an algorithm that constructs such a circuit whenever this condition is satisfied, either exactly or approximately. Our results have direct applications to (approximate) state preparation and to disentangling procedures. Moreover, we introduce a new classical simulation algorithm for matchgate circuits, based entirely on manipulating the generating circuits of the FGSs. Finally, we briefly study an extension of our framework for
t-doped Gaussian states and circuits.
Fermionic Gaussian circuits can be simulated efficiently on a classical computer, but become universal when supplemented with non-Gaussian operations. Similar to stabilizer circuits augmented with non-stabilizer resources, these non-Gaussian circuits can be simulated classically using rank- or extent-based methods. These methods decompose non-Gaussian states or operations into Gaussian ones, with runtimes that scale polynomially with measures of non-Gaussianity such as the rank and the extent -- quantities that typically grow exponentially with the number of non-Gaussian resources. Current fermionic rank- and extent-based simulators have mostly been limited to Gaussian circuits with magic-state injection. Extending them to mixed states and non-unitary channels has been hindered by the lack of known extent-optimized decompositions for physically relevant gates and noisy channels. In this work, we address this gap. First, we derive analytic decompositions for key non-Gaussian gates and channels, including decompositions for arbitrary two-qubit fermionic gates which are provably optimal for diagonal gates or those acting on Jordan-Wigner-adjacent qubit pairs. Second, we show that stochastic Pauli noise can reduce the effective extent of non-Gaussian rotation gates, but that fermionic magic is substantially more robust to such noise than stabilizer magic. Finally, we demonstrate how these decompositions can accelerate classical sampling from the output distribution of a quantum circuit. This involves a generalization of existing sparsification methods, previously limited to convex-unitary channels, to circuits involving intermediate measurements and feed-forward. Our decompositions also yield speedups for emulating noisy Pauli rotations with quasiprobability simulators in the large-angle/arbitrary-strength-noise and small-angle/low-noise parameter regimes.
We present a classical simulation method for fermionic quantum systems which, without loss of generality, can be represented by parity-preserving circuits made of two-qubit gates in a brick-wall structure. We map such circuits to a fermionic tensor network and introduce a novel decomposition of non-Matchgate gates into a Gaussian fermionic tensor and a residual quartic term, inspired by interacting fermionic systems. The quartic term is independent of the specific gate, which allows us to precompute intermediate results independently of the exact circuit structure and leads to significant speedups when compared to other methods. Our decomposition suggests a natural perturbative expansion which can be turned into an algorithm to compute measurement outcomes and observables to finite accuracy when truncating at some order of the expansion. For particle number conserving gates, our decomposition features a unique truncation cutoff reducing the computational effort for high precision calculations. Our algorithm significantly lowers resource requirements for simulating parity-preserving circuits while retaining high accuracy, making it suitable for simulations of interacting systems in quantum chemistry and material science. Lastly, we discuss how our algorithm compares to other classical simulation methods for fermionic quantum systems.
Fermionic Gaussian states are the workhorse reference states for qubit-based quantum simulation of fermionic systems, yet existing certification protocols either proceed via fidelity estimation, leading to suboptimal sample complexity in the target precision
ε, only apply to Haar-typical states, or require adaptive measurements on a large fraction of qubits. We give an adaptive protocol that certifies any
d-mode pure fermionic Gaussian state using
O(d2ε−1) copies, single-qubit measurements with only one qubit measured adaptively per copy, and
O(d3) classical processing time per copy. The
ε−1 dependence is optimal for the certification problem, even among strategies using entangled measurements. The sample complexity is controlled by the spectral gap of a
d↔d−2 down-up walk---a Markov chain studied in the theory of high-dimensional expanders, equivalent to a two-site Glauber dynamics in statistical physics---relating certification efficiency to relaxation time to equilibrium. The worst-case bound is tight for this protocol and is attained by physically relevant states, including ground states of the fully dimerized Su-Schrieffer-Heeger (SSH) chain and BCS pair states. In contrast, numerics up to
d=14 suggest that
O(dε−1) copies suffice to certify Haar-typical Gaussian states, a factor of
d improvement over the worst-case bound. Finally, because the bound depends only on the target's computational-basis distribution, the protocol extends to efficiently phase-dressed states---states obtained by injecting an efficiently computable diagonal phase to Gaussian states---with the same sample complexity. The class includes a continuous family of four-mode non-Gaussian magic states for matchgate computation.
Matchgates are a family of two-qubit gates associated with noninteracting fermions. They are classically simulatable if acting only on nearest neighbors but become universal for quantum computation if we relax this restriction or use swap gates [Jozsa and Miyake, Proc. R. Soc. A 464, 3089 (2008)]. We generalize this result by proving that any nonmatchgate parity-preserving unitary is capable of extending the computational power of matchgates into universal quantum computation. We identify the single local invariant of parity-preserving unitaries responsible for this, and discuss related results in the context of fermionic systems.
Fermionic Gaussian states describe free fermions and underlie the mean-field picture of matter, from metals to superconductors; they are also efficiently simulable on classical computers. Departures from Gaussianity -- the correlations produced by interactions -- are therefore what make a fermionic system hard to simulate classically and useful for quantum computation, analogous to the role of magic in stabilizer-based quantum computation. Yet detecting and quantifying such non-Gaussianity at scale has remained challenging. Here we introduce practical tests and witnesses of fermionic non-Gaussianity built on fermionic antiflatness, a measure derived from the two-point covariance matrix. We estimate it with two protocols -- a two-copy Bell measurement and a single-copy scheme using commuting Majorana bilinears -- that determine whether a state is Gaussian or far from it at lower measurement cost than existing approaches, using only operations native to fault-tolerant hardware. For mixed states, a purity-corrected witness certifies non-Gaussianity and remains robust under strong noise; running it on the IQM quantum processor, we find that noise can both reduce and enhance non-Gaussianity. Finally, we show that preparing pseudorandom fermionic states requires extensive non-Gaussianity. Together, these tools enable the study and certification of non-Gaussian fermionic resources on present-day quantum devices.