arXiv:2609.40187
Fast classical simulation algorithms for free-fermion dynamics with magic input
Jiwon Heo, Oliver Reardon-Smith, Michał Oszmaniec, Zoltán Zimborás, Changhun Oh
Abstract
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 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.
AI Summary
The paper studies how non-Gaussian product inputs change the classical cost of simulating free-fermion (matchgate) dynamics, distinguishing exact sampling, exact observable evaluation, and additive-error estimation. For $n$ copies of the four-mode state $(|1100\rangle+|0011\rangle)/\sqrt2$, it gives exact occupation-number samplers costing $O(n^4+2^n)$ for particle-number-preserving dynamics and $O(n^5+2^n)$ for general Gaussian dynamics, in an exact-arithmetic model. A covariant quantum instrument generates simpler conditional inputs; Bayesian recovery reconstructs the parent sample. Shared determinant/Pfaffian calculations remove polynomial prefactors from the exponential contribution. The worst-case active sampler additionally groups instrument histories and replaces averaged endpoints by Gaussian ensembles. The passive sampler benchmarks a trapped-ion experiment’s noninteracting regime with 28 particles in 56 modes, including Wilson-loop observables. For arbitrary definite-parity, constant-size product blocks, a subset-based dynamic program computes weight-$k$ Majorana expectations exactly in $O(n^2+nK2^K)$ time, where $K=\min\{k,2M-k\}$. This makes logarithmic effective weight polynomial-time computable. For arbitrary pure even-parity four-mode blocks, a covariance-adapted Gaussian decomposition and compression bound yield a transition-amplitude estimator with second moment at most one. Number correlators of unrestricted weight, output probabilities, and occupation marginals follow with additive error $\epsilon$ and failure probability $\delta$ in $O(n^3\epsilon^{-2}\log(2/\delta))$ time after circuit preprocessing. Sampling remains exponential and is restricted to the specified magic input. Additive probability estimation does not imply efficient sampling or relative accuracy for exponentially small probabilities. Optimal complexity, hardness beyond logarithmic effective weight, and extensions to larger input blocks remain open.
Written by gpt-6.1-sol from the paper's full text. Automated: it can be wrong.
- Comments
- 16 pages, 5 figures