# FFT-Accelerated Auxiliary Variable MCMC for Fermionic Lattice Models: A Determinant-Free Approach with O(Nlog N) Complexity

arXiv: https://arxiv.org/abs/2510.13866 · HTML: https://mlsanity.com/paper/2510.13866/

## Key facts

- No citing papers in the map yet (data through 14 Oct 2026).
- Builds on 0 of its 34 references that are in the map.
- First posted on arXiv 13 Oct 2025.

## Abstract (arXiv)

We introduce a Markov Chain Monte Carlo (MCMC) algorithm that dramatically accelerates the simulation of quantum many-body systems, a grand challenge in computational science. State-of-the-art methods for these problems are severely limited by O(N3) computational complexity. Our method avoids this bottleneck, achieving near-linear O(N log N) scaling per sweep. Our approach samples a joint probability measure over two coupled variable sets: (1) particle trajectories of the fundamental fermions, and (2) auxiliary variables that decouple fermion interactions. The key innovation is a novel transition kernel for particle trajectories formulated in the Fourier domain, revealing the transition probability as a convolution that enables massive acceleration via the Fast Fourier Transform (FFT). The auxiliary variables admit closed-form, factorized conditional distributions, enabling efficient exact Gibbs sampling update. We validate our algorithm on benchmark quantum physics problems, accurately reproducing known theoretical results and matching traditional O(N3) algorithms on 32× 32 lattice simulations at a fraction of the wall-clock time, empirically demonstrating N log N scaling. By reformulating a long-standing physics simulation problem in machine learning language, our work provides a powerful tool for large-scale probabilistic inference and opens avenues for physics-inspired generative models.