{"id":"arxiv/2609.40187","url":"https://arxiv.org/abs/2609.40187","tags":["quant-ph"],"score":0,"title":"Fast classical simulation algorithms for free-fermion dynamics with magic input","domain":"quant-ph","source":"arxiv","authors":["Jiwon Heo","Oliver Reardon-Smith","Michał Oszmaniec","Zoltán Zimborás","Changhun Oh"],"reviews":0,"subject":"quant-ph","summary":"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(2^n)$ per sample, without any multiplicative polynomial…","category":"research","comments":0,"disputed":false,"division":"physics","mentions":0,"discussed":0,"published":"2026-09-30","reactions":{}}