Challenges
Datasets
Workspaces
Papers
Discussions
Leaderboard
Log inSign up
Challenges
Datasets
Workspaces
Papers
Discussions
Leaderboard
Blog
Job Board
Q3AS

© 2026 Aqora Quantum S.A.S.

TermsPrivacyLegal Notice

arXiv:2109.07358 · Physical review. B./Physical review. B

Fermion sampling made more efficient

Haoran Sun, Jie Zou, Xiaopeng Li

Published Jan 11, 2023• 4 citations
arXivHTMLPDF

Abstract

Fermion sampling is to generate probability distribution of a many-body Slater-determinant wave function, which is termed ``determinantal point process'' in statistical analysis. For its inherently embedded Pauli exclusion principle, its application reaches beyond simulating fermionic quantum many-body physics to constructing machine learning models for diversified datasets. Here we propose a fermion sampling algorithm, which has a polynomial time complexity---quadratic in the fermion number and linear in the system size. This algorithm is about $100%$ more efficient in computation time than the best known algorithms. In sampling the corresponding marginal distribution, our algorithm has a more drastic improvement, achieving a scaling advantage. We demonstrate its power on several test applications, including sampling fermions in a many-body system and a machine learning task of text summarization, and confirm its improved computation efficiency over other methods by counting floating-point operations.

DOI
10.1103/physrevb.107.035119

Related papers

Particle-preserving fermionic shadows with mode-independent sample complexity

Maxwell West, M. Cerezo, Martin Larocca

We consider the problem of learning expectation values of particle-preserving operators with respect to an unknown $η$-particle $n$-mode fermionic state via classical shadows. Our main application is to estimating overlaps with arbitrary Slater determinant states: While it is known that such overlaps can, in the average case, be learnt to a fixed additive precision with a constant number of samples, the best-known worst case bound is $\mathcal{O}(\sqrt n \log n)$; here we improve this to $\mathcal{O}(η\logη)$, achieving a mode-independent sample cost. Our procedure is also computationally efficient, requiring only classical post-processing which for a generic dense orbital runs in time $\mathcal{O}(nη^2)$. For the task of estimating the expectation value of a general particle-preserving quadratic fermionic observable $h$, we prove a sample complexity bound of $\mathcal{O}(η\|h_0\|_2^2)$, where $h_0$ is the traceless component of $h$; the associated classical post-processing scales as $\mathcal{O}(n^2η)$. Finally, we discuss implementation of the required randomization: in a first-quantized encoding, approximate unitary designs give circuit depths polylogarithmic in the number of modes, contrasting with linear-depth requirements for nearest-neighbor second-quantized matchgate implementations. On the technical side, our proof reduces the extremal shadow variance to harmonic analysis on the AIII symmetric space $U(n)/(U(η)\times U(n-η))$ and evaluates the resulting integral using techniques from the theories of Jacobi ensembles and orthogonal polynomials, in a calculation which may be of independent interest.

quant-pharXiv:2606.27254•Jun 26, 2026•10 citations

Learning the closest Slater determinant

Nisarga Paul, Haimeng Zhao, David D. Dai

Learning compact, interpretable descriptions of quantum many-body states is an important task in quantum science. We study the task of learning the Slater determinant with maximum fidelity to an arbitrary fermionic many-body state, with motivation from both Hartree-Fock methods and agnostic tomography. Given an $n$-fermion wavefunction built from $m$ fermionic modes, we provide classical and quantum algorithms returning a Slater determinant with fidelity within $\varepsilon$ of maximal in time $m^{\text{poly}(n,1/\varepsilon)}$. We prove matching hardness lower bounds, assuming standard complexity conjectures, along some parameter axes. Given access to quantum copies, we prove this can be accomplished with $\text{poly}(m,n,1/\varepsilon)$ copies of $ρ$. We also show that above a fidelity of $2/3$ any stationary point is the unique global maximum while below $2/3$ the optimization landscape can have spurious stationary points, and hence $2/3$ marks a transition point in the optimization landscape for this problem. We apply the algorithm to the Fermi-Hubbard model, extracting the closest Slater determinant from neural quantum state solutions. Together, our results provide algorithmic tools with provable guarantees in understanding fermionic many-body systems with classical or quantum simulation.

quant-pharXiv:2607.20623•Jul 24, 2026•2 citations

Implementing advanced trial wave functions in fermion quantum Monte Carlo via stochastic sampling

Zhi-Yu Xiao, Tao Xiang, Zixiang Lu +2 more

