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

Physica A Statistical Mechanics and its Applications

Optimization of Monte Carlo simulations

Hans-Otto Heuer

Published Apr 1, 1992• 2 citations
Publisher
DOI
10.1016/0378-4371(92)90029-p

Related papers

Diffusion Monte Carlo approach versus adiabatic computation for local Hamiltonians

Jacob Bringewatt, W. Dorland, Stephen P. Jordan +1 more

Most research regarding quantum adiabatic optimization has focused on stoquastic Hamiltonians, whose ground states can be expressed with only real non-negative amplitudes and thus for whom destructive interference is not manifest. This raises the question of whether classical Monte Carlo algorithms can efficiently simulate quantum adiabatic optimization with stoquastic Hamiltonians. Recent results have given counterexamples in which path-integral and diffusion Monte Carlo fail to do so. However, most adiabatic optimization algorithms, such as for solving MAX-$k$-SAT problems, use $k$-local Hamiltonians, whereas our previous counterexample for diffusion Monte Carlo involved $n$-body interactions. Here we present a 6-local counterexample which demonstrates that even for these local Hamiltonians there are cases where diffusion Monte Carlo cannot efficiently simulate quantum adiabatic optimization. Furthermore, we perform empirical testing of diffusion Monte Carlo on a standard well-studied class of permutation-symmetric tunneling problems and similarly find large advantages for quantum optimization over diffusion Monte Carlo.

arXiv:1709.03971•Physical Review A•Feb 15, 2018•12 citations

Tuning the generalized Hybrid Monte Carlo algorithm

Anthony D. Kennedy, Robert G. Edwards, H. Mino +1 more

arXiv:hep-lat/9509043•Nuclear Physics B - Proceedings Supplements•Mar 1, 1996•11 citations

Extending Monte Carlo samples

Bernard B. Beard

Nuclear Physics B - Proceedings Supplements•May 1, 2003•1 citation

Optimization of population annealing Monte Carlo for large-scale spin-glass simulations

Amin Barzegar, Christopher A. Pattison, Wenlong Wang +1 more

Population annealing Monte Carlo is an efficient sequential algorithm for simulating $k$-local Boolean Hamiltonians. Because of its structure, the algorithm is inherently parallel and therefore well suited for large-scale simulations of computationally hard problems. Here we present various ways of optimizing population annealing Monte Carlo using 2-local spin-glass Hamiltonians as a case study. We demonstrate how the algorithm can be optimized from an implementation, algorithmic accelerator, as well as scalable parallelization points of view. This makes population annealing Monte Carlo perfectly suited to study other frustrated problems such as pyrochlore lattices, constraint-satisfaction problems, as well as higher-order Hamiltonians commonly found in, e.g., topological color codes.

arXiv:1710.09025•Physical review. E•Nov 21, 2018•30 citations

Adiabatic optimization versus diffusion Monte Carlo methods

Michael Jarret, Stephen P. Jordan, Brad Lackey

Most experimental and theoretical studies of adiabatic optimization use stoquastic Hamiltonians, whose ground states are expressible using only real nonnegative amplitudes. This raises a question as to whether classical Monte Carlo methods can simulate stoquastic adiabatic algorithms with polynomial overhead. Here we analyze diffusion Monte Carlo algorithms. We argue that, based on differences between ${L}_{1}$ and ${L}_{2}$ normalized states, these algorithms suffer from certain obstructions preventing them from efficiently simulating stoquastic adiabatic evolution in generality. In practice however, we obtain good performance by introducing a method that we call Substochastic Monte Carlo. In fact, our simulations are good classical optimization algorithms in their own right, competitive with the best previously known heuristic solvers for MAX-$k$-SAT at $k=2,3,4$.

arXiv:1607.03389•Physical Review A•Oct 13, 2016•35 citations

Monte Carlo simulation with fluctuating boundary conditions

Martin Hasenbusch B

Physica A Statistical Mechanics and its Applications•Aug 1, 1993•34 citations
Most research regarding quantum adiabatic optimization has focused on stoquastic Hamiltonians, whose ground states can be expressed with only real non-negative amplitudes and thus for whom destructive interference is not manifest. This raises the question of whether classical Monte Carlo algorithms can efficiently simulate quantum adiabatic optimization with stoquastic Hamiltonians. Recent results have given counterexamples in which path-integral and diffusion Monte Carlo fail to do so. However, most adiabatic optimization algorithms, such as for solving MAX-kkk-SAT problems, use kkk-local Hamiltonians, whereas our previous counterexample for diffusion Monte Carlo involved nnn-body interactions. Here we present a 6-local counterexample which demonstrates that even for these local Hamiltonians there are cases where diffusion Monte Carlo cannot efficiently simulate quantum adiabatic optimization. Furthermore, we perform empirical testing of diffusion Monte Carlo on a standard well-studied class of permutation-symmetric tunneling problems and similarly find large advantages for quantum optimization over diffusion Monte Carlo.
Population annealing Monte Carlo is an efficient sequential algorithm for simulating kkk-local Boolean Hamiltonians. Because of its structure, the algorithm is inherently parallel and therefore well suited for large-scale simulations of computationally hard problems. Here we present various ways of optimizing population annealing Monte Carlo using 2-local spin-glass Hamiltonians as a case study. We demonstrate how the algorithm can be optimized from an implementation, algorithmic accelerator, as well as scalable parallelization points of view. This makes population annealing Monte Carlo perfectly suited to study other frustrated problems such as pyrochlore lattices, constraint-satisfaction problems, as well as higher-order Hamiltonians commonly found in, e.g., topological color codes.
Most experimental and theoretical studies of adiabatic optimization use stoquastic Hamiltonians, whose ground states are expressible using only real nonnegative amplitudes. This raises a question as to whether classical Monte Carlo methods can simulate stoquastic adiabatic algorithms with polynomial overhead. Here we analyze diffusion Monte Carlo algorithms. We argue that, based on differences between L1{L}_{1}L1​ and L2{L}_{2}L2​ normalized states, these algorithms suffer from certain obstructions preventing them from efficiently simulating stoquastic adiabatic evolution in generality. In practice however, we obtain good performance by introducing a method that we call Substochastic Monte Carlo. In fact, our simulations are good classical optimization algorithms in their own right, competitive with the best previously known heuristic solvers for MAX-kkk-SAT at k=2,3,4k=2,3,4k=2,3,4.