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:2106.11645

Fast-update in self-learning algorithm for continuous-time quantum Monte Carlo

Ruixiao Cao, Synge Todo

Published Jun 22, 2021• 0 citations
arXivHTMLPDF

Abstract

We propose a novel technique for speeding up the self-learning Monte Carlo method applied to the single-site impurity model. For the case where the effective Hamiltonian is expressed by polynomial functions of differences of imaginary-time coordinate between vertices, we can remove the dependence of CPU time on the number of vertices, $n$, by saving and updating some coefficients for each insertion and deletion process. As a result, the total cost for a single-step update is drastically reduced from $O(nm)$ to $O(m^2)$ with $m$ being the order of polynomials in the effective Hamiltonian. Even for the existing algorithms, in which the absolute value is used instead of the difference as the variable of polynomial functions, we can limit the CPU time for a single step of Monte Carlo update to $O(m^2 + m \log n)$ with the help of balanced binary search trees. We demonstrate that our proposed algorithm with only logarithmic $n$-dependence achieves an exponential speedup from the existing methods, which suffer from severe performance issues at low temperatures.

DOI
10.48550/arxiv.2106.11645

Related papers

Self-learning Monte Carlo method: Continuous-time algorithm

Yuki Nagai, Huitao Shen, Yang Qi +2 more

The self-learning Monte Carlo (SLMC) method speeds up the Monte Carlo simulation by designing and training an effective model to propose efficient global updates. We implement the continuous-time quantum Monte Carlo algorithm for quantum impurity models in the framework of SLMC. We introduce and train a diagram generating function (DGF) to model the probability distribution of field configurations in the continuous imaginary time at all orders of diagrammatic expansion. By using the DGF to propose global updates, we show that the self-learning continuous-time Monte Carlo method can significantly reduce the computational complexity of the simulation.

arXiv:1705.06724•Physical review. B./Physical review. B•Oct 3, 2017•64 citations

Self-learning Monte Carlo with deep neural networks

Huitao Shen, Junwei Liu, Liang Fu

The self-learning Monte Carlo (SLMC) method is a general algorithm to speedup MC simulations. Its efficiency has been demonstrated in various systems by introducing an effective model to propose global moves in the configuration space. In this paper, we show that deep neural networks can be naturally incorporated into SLMC, and without any prior knowledge can learn the original model accurately and efficiently. Demonstrated in quantum impurity models, we reduce the complexity for a local update from $O({\ensuremath{\beta}}^{2})$ in Hirsch-Fye algorithm to $O(\ensuremath{\beta}ln\ensuremath{\beta})$, which is a significant speedup especially for systems at low temperatures.

arXiv:1801.01127•Physical review. B./Physical review. B•May 29, 2018•83 citations

Accelerated continuous time quantum Monte Carlo method with machine learning

Taegeun Song, Hunpyo Lee

An acceleration of continuous time quantum Monte Carlo (CTQMC) methods is a potentially interesting branch of work as they are matchless as impurity solvers of a dynamical mean field theory (DMFT) approach for the description of strongly correlated systems. The inversion of the $k\ifmmode\times\else\texttimes\fi{}k$ matrix with ${k}^{2}$ operations given by the diagram expansion order $k$ in the CTQMC fast update and the multiplication of the $k\ifmmode\times\else\texttimes\fi{}k$ matrix, and the noninteracting properties with $k\ifmmode\times\else\texttimes\fi{}{\ensuremath{\omega}}_{{n}_{\text{max}}}^{m\ensuremath{-}1}$ operations to measure the $m$-point correlators, are computationally time consuming. Here we propose the CTQMC method in combination with a machine learning technique, which eliminates the $k\ifmmode\times\else\texttimes\fi{}{\ensuremath{\omega}}_{{n}_{\text{max}}}$ and $k\ifmmode\times\else\texttimes\fi{}{\ensuremath{\omega}}_{{n}_{\text{max}}}^{3}$ operations for the two-point impurity Green's functions ${G}_{\ensuremath{\sigma}}(i{\ensuremath{\omega}}_{n})$ and four-point vertices ${\ensuremath{\chi}}_{\ensuremath{\sigma},\overline{\ensuremath{\sigma}}}(i{\ensuremath{\omega}}_{n{}_{1}},i{\ensuremath{\omega}}_{n{}_{2}},i{\ensuremath{\omega}}_{n{}_{3}},i{\ensuremath{\omega}}_{n{}_{4}})$, respectively. This method not only predicts the accurate physical properties at low temperature, but also dramatically decreases the computational times of ${\ensuremath{\chi}}_{\ensuremath{\sigma},\overline{\ensuremath{\sigma}}}(i{\ensuremath{\omega}}_{n{}_{1}},i{\ensuremath{\omega}}_{n{}_{2}},i{\ensuremath{\omega}}_{n{}_{3}},i{\ensuremath{\omega}}_{n{}_{4}})$ for the nonlocal extension of DMFT approximation.

