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:1710.09025 · Physical review. E

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

Amin Barzegar, Christopher A. Pattison, Wenlong Wang, Helmut G. Katzgraber

Published Nov 21, 2018• 30 citations
arXivHTMLPDF

Abstract

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.

DOI
10.1103/physreve.98.053308

Related papers

BatchTNMC: Efficient sampling of two-dimensional spin glasses using tensor network Monte Carlo

Tao Chen, Jingtong Zhang, Liu, Jing +2 more

Efficient sampling of two-dimensional statistical physics systems remains a central challenge in computational statistical physics. Traditional Markov chain Monte Carlo (MCMC) methods, including cluster algorithms, provide only partial solutions, as their efficiency collapses for large systems in the presence of frustration and quenched disorder. The recently proposed Tensor Network Monte Carlo (TNMC) method offers a promising alternative, yet its original implementation suffers from inefficiencies due to the lack of scalable parallel sampling. In this work, we introduce BatchTNMC, a GPU-optimized and parallelized implementation of TNMC tailored for large-scale simulations of two-dimensional spin glasses. By leveraging batch processing and parallel sampling across multiple disorder realizations, our implementation achieves speedups of up to five orders of magnitude compared with the original serial scheme. Benchmarking on two-dimensional spin glasses demonstrates dramatic gains in efficiency: for instance, on a single GPU, BatchTNMC concurrently produces 1000 uncorrelated and unbiased samples across 1000 disorder realizations on $1024\times 1024$ lattices in just 3.3 hours, with an acceptance probability of 37%. These results establish BatchTNMC as a scalable and powerful computational framework for the study of two-dimensional disordered spin glass systems.

arXiv:2509.19006•Sep 23, 2025•7 citations

Optimization by quantum annealing: Lessons from hard satisfiability problems

Demian A. Battaglia, Giuseppe E. Santoro, Erio Tosatti

The path integral Monte Carlo simulated quantum annealing algorithm is applied to the optimization of a large hard instance of the random satisfiability problem (N = 10,000). The dynamical behavior of the quantum and the classical annealing are compared, showing important qualitative differences in the way of exploring the complex energy landscape of the combinatorial optimization problem. At variance with the results obtained for the Ising spin glass and for the traveling salesman problem, in the present case the linear-schedule quantum annealing performance is definitely worse than classical annealing. Nevertheless, a quantum cooling protocol based on field-cycling and able to outperform standard classical simulated annealing over short time scales is introduced.

arXiv:cond-mat/0502468•Physical Review E•Jun 29, 2005•111 citations

Spin Glass Patch Planting

Wenlong Wang, Salvatore Mandrà, Helmut G. Katzgraber

In this paper, we propose a patch planting method for creating arbitrarily large spin glass instances with known ground states. The scaling of the computational complexity of these instances with various block numbers and sizes is investigated and compared with random instances using population annealing Monte Carlo and the quantum annealing DW2X machine. The method can be useful for benchmarking tests for future generation quantum annealing machines, classical and quantum mechanical optimization algorithms.

•Jan 1, 2016•0 citations

Quantum Monte Carlo annealing with multi-spin dynamics

Guglielmo Mazzola, Matthias Troyer

Abstract We introduce a novel simulated quantum annealing (SQA) algorithm which employs a multispin quantum fluctuation operator. At variance with the usual transverse field, short-range two-spin flip interactions are included in the driver Hamiltonian. A Quantum Monte Carlo algorithm, capable of efficiently simulating large disordered systems, is described and tested. A first application to SQA, on a random square lattice Ising spin glass, reveals that the multi-spin driver Hamiltonian improves upon the usual transverse field. This work paves the way for more systematic investigations using multi-spin quantum fluctuations on a broader range of problems.

arXiv:1701.08775•Journal of Statistical Mechanics Theory and Experiment•May 1, 2017•7 citations

Population annealing with topological defect driven nonlocal updates for spin systems with quenched disorder

David Cirauqui, Miguel Ángel García-March, J. R. M. Saavedra +2 more

Population annealing, one of the currently state-of-the-art algorithms for solving spin-glass systems, sometimes finds hard disorder instances for which its equilibration quality at each temperature step is severely damaged. In such cases, therefore, one cannot be sure about having reached the true ground state without vastly increasing the computational resources. In this work, we seek to overcome this problem by proposing a quantum-inspired modification of population annealing. Here we focus on the three-dimensional random plaquette gauge model, whose ground-state energy problem seems to be much harder to solve than that of the standard spin-glass Edwards-Anderson model. In analogy to the toric code, by allowing single bond flips we let the system explore nonphysical states, effectively expanding the configurational space by introducing topological defects that are then annealed through an additional field parameter. The dynamics of these defects allow for the effective realization of nonlocal cluster moves, potentially easing the equilibration process. We study the performance of this method in three-dimensional random plaquette gauge model lattices of various sizes, and we compare it against population annealing. With that we conclude that the newly introduced nonlocal moves are able to improve the equilibration of the lattices, in some cases being superior to a normal population annealing algorithm with a computational resource investment that is 16 times higher.

arXiv:2307.16087•Physical review. B./Physical review. B•Apr 11, 2024•1 citation

Quantum annealing of an Ising spin-glass by Green’s function Monte Carlo

Lorenzo Stella, Giuseppe E. Santoro