We introduce an efficient approach to implement correlated many-body trial wave functions in auxiliary-field quantum Monte Carlo (AFQMC). To control the sign/phase problem in AFQMC, a constraint is derived from an exact gauge condition but is typically imposed approximately through a trial wave function or trial density matrix, whose quality can affect the accuracy of the method. Furthermore, the trial wave function can also affect the efficiency through importance sampling. The most natural form of the trial wave function has been single Slater determinants or their linear combinations. More sophisticated forms, for example, with the inclusion of a Jastrow factor or other explicit correlations, have been challenging to use, and their implementation is often assumed to require a quantum computer. In this work, we demonstrate that a large class of correlated wave functions, written in the general form of multi-dimensional integrals over hidden or auxiliary variables times Slater determinants, can be implemented as a trial wave function by coupling the random walkers to a generalized Metropolis sampling. We discuss the fidelity of AFQMC with stochastically sampled trial wave functions, which are relevant to both quantum and classical algorithms. We illustrate the method and show that an efficient implementation can be achieved, which preserves the computational scaling of AFQMC. We test our method in molecules under bond stretching and in transition metal diatomics. Significant improvements are seen in both accuracy and efficiency over typical trial wave functions, and the method yields total ground-state energies systematically within chemical accuracy. The method can be useful for incorporating other advanced wave functions, for example, neural quantum state wave functions optimized from machine learning techniques, or for other forms of fermion quantum Monte Carlo.

arXiv:2505.18519•The Journal of Chemical Physics•Oct 22, 2025•7 citations

Sample-efficient learning of quantum many-body systems

Anurag Anshu, Srinivasan Arunachalam, Tomotaka Kuwahara +1 more

We study the problem of learning the Hamiltonian of a quantum many-body system given samples from its Gibbs (thermal) state. The classical analog of this problem, known as learning graphical models or Boltzmann machines, is a well-studied question in machine learning and statistics. In this work, we give the first sample-efficient algorithm for the quantum Hamiltonian learning problem. In particular, we prove that polynomially many samples in the number of particles (qudits) are necessary and sufficient for learning the parameters of a spatially local Hamiltonian in l_2-norm. Our main contribution is in establishing the strong convexity of the log-partition function of quantum many-body systems, which along with the maximum entropy estimation yields our sample-efficient algorithm. Classically, the strong convexity for partition functions follows from the Markov property of Gibbs distributions. This is, however, known to be violated in its exact form in the quantum case. We introduce several new ideas to obtain an unconditional result that avoids relying on the Markov property of quantum systems, at the cost of a slightly weaker bound. In particular, we prove a lower bound on the variance of quasi-local operators with respect to the Gibbs state, which might be of independent interest. Our work paves the way toward a more rigorous application of machine learning techniques to quantum many-body problems.

Annual Symposium on Foundations of Computer Science•Nov 1, 2020•12 citations

Thermal-Drift Sampling: Generating Thermal Ensembles for Learning Many-Body Systems

Jiyu Jiang, Mingrui Jing, Jizhe Lai +2 more

Thermal equilibrium states of many-body Hamiltonians are essential for probing quantum chaos, finite-temperature phases of matter, and training quantum machine learning models, yet generating large collections of such states across different Hamiltonians remains costly with existing methods. We introduce a powerful operation, the quantum thermal-drift channel, to construct a measurement-controlled sampling algorithm that autonomously generates thermal states together with their system Hamiltonians as labels for general physical models. We prove that our algorithm is efficient: the total gate count scales polynomially with system size and quadratically with inverse temperature, providing the first polynomial resource bound for random thermal state generation. We characterize the distribution of sampled Hamiltonians as a normal distribution reweighted by partition functions, which quantifies a trade-off between sampling accuracy and effective label range. Level-spacing statistics computed from sampled thermal states of a 2D transverse-field Ising model show a crossover to Wigner-Dyson universality, confirming that the sampler captures nontrivial chaotic correlations. Finally, a variational quantum classifier trained on the generated dataset achieves near-optimal accuracy in predicting Hamiltonian properties of unseen states. These results establish a scalable, quantum-native route for thermodynamic simulation and labeled quantum data generation in many-body systems.

quant-pharXiv:2602.05912•Feb 6, 2026•0 citations

Efficient Sampling for Many-Body Fermionic Non-Gaussianity

Ryota Matsuda, Masahiro Hoshino, Yuto Ashida

