The classical cost of simulating free-fermion (matchgate) circuits depends on both the input state and the computational task. We develop classical algorithms for circuits with non-Gaussian inputs, addressing exact sampling and both additive-error and exact estimation of expectation values. For inputs consisting of
n copies of the four-mode magic state, we give exact sampling algorithms, generalizing the Clifford and Clifford algorithm for Boson sampling, for passive and active free-fermion dynamics with worst-case arithmetic cost
O(2n) per sample, without any multiplicative polynomial prefactor. The passive algorithm enables an exact simulation of the non-interacting regime of a recent trapped-ion experiment. We also extend recently developed additive-error estimation of number correlators and related observables from passive to active dynamics with runtime polynomial in
n and the inverse additive-error, for input states formed by products of
n four-mode even parity states. Our estimator uses a Gaussian-state decomposition adapted to each sampled state to control its second moment. This includes estimation of individual output probabilities. Finally, we show that for even-parity product inputs composed of constant-size blocks, expectation values of Majorana monomials of logarithmic weight can be computed exactly in polynomial time, improving on prior Majorana propagation-style algorithms with quasi-polynomial runtime. The exact algorithm processes the input blocks by dynamic programming, sharing calculations across subsets of Majorana factors. Our suite of algorithms provide classical benchmarks for fermionic quantum simulations across a broad spectrum of computational tasks.
Recently developed simulation algorithms for strongly correlated lattice fermions are reviewed. The simulation methods which we describe are based on the path-integral formalism. Basic algorithms for auxiliary-field methods as well as prescriptions for reducing the minus-sign problem are presented. As an important application, ground state properties of the Hubbard model are discussed in the light of recent simulation results. Clarified so far, important features of antiferromagnetic transitions, metal-insulator transitions and pairing mechanisms in strongly correlated systems are summarized. Recent applications of the fermion Monte Carlo method to other fermion models with degenerate orbitals such as the d - p model are also reviewed. Heavy fermion systems, exhibiting a variety of crossovers such as the temperature crossover between the intersite antiferromagnetic correlation and the local singlet formation, are also discussed. Pairing mechanisms examined numerically in a variety of extended lattice models are briefly sketched.