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• 29 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•0 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

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•107 citations

Demonstrating real advantage of machine learning–enhanced Monte Carlo for combinatorial optimization

Luca Maria Del Bono, Federico Ricci‐Tersenghi, Francesco Zamponi

Combinatorial optimization problems are central to both practical applications and the development of optimization methods. While classical and quantum algorithms have been refined over decades, machine learning-assisted approaches are comparatively recent and have not yet consistently outperformed simple, state-of-the-art classical methods. Here, we focus on a class of Quadratic Unconstrained Binary Optimization problems, specifically the challenge of finding minimum energy configurations in three-dimensional Ising spin glasses. We use a Global Annealing Monte Carlo algorithm that integrates standard local moves with global moves proposed via machine learning. We show that local moves play a crucial role in achieving optimal performance. Benchmarking against Simulated Annealing and Population Annealing, we demonstrate that Global Annealing not only surpasses the performance of Simulated Annealing but also exhibits greater robustness than Population Annealing, maintaining effectiveness across problem hardness and system size without hyperparameter tuning. These results provide clear and robust evidence that a machine learning-assisted optimization method can exceed the capabilities of classical state-of-the-art techniques in a combinatorial optimization setting.

arXiv:2510.19544•Proceedings of the National Academy of Sciences•May 8, 2026•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
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.
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.
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.
Combinatorial optimization problems are central to both practical applications and the development of optimization methods. While classical and quantum algorithms have been refined over decades, machine learning-assisted approaches are comparatively recent and have not yet consistently outperformed simple, state-of-the-art classical methods. Here, we focus on a class of Quadratic Unconstrained Binary Optimization problems, specifically the challenge of finding minimum energy configurations in three-dimensional Ising spin glasses. We use a Global Annealing Monte Carlo algorithm that integrates standard local moves with global moves proposed via machine learning. We show that local moves play a crucial role in achieving optimal performance. Benchmarking against Simulated Annealing and Population Annealing, we demonstrate that Global Annealing not only surpasses the performance of Simulated Annealing but also exhibits greater robustness than Population Annealing, maintaining effectiveness across problem hardness and system size without hyperparameter tuning. These results provide clear and robust evidence that a machine learning-assisted optimization method can exceed the capabilities of classical state-of-the-art techniques in a combinatorial optimization setting.
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.