arXiv:1901.01501•Physical review. B./Physical review. B•Jul 31, 2019•13 citations

Self-Learning Monte Carlo Method in Fermion Systems

Zi Yang Meng, Liang Fu, Junwei Liu +2 more

As a new general-purpose Monte Carlo method, self-learning Monte Carlo (SLMC) has been numerically demonstrated in boson systems. In this work, we propose a new type of update algorithm, dubbed cumulative update, which could be naturally integrated into SLMC. Based on many local updates in the self-learned effective model, cumulative update efficiently proposes a global move with a high acceptance probability in the original model. Cumulative update can reduce the conventional computational cost of a full sweep O(N4) to O(N3), and also effectively reduce the auto-correlation time to be 1. We numerically show its efficiency through the well-known double-exchange model. With cumulative update, the SLMC could be several hundreds of times faster than the conventional local update method. By employing the cumulative update, SLMC can be generally used in any sign-problem-free Fermion systems and maximize the performance of Monte Carlo simulation.

•Jan 1, 2017•0 citations

Self-learning Monte Carlo method

Zi Yang Meng, Junwei Liu, Yang Qi +1 more

Monte Carlo simulation is an unbiased numerical tool for studying classical and quantum many-body systems. One of its bottlenecks is the lack of a general and efficient update algorithm for large size systems close to the phase transition, for which local updates perform badly. In this Rapid Communication, we propose a general-purpose Monte Carlo method, dubbed self-learning Monte Carlo (SLMC), in which an efficient update algorithm is first learned from the training data generated in trial simulations and then used to speed up the actual simulation. We demonstrate the efficiency of SLMC in a spin model at the phase transition point, achieving a 10–20 times speedup.

Physical Review Letters•Jan 1, 2017•1 citation

Self-learning Monte Carlo method

Junwei Liu, Yang Qi, Zi Yang Meng +1 more

Monte Carlo simulation is an unbiased numerical tool for studying classical and quantum many-body systems. One of its bottlenecks is the lack of a general and efficient update algorithm for large size systems close to the phase transition, for which local updates perform badly. In this Rapid Communication, we propose a general-purpose Monte Carlo method, dubbed self-learning Monte Carlo (SLMC), in which an efficient update algorithm is first learned from the training data generated in trial simulations and then used to speed up the actual simulation. We demonstrate the efficiency of SLMC in a spin model at the phase transition point, achieving a 10--20 times speedup.

