{"ID":2856176,"CreatedAt":"2026-06-01T04:54:23.091178241Z","UpdatedAt":"2026-06-01T04:54:23.091178241Z","DeletedAt":null,"paper_url":"https://arxiv.org/abs/2510.13866","arxiv_id":"2510.13866","title":"FFT-Accelerated Auxiliary Variable MCMC for Fermionic Lattice Models: A Determinant-Free Approach with $O(N\\log N)$ Complexity","abstract":"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(N^3)$ 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(N^3)$ algorithms on $32\\times 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.","short_abstract":"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(N^3)$ computational complexity. Our method avoids this bottleneck, achiev...","url_abs":"https://arxiv.org/abs/2510.13866","url_pdf":"https://arxiv.org/pdf/2510.13866v1","authors":"[\"Deqian Kong\",\"Shi Feng\",\"Jianwen Xie\",\"Ying Nian Wu\"]","published":"2025-10-13T07:57:21Z","proceeding":"cond-mat.str-el","tasks":"[\"cond-mat.str-el\",\"cs.AI\",\"cs.LG\",\"stat.ML\"]","methods":"[]","has_code":false}