Fermionic non-Gaussianity is a key resource for universal quantum computation, and its behavior in quantum many-body systems has attracted growing interest. Recently, a convolution-based measure, which we call the magic Rényi entropy (MRE), has been proposed as a resource measure of non-Gaussianity, but its evaluation is limited to small systems due to the computational cost growing exponentially with system size. In this work, we develop a perfect-sampling method to calculate the second-order MRE from matrix product states (MPSs). Our method uses a bounded estimator to control sampling fluctuations and a recursive sweep to draw the samples directly from the input MPS, which allows us to generate each sample with $\mathcal O(nD^3)$ time, where $n$ and $D$ denote the number of modes and MPS bond dimension, respectively. We benchmark our method on the XXZ chain with up to $128$ sites, demonstrating that the MRE captures intricate higher-order correlations at large scales, which are inaccessible to covariance-based measures. These results provide a computational tool that quantitatively evaluates many-body fermionic non-Gaussianity by accounting for higher-order correlations.

quant-pharXiv:2610.03492•Oct 5, 2026•0 citations
Fermion sampling is to generate probability distribution of a many-body Slater-determinant wave function, which is termed ``determinantal point process'' in statistical analysis. For its inherently embedded Pauli exclusion principle, its application reaches beyond simulating fermionic quantum many-body physics to constructing machine learning models for diversified datasets. Here we propose a fermion sampling algorithm, which has a polynomial time complexity---quadratic in the fermion number and linear in the system size. This algorithm is about 100100%100 more efficient in computation time than the best known algorithms. In sampling the corresponding marginal distribution, our algorithm has a more drastic improvement, achieving a scaling advantage. We demonstrate its power on several test applications, including sampling fermions in a many-body system and a machine learning task of text summarization, and confirm its improved computation efficiency over other methods by counting floating-point operations.
We consider the problem of learning expectation values of particle-preserving operators with respect to an unknown ηηη-particle nnn-mode fermionic state via classical shadows. Our main application is to estimating overlaps with arbitrary Slater determinant states: While it is known that such overlaps can, in the average case, be learnt to a fixed additive precision with a constant number of samples, the best-known worst case bound is O(nlog⁡n)\mathcal{O}(\sqrt n \log n)O(n​logn); here we improve this to O(ηlog⁡η)\mathcal{O}(η\logη)O(ηlogη), achieving a mode-independent sample cost. Our procedure is also computationally efficient, requiring only classical post-processing which for a generic dense orbital runs in time O(nη2)\mathcal{O}(nη^2)O(nη2). For the task of estimating the expectation value of a general particle-preserving quadratic fermionic observable hhh, we prove a sample complexity bound of O(η∥h0∥22)\mathcal{O}(η\|h_0\|_2^2)O(η∥h0​∥22​), where h0h_0h0​ is the traceless component of hhh; the associated classical post-processing scales as O(n2η)\mathcal{O}(n^2η)O(n2η). Finally, we discuss implementation of the required randomization: in a first-quantized encoding, approximate unitary designs give circuit depths polylogarithmic in the number of modes, contrasting with linear-depth requirements for nearest-neighbor second-quantized matchgate implementations. On the technical side, our proof reduces the extremal shadow variance to harmonic analysis on the AIII symmetric space U(n)/(U(η)×U(n−η))U(n)/(U(η)\times U(n-η))U(n)/(U(η)×U(n−η)) and evaluates the resulting integral using techniques from the theories of Jacobi ensembles and orthogonal polynomials, in a calculation which may be of independent interest.
Learning compact, interpretable descriptions of quantum many-body states is an important task in quantum science. We study the task of learning the Slater determinant with maximum fidelity to an arbitrary fermionic many-body state, with motivation from both Hartree-Fock methods and agnostic tomography. Given an nnn-fermion wavefunction built from mmm fermionic modes, we provide classical and quantum algorithms returning a Slater determinant with fidelity within ε\varepsilonε of maximal in time mpoly(n,1/ε)m^{\text{poly}(n,1/\varepsilon)}mpoly(n,1/ε). We prove matching hardness lower bounds, assuming standard complexity conjectures, along some parameter axes. Given access to quantum copies, we prove this can be accomplished with poly(m,n,1/ε)\text{poly}(m,n,1/\varepsilon)poly(m,n,1/ε) copies of ρρρ. We also show that above a fidelity of 2/32/32/3 any stationary point is the unique global maximum while below 2/32/32/3 the optimization landscape can have spurious stationary points, and hence 2/32/32/3 marks a transition point in the optimization landscape for this problem. We apply the algorithm to the Fermi-Hubbard model, extracting the closest Slater determinant from neural quantum state solutions. Together, our results provide algorithmic tools with provable guarantees in understanding fermionic many-body systems with classical or quantum simulation.
We introduce an efficient approach to implement correlated many-body trial wave functions in auxiliary-field quantum Monte Carlo (AFQMC). To control the sign/phase problem in AFQMC, a constraint is derived from an exact gauge condition but is typically imposed approximately through a trial wave function or trial density matrix, whose quality can affect the accuracy of the method. Furthermore, the trial wave function can also affect the efficiency through importance sampling. The most natural form of the trial wave function has been single Slater determinants or their linear combinations. More sophisticated forms, for example, with the inclusion of a Jastrow factor or other explicit correlations, have been challenging to use, and their implementation is often assumed to require a quantum computer. In this work, we demonstrate that a large class of correlated wave functions, written in the general form of multi-dimensional integrals over hidden or auxiliary variables times Slater determinants, can be implemented as a trial wave function by coupling the random walkers to a generalized Metropolis sampling. We discuss the fidelity of AFQMC with stochastically sampled trial wave functions, which are relevant to both quantum and classical algorithms. We illustrate the method and show that an efficient implementation can be achieved, which preserves the computational scaling of AFQMC. We test our method in molecules under bond stretching and in transition metal diatomics. Significant improvements are seen in both accuracy and efficiency over typical trial wave functions, and the method yields total ground-state energies systematically within chemical accuracy. The method can be useful for incorporating other advanced wave functions, for example, neural quantum state wave functions optimized from machine learning techniques, or for other forms of fermion quantum Monte Carlo.
We study the problem of learning the Hamiltonian of a quantum many-body system given samples from its Gibbs (thermal) state. The classical analog of this problem, known as learning graphical models or Boltzmann machines, is a well-studied question in machine learning and statistics. In this work, we give the first sample-efficient algorithm for the quantum Hamiltonian learning problem. In particular, we prove that polynomially many samples in the number of particles (qudits) are necessary and sufficient for learning the parameters of a spatially local Hamiltonian in l_2-norm. Our main contribution is in establishing the strong convexity of the log-partition function of quantum many-body systems, which along with the maximum entropy estimation yields our sample-efficient algorithm. Classically, the strong convexity for partition functions follows from the Markov property of Gibbs distributions. This is, however, known to be violated in its exact form in the quantum case. We introduce several new ideas to obtain an unconditional result that avoids relying on the Markov property of quantum systems, at the cost of a slightly weaker bound. In particular, we prove a lower bound on the variance of quasi-local operators with respect to the Gibbs state, which might be of independent interest. Our work paves the way toward a more rigorous application of machine learning techniques to quantum many-body problems.
Thermal equilibrium states of many-body Hamiltonians are essential for probing quantum chaos, finite-temperature phases of matter, and training quantum machine learning models, yet generating large collections of such states across different Hamiltonians remains costly with existing methods. We introduce a powerful operation, the quantum thermal-drift channel, to construct a measurement-controlled sampling algorithm that autonomously generates thermal states together with their system Hamiltonians as labels for general physical models. We prove that our algorithm is efficient: the total gate count scales polynomially with system size and quadratically with inverse temperature, providing the first polynomial resource bound for random thermal state generation. We characterize the distribution of sampled Hamiltonians as a normal distribution reweighted by partition functions, which quantifies a trade-off between sampling accuracy and effective label range. Level-spacing statistics computed from sampled thermal states of a 2D transverse-field Ising model show a crossover to Wigner-Dyson universality, confirming that the sampler captures nontrivial chaotic correlations. Finally, a variational quantum classifier trained on the generated dataset achieves near-optimal accuracy in predicting Hamiltonian properties of unseen states. These results establish a scalable, quantum-native route for thermodynamic simulation and labeled quantum data generation in many-body systems.
Fermionic non-Gaussianity is a key resource for universal quantum computation, and its behavior in quantum many-body systems has attracted growing interest. Recently, a convolution-based measure, which we call the magic Rényi entropy (MRE), has been proposed as a resource measure of non-Gaussianity, but its evaluation is limited to small systems due to the computational cost growing exponentially with system size. In this work, we develop a perfect-sampling method to calculate the second-order MRE from matrix product states (MPSs). Our method uses a bounded estimator to control sampling fluctuations and a recursive sweep to draw the samples directly from the input MPS, which allows us to generate each sample with O(nD3)\mathcal O(nD^3)O(nD3) time, where nnn and DDD denote the number of modes and MPS bond dimension, respectively. We benchmark our method on the XXZ chain with up to 128128128 sites, demonstrating that the MRE captures intricate higher-order correlations at large scales, which are inaccessible to covariance-based measures. These results provide a computational tool that quantitatively evaluates many-body fermionic non-Gaussianity by accounting for higher-order correlations.