arXiv:1610.03137•Physical review. B./Physical review. B•Jan 4, 2017•258 citations
We propose a novel technique for speeding up the self-learning Monte Carlo method applied to the single-site impurity model. For the case where the effective Hamiltonian is expressed by polynomial functions of differences of imaginary-time coordinate between vertices, we can remove the dependence of CPU time on the number of vertices, nnn, by saving and updating some coefficients for each insertion and deletion process. As a result, the total cost for a single-step update is drastically reduced from O(nm)O(nm)O(nm) to O(m2)O(m^2)O(m2) with mmm being the order of polynomials in the effective Hamiltonian. Even for the existing algorithms, in which the absolute value is used instead of the difference as the variable of polynomial functions, we can limit the CPU time for a single step of Monte Carlo update to O(m2+mlog⁡n)O(m^2 + m \log n)O(m2+mlogn) with the help of balanced binary search trees. We demonstrate that our proposed algorithm with only logarithmic nnn-dependence achieves an exponential speedup from the existing methods, which suffer from severe performance issues at low temperatures.
The self-learning Monte Carlo (SLMC) method speeds up the Monte Carlo simulation by designing and training an effective model to propose efficient global updates. We implement the continuous-time quantum Monte Carlo algorithm for quantum impurity models in the framework of SLMC. We introduce and train a diagram generating function (DGF) to model the probability distribution of field configurations in the continuous imaginary time at all orders of diagrammatic expansion. By using the DGF to propose global updates, we show that the self-learning continuous-time Monte Carlo method can significantly reduce the computational complexity of the simulation.
The self-learning Monte Carlo (SLMC) method is a general algorithm to speedup MC simulations. Its efficiency has been demonstrated in various systems by introducing an effective model to propose global moves in the configuration space. In this paper, we show that deep neural networks can be naturally incorporated into SLMC, and without any prior knowledge can learn the original model accurately and efficiently. Demonstrated in quantum impurity models, we reduce the complexity for a local update from $O({\ensuremath{\beta}}^{2})$ in Hirsch-Fye algorithm to $O(\ensuremath{\beta}ln\ensuremath{\beta})$, which is a significant speedup especially for systems at low temperatures.
An acceleration of continuous time quantum Monte Carlo (CTQMC) methods is a potentially interesting branch of work as they are matchless as impurity solvers of a dynamical mean field theory (DMFT) approach for the description of strongly correlated systems. The inversion of the $k\ifmmode\times\else\texttimes\fi{}k$ matrix with k2{k}^{2}k2 operations given by the diagram expansion order kkk in the CTQMC fast update and the multiplication of the $k\ifmmode\times\else\texttimes\fi{}k$ matrix, and the noninteracting properties with $k\ifmmode\times\else\texttimes\fi{}{\ensuremath{\omega}}_{{n}_{\text{max}}}^{m\ensuremath{-}1}$ operations to measure the mmm-point correlators, are computationally time consuming. Here we propose the CTQMC method in combination with a machine learning technique, which eliminates the $k\ifmmode\times\else\texttimes\fi{}{\ensuremath{\omega}}_{{n}_{\text{max}}}$ and $k\ifmmode\times\else\texttimes\fi{}{\ensuremath{\omega}}_{{n}_{\text{max}}}^{3}$ operations for the two-point impurity Green's functions ${G}_{\ensuremath{\sigma}}(i{\ensuremath{\omega}}_{n})$ and four-point vertices ${\ensuremath{\chi}}_{\ensuremath{\sigma},\overline{\ensuremath{\sigma}}}(i{\ensuremath{\omega}}_{n{}_{1}},i{\ensuremath{\omega}}_{n{}_{2}},i{\ensuremath{\omega}}_{n{}_{3}},i{\ensuremath{\omega}}_{n{}_{4}})$, respectively. This method not only predicts the accurate physical properties at low temperature, but also dramatically decreases the computational times of ${\ensuremath{\chi}}_{\ensuremath{\sigma},\overline{\ensuremath{\sigma}}}(i{\ensuremath{\omega}}_{n{}_{1}},i{\ensuremath{\omega}}_{n{}_{2}},i{\ensuremath{\omega}}_{n{}_{3}},i{\ensuremath{\omega}}_{n{}_{4}})$ for the nonlocal extension of DMFT approximation.
As a new general-purpose Monte Carlo method, self-learning Monte Carlo (SLMC) has been numerically demonstrated in boson systems. In this work, we propose a new type of update algorithm, dubbed cumulative update, which could be naturally integrated into SLMC. Based on many local updates in the self-learned effective model, cumulative update efficiently proposes a global move with a high acceptance probability in the original model. Cumulative update can reduce the conventional computational cost of a full sweep O(N4) to O(N3), and also effectively reduce the auto-correlation time to be 1. We numerically show its efficiency through the well-known double-exchange model. With cumulative update, the SLMC could be several hundreds of times faster than the conventional local update method. By employing the cumulative update, SLMC can be generally used in any sign-problem-free Fermion systems and maximize the performance of Monte Carlo simulation.
Monte Carlo simulation is an unbiased numerical tool for studying classical and quantum many-body systems. One of its bottlenecks is the lack of a general and efficient update algorithm for large size systems close to the phase transition, for which local updates perform badly. In this Rapid Communication, we propose a general-purpose Monte Carlo method, dubbed self-learning Monte Carlo (SLMC), in which an efficient update algorithm is first learned from the training data generated in trial simulations and then used to speed up the actual simulation. We demonstrate the efficiency of SLMC in a spin model at the phase transition point, achieving a 10–20 times speedup.
Monte Carlo simulation is an unbiased numerical tool for studying classical and quantum many-body systems. One of its bottlenecks is the lack of a general and efficient update algorithm for large size systems close to the phase transition, for which local updates perform badly. In this Rapid Communication, we propose a general-purpose Monte Carlo method, dubbed self-learning Monte Carlo (SLMC), in which an efficient update algorithm is first learned from the training data generated in trial simulations and then used to speed up the actual simulation. We demonstrate the efficiency of SLMC in a spin model at the phase transition point, achieving a 10--20 times speedup.