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.
A bstract Thermal properties of quantum fields at finite temperature are crucial to understanding strongly interacting matter and recent development in quantum computing has provided an alternative and promising avenue of study. In this work, we study thermal field theories involving only fermions using quantum algorithms. We first delve into the presentations of fermion fields via qubits on digital quantum computers alongside the quantum algorithms such as quantum imaginary time evolutions employed to evaluate thermal properties of generic quantum field theories. Specifically, we show numerical results such as the thermal distribution and the energy density of thermal field theories for Majorana fermions in 1+1 dimensions using quantum simulators. In addition to free field theory, we also study the effects of interactions resulting from coupling with a spatially homogeneous Majorana field. In both cases, we show analytically that thermal properties of the system can be described using phase-space distributions, and the quantum simulation results agree with analytical and semiclassical expectations. Our work is an important step to understand thermal fixed points, preparing for quantum simulation of thermalization in real time.