In this paper we introduce and formalize Substochastic Monte Carlo (SSMC) algorithms. These algorithms, originally intended to be a better classical foil to quantum annealing than simulated annealing, prove to be worthy optimization algorithms in their own right. In SSMC, a population of walkers is initialized according to a known distribution on an arbitrary search space and varied into the solution of some optimization problem of interest. The first argument of this paper shows how an existing classical algorithm, "Go-With-The-Winners" (GWW), is a limiting case of SSMC when restricted to binary search and particular driving dynamics. Although limiting to GWW, SSMC is more general. We show that (1) GWW can be efficiently simulated within the SSMC framework, (2) SSMC can be exponentially faster than GWW, (3) by naturally incorporating structural information, SSMC can exponentially outperform the quantum algorithm that first inspired it, and (4) SSMC exhibits desirable search features in general spaces. Our approach combines ideas from genetic algorithms (GWW), theoretical probability (Fleming-Viot processes), and quantum computing. Not only do we demonstrate that SSMC is often more efficient than competing algorithms, but we also hope that our results connecting these disciplines will impact each independently. An implemented version of SSMC has previously enjoyed some success as a competitive optimization algorithm for Max- $k$ -SAT.In this paper we introduce and formalize Substochastic Monte Carlo (SSMC) algorithms. These algorithms, originally intended to be a better classical foil to quantum annealing than simulated annealing, prove to be worthy optimization algorithms in their own right. In SSMC, a population of walkers is initialized according to a known distribution on an arbitrary search space and varied into the solution of some optimization problem of interest. The first argument of this paper shows how an existing classical algorithm, "Go-With-The-Winners" (GWW), is a limiting case of SSMC when restricted to binary search and particular driving dynamics. Although limiting to GWW, SSMC is more general. We show that (1) GWW can be efficiently simulated within the SSMC framework, (2) SSMC can be exponentially faster than GWW, (3) by naturally incorporating structural information, SSMC can exponentially outperform the quantum algorithm that first inspired it, and (4) SSMC exhibits desirable search features in general spaces. Our approach combines ideas from genetic algorithms (GWW), theoretical probability (Fleming-Viot processes), and quantum computing. Not only do we demonstrate that SSMC is often more efficient than competing algorithms, but we also hope that our results connecting these disciplines will impact each independently. An implemented version of SSMC has previously enjoyed some success as a competitive optimization algorithm for Max-$k$-SAT.

arXiv:1704.09014Apr 28, 20175 citations

Hamiltonian Monte Carlo enhanced by exact diagonalization

Anonymous, Martina Gisti, David J. Luitz +2 more

Strongly correlated fermionic systems are of great interest in condensed matter physics and numerical methods are indispensable tools for their study. However, existing approaches such as exact diagonalization (ED) and stochastic quantum Monte Carlo methods each suffer from fundamental limitations: ED is hindered by exponential scaling in system size, while Monte Carlo methods are plagued by sign problems and long autocorrelation times. These limitations restrict the accessible parameter space and developing algorithms that efficiently alleviate them remains a central challenge in computational physics. In this work, we propose a algorithm that combines ED and Hamiltonian Monte Carlo (HMC) to simulate two-dimensional (2D) arrays of coupled quantum wires, modeled as interacting fermionic Hubbard chains. We demonstrate how our hybrid implementation of HMC, which we dub H 2 MC , outperforms either method alone across several key simulation facets. When compared to pure ED, H 2 MC has a much more favorable computational scaling, which allows us to push simulations to much larger 2D arrays. H 2 MC also greatly alleviates the sign problem and reduces autocorrelation times when compared to pure HMC formulations utilizing either real or imaginary auxiliary fields. Our formalism demonstrates how complementary strengths of seemingly disparate methods can be leveraged to enable feasible simulations in an extended parameter space.Strongly correlated fermionic systems are of great interest in condensed matter physics and numerical methods are indispensable tools for their study. However, existing approaches such as exact diagonalization (ED) and stochastic quantum Monte Carlo methods each suffer from fundamental limitations: ED is hindered by exponential scaling in system size, while Monte Carlo methods are plagued by sign problems and long autocorrelation times. These limitations restrict the accessible parameter space and developing algorithms that efficiently alleviate them remains a central challenge in computational physics. In this work, we propose a algorithm that combines ED and Hamiltonian Monte Carlo (HMC) to simulate two-dimensional (2D) arrays of coupled quantum wires, modeled as interacting fermionic Hubbard chains. We demonstrate how our hybrid implementation of HMC, which we dub H 2 MC , outperforms either method alone across several key simulation facets. When compared to pure ED, H 2 MC has a much more favorable computational scaling, which allows us to push simulations to much larger 2D arrays. H 2 MC also greatly alleviates the sign problem and reduces autocorrelation times when compared to pure HMC formulations utilizing either real or imaginary auxiliary fields. Our formalism demonstrates how complementary strengths of seemingly disparate methods can be leveraged to enable feasible simulations in an extended parameter space.

arXiv:2603.17788Physical review. B./Physical review. BAug 13, 20260 citations

Bernstein Numbers and Lower Bounds for the Monte Carlo Error

Robert J. Kunsch

Springer proceedings in mathematics & statisticsJan 1, 20166 citations

Benchmark of the Polynomial Expansion Monte Carlo Method

Hiroaki Ishizuka

Springer thesesJan 1, 20150 citations

k

-SAT.