We present an implementation of quantum annealing (QA) via lattice Green's function Monte Carlo (GFMC), focusing on its application to the Ising spin glass in transverse field. In particular, we study whether or not such a method is more effective than the path-integral Monte Carlo- (PIMC) based QA, as well as classical simulated annealing (CA), previously tested on the same optimization problem. We identify the issue of importance sampling, i.e., the necessity of possessing reasonably good (variational) trial wave functions, as the key point of the algorithm. We performed GFMC-QA runs using such a Boltzmann-type trial wave function, finding results for the residual energies that are qualitatively similar to those of CA (but at a much larger computational cost), and definitely worse than PIMC-QA. We conclude that, at present, without a serious effort in constructing reliable importance sampling variational wave functions for a quantum glass, GFMC-QA is not a true competitor of PIMC-QA.

arXiv:cond-mat/0608420•Physical Review E•Mar 13, 2007•19 citations
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.
Efficient sampling of two-dimensional statistical physics systems remains a central challenge in computational statistical physics. Traditional Markov chain Monte Carlo (MCMC) methods, including cluster algorithms, provide only partial solutions, as their efficiency collapses for large systems in the presence of frustration and quenched disorder. The recently proposed Tensor Network Monte Carlo (TNMC) method offers a promising alternative, yet its original implementation suffers from inefficiencies due to the lack of scalable parallel sampling. In this work, we introduce BatchTNMC, a GPU-optimized and parallelized implementation of TNMC tailored for large-scale simulations of two-dimensional spin glasses. By leveraging batch processing and parallel sampling across multiple disorder realizations, our implementation achieves speedups of up to five orders of magnitude compared with the original serial scheme. Benchmarking on two-dimensional spin glasses demonstrates dramatic gains in efficiency: for instance, on a single GPU, BatchTNMC concurrently produces 1000 uncorrelated and unbiased samples across 1000 disorder realizations on 1024×10241024\times 10241024×1024 lattices in just 3.3 hours, with an acceptance probability of 37%. These results establish BatchTNMC as a scalable and powerful computational framework for the study of two-dimensional disordered spin glass systems.
The path integral Monte Carlo simulated quantum annealing algorithm is applied to the optimization of a large hard instance of the random satisfiability problem (N = 10,000). The dynamical behavior of the quantum and the classical annealing are compared, showing important qualitative differences in the way of exploring the complex energy landscape of the combinatorial optimization problem. At variance with the results obtained for the Ising spin glass and for the traveling salesman problem, in the present case the linear-schedule quantum annealing performance is definitely worse than classical annealing. Nevertheless, a quantum cooling protocol based on field-cycling and able to outperform standard classical simulated annealing over short time scales is introduced.
In this paper, we propose a patch planting method for creating arbitrarily large spin glass instances with known ground states. The scaling of the computational complexity of these instances with various block numbers and sizes is investigated and compared with random instances using population annealing Monte Carlo and the quantum annealing DW2X machine. The method can be useful for benchmarking tests for future generation quantum annealing machines, classical and quantum mechanical optimization algorithms.
Abstract We introduce a novel simulated quantum annealing (SQA) algorithm which employs a multispin quantum fluctuation operator. At variance with the usual transverse field, short-range two-spin flip interactions are included in the driver Hamiltonian. A Quantum Monte Carlo algorithm, capable of efficiently simulating large disordered systems, is described and tested. A first application to SQA, on a random square lattice Ising spin glass, reveals that the multi-spin driver Hamiltonian improves upon the usual transverse field. This work paves the way for more systematic investigations using multi-spin quantum fluctuations on a broader range of problems.
Population annealing, one of the currently state-of-the-art algorithms for solving spin-glass systems, sometimes finds hard disorder instances for which its equilibration quality at each temperature step is severely damaged. In such cases, therefore, one cannot be sure about having reached the true ground state without vastly increasing the computational resources. In this work, we seek to overcome this problem by proposing a quantum-inspired modification of population annealing. Here we focus on the three-dimensional random plaquette gauge model, whose ground-state energy problem seems to be much harder to solve than that of the standard spin-glass Edwards-Anderson model. In analogy to the toric code, by allowing single bond flips we let the system explore nonphysical states, effectively expanding the configurational space by introducing topological defects that are then annealed through an additional field parameter. The dynamics of these defects allow for the effective realization of nonlocal cluster moves, potentially easing the equilibration process. We study the performance of this method in three-dimensional random plaquette gauge model lattices of various sizes, and we compare it against population annealing. With that we conclude that the newly introduced nonlocal moves are able to improve the equilibration of the lattices, in some cases being superior to a normal population annealing algorithm with a computational resource investment that is 16 times higher.
We present an implementation of quantum annealing (QA) via lattice Green's function Monte Carlo (GFMC), focusing on its application to the Ising spin glass in transverse field. In particular, we study whether or not such a method is more effective than the path-integral Monte Carlo- (PIMC) based QA, as well as classical simulated annealing (CA), previously tested on the same optimization problem. We identify the issue of importance sampling, i.e., the necessity of possessing reasonably good (variational) trial wave functions, as the key point of the algorithm. We performed GFMC-QA runs using such a Boltzmann-type trial wave function, finding results for the residual energies that are qualitatively similar to those of CA (but at a much larger computational cost), and definitely worse than PIMC-QA. We conclude that, at present, without a serious effort in constructing reliable importance sampling variational wave functions for a quantum glass, GFMC-QA is not a true competitor of PIMC-QA.