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:2006.07654 · Mathematics of Computation

Numerical analysis for inchworm Monte Carlo method: Sign problem and error growth

Zhenning Cai, Jianfeng Lu, Siyao Yang

Published Nov 21, 2022• 19 citations
arXivHTMLPDF

Abstract

We consider the numerical analysis of the inchworm Monte Carlo method, which is proposed recently to tackle the numerical sign problem for open quantum systems. We focus on the growth of the numerical error with respect to the simulation time, for which the inchworm Monte Carlo method shows a flatter curve than the direct application of Monte Carlo method to the classical Dyson series. To better understand the underlying mechanism of the inchworm Monte Carlo method, we distinguish two types of exponential error growth, which are known as the numerical sign problem and the error amplification. The former is due to the fast growth of variance in the stochastic method, which can be observed from the Dyson series, and the latter comes from the evolution of the numerical solution. Our analysis demonstrates that the technique of partial resummation can be considered as a tool to balance these two types of error, and the inchworm Monte Carlo method is a successful case where the numerical sign problem is effectively suppressed by such means. We first demonstrate our idea in the context of ordinary differential equations, and then provide complete analysis for the inchworm Monte Carlo method. Several numerical experiments are carried out to verify our theoretical results.

DOI
10.1090/mcom/3785

Related papers

Inchworm Monte Carlo Method for Open Quantum Systems

Zhenning Cai, Jianfeng Lu, Siyao Yang

Abstract We investigate in this work a recently proposed diagrammatic quantum Monte Carlo method—the inchworm Monte Carlo method—for open quantum systems. We establish its validity rigorously based on resummation of Dyson series. Moreover, we introduce an integro‐differential equation formulation for open quantum systems, which illuminates the mathematical structure of the inchworm algorithm. This new formulation leads to an improvement of the inchworm algorithm by introducing classical deterministic time‐integration schemes. The numerical method is validated by applications to the spin‐boson model. © 2020 Wiley Periodicals, Inc.

arXiv:1811.08044•Communications on Pure and Applied Mathematics•Mar 6, 2020•26 citations

Steady-state properties of multi-orbital systems using quantum Monte Carlo

André Erpenbeck, Thomas Blommel, Lei Zhang +3 more

A precise dynamical characterization of quantum impurity models with multiple interacting orbitals is challenging. In quantum Monte Carlo methods, this is embodied by sign problems. A dynamical sign problem makes it exponentially difficult to simulate long times. A multi-orbital sign problem generally results in a prohibitive computational cost for systems with multiple impurity degrees of freedom even in static equilibrium calculations. Here, we present a numerically exact inchworm method that simultaneously alleviates both sign problems, enabling simulation of multi-orbital systems directly in the equilibrium or nonequilibrium steady-state. The method combines ideas from the recently developed steady-state inchworm Monte Carlo framework [Erpenbeck et al., Phys. Rev. Lett. 130, 186301 (2023)] with other ideas from the equilibrium multi-orbital inchworm algorithm [Eidelstein et al., Phys. Rev. Lett. 124, 206405 (2020)]. We verify our method by comparison with analytical limits and numerical results from previous methods.

arXiv:2407.00771•The Journal of Chemical Physics•Sep 4, 2024•12 citations

Inchworm Monte Carlo for exact non-adiabatic dynamics. I. Theory and algorithms

Hsing-Ta Chen, Guy Cohen, David R. Reichman

In this paper, we provide a detailed description of the inchworm Monte Carlo formalism for the exact study of real-time non-adiabatic dynamics. This method optimally recycles Monte Carlo information from earlier times to greatly suppress the dynamical sign problem. Using the example of the spin-boson model, we formulate the inchworm expansion in two distinct ways: The first with respect to an expansion in the system-bath coupling and the second as an expansion in the diabatic coupling. The latter approach motivates the development of a cumulant version of the inchworm Monte Carlo method, which has the benefit of improved scaling. This paper deals completely with methodology, while Paper II provides a comprehensive comparison of the performance of the inchworm Monte Carlo algorithms to other exact methodologies as well as a discussion of the relative advantages and disadvantages of each.

arXiv:1610.09566•The Journal of Chemical Physics•Feb 1, 2017•82 citations

Inchworm quasi Monte Carlo for quantum impurities

Hugo U. R. Strand, Joseph Kleinhenz, Igor S. Krivenko

The inchworm expansion is a promising approach to solving strongly correlated quantum impurity models due to its reduction of the sign problem in real and imaginary time. However, inchworm Monte Carlo is computationally expensive, converging as 1 / N where N is the number of samples. We show that the imaginary-time integration is amenable to quasi Monte Carlo, with parametrically better 1 / N convergence, by mapping the Sobol low-discrepancy sequence from the hypercube to the simplex with the so-called Root transform. This extends the applicability of the inchworm method to, e.g., multiorbital Anderson impurity models with off-diagonal hybridization, relevant for materials simulation, where continuous-time hybridization expansion Monte Carlo has a severe sign problem. Published by the American Physical Society 2024

arXiv:2310.16957•Physical review. B./Physical review. B•Sep 24, 2024•6 citations

Inchworm Monte Carlo for exact non-adiabatic dynamics. II. Benchmarks and comparison with established methods

Hsing-Ta Chen, Guy Cohen, David R. Reichman

In this second paper of a two part series, we present extensive benchmark results for two different inchworm Monte Carlo expansions for the spin-boson model. Our results are compared to previously developed numerically exact approaches for this problem. A detailed discussion of convergence and error propagation is presented. Our results and analysis allow for an understanding of the benefits and drawbacks of inchworm Monte Carlo compared to other approaches for exact real-time non-adiabatic quantum dynamics.

arXiv:1610.09402•The Journal of Chemical Physics•Feb 1, 2017•66 citations

Sign Problem in Quantum Monte Carlo Simulation

Gaopei Pan, Zi Yang Meng

Sign problem in quantum Monte Carlo (QMC) simulation appears to be an extremely hard yet interesting problem. In this article, we present a pedagogical overview on the origin of the sign problem in various quantum Monte Carlo simulation techniques, ranging from the world-line and stochastic series expansion Monte Carlo for boson and spin systems to the determinant and momentum-space quantum Monte Carlo for interacting fermions. We point out the basis dependency of the sign problem and summarize the progresses to cure, ease and even make use of the sign problem over the years, such as symmetry analysis of the underlying Hamiltonian, basis optimization in writting down the partition functions and many others. Moreover, we state that although traditional lore saying that in case of sign problem, the average sign in QMC simulation approaches zero exponentially fast with the space-time volume of the configurational space, there are recent breakthroughs showing this is not always the case and based on the properties of the partition function for finite size systems, one could distinguish when the average sign has the usual exponential scaling and when it is bestowed with an algebraic scaling at the low temperature limit. Fermionic QMC simulations with such algebraic sign problems have been successfully carried out for extended Hubbard-type and quantum Moiré lattice models.

arXiv:2204.08777•Apr 19, 2022•7 citations
We consider the numerical analysis of the inchworm Monte Carlo method, which is proposed recently to tackle the numerical sign problem for open quantum systems. We focus on the growth of the numerical error with respect to the simulation time, for which the inchworm Monte Carlo method shows a flatter curve than the direct application of Monte Carlo method to the classical Dyson series. To better understand the underlying mechanism of the inchworm Monte Carlo method, we distinguish two types of exponential error growth, which are known as the numerical sign problem and the error amplification. The former is due to the fast growth of variance in the stochastic method, which can be observed from the Dyson series, and the latter comes from the evolution of the numerical solution. Our analysis demonstrates that the technique of partial resummation can be considered as a tool to balance these two types of error, and the inchworm Monte Carlo method is a successful case where the numerical sign problem is effectively suppressed by such means. We first demonstrate our idea in the context of ordinary differential equations, and then provide complete analysis for the inchworm Monte Carlo method. Several numerical experiments are carried out to verify our theoretical results.
Abstract We investigate in this work a recently proposed diagrammatic quantum Monte Carlo method—the inchworm Monte Carlo method—for open quantum systems. We establish its validity rigorously based on resummation of Dyson series. Moreover, we introduce an integro‐differential equation formulation for open quantum systems, which illuminates the mathematical structure of the inchworm algorithm. This new formulation leads to an improvement of the inchworm algorithm by introducing classical deterministic time‐integration schemes. The numerical method is validated by applications to the spin‐boson model. © 2020 Wiley Periodicals, Inc.
A precise dynamical characterization of quantum impurity models with multiple interacting orbitals is challenging. In quantum Monte Carlo methods, this is embodied by sign problems. A dynamical sign problem makes it exponentially difficult to simulate long times. A multi-orbital sign problem generally results in a prohibitive computational cost for systems with multiple impurity degrees of freedom even in static equilibrium calculations. Here, we present a numerically exact inchworm method that simultaneously alleviates both sign problems, enabling simulation of multi-orbital systems directly in the equilibrium or nonequilibrium steady-state. The method combines ideas from the recently developed steady-state inchworm Monte Carlo framework [Erpenbeck et al., Phys. Rev. Lett. 130, 186301 (2023)] with other ideas from the equilibrium multi-orbital inchworm algorithm [Eidelstein et al., Phys. Rev. Lett. 124, 206405 (2020)]. We verify our method by comparison with analytical limits and numerical results from previous methods.
In this paper, we provide a detailed description of the inchworm Monte Carlo formalism for the exact study of real-time non-adiabatic dynamics. This method optimally recycles Monte Carlo information from earlier times to greatly suppress the dynamical sign problem. Using the example of the spin-boson model, we formulate the inchworm expansion in two distinct ways: The first with respect to an expansion in the system-bath coupling and the second as an expansion in the diabatic coupling. The latter approach motivates the development of a cumulant version of the inchworm Monte Carlo method, which has the benefit of improved scaling. This paper deals completely with methodology, while Paper II provides a comprehensive comparison of the performance of the inchworm Monte Carlo algorithms to other exact methodologies as well as a discussion of the relative advantages and disadvantages of each.
The inchworm expansion is a promising approach to solving strongly correlated quantum impurity models due to its reduction of the sign problem in real and imaginary time. However, inchworm Monte Carlo is computationally expensive, converging as 1 / N where N is the number of samples. We show that the imaginary-time integration is amenable to quasi Monte Carlo, with parametrically better 1 / N convergence, by mapping the Sobol low-discrepancy sequence from the hypercube to the simplex with the so-called Root transform. This extends the applicability of the inchworm method to, e.g., multiorbital Anderson impurity models with off-diagonal hybridization, relevant for materials simulation, where continuous-time hybridization expansion Monte Carlo has a severe sign problem. Published by the American Physical Society 2024
In this second paper of a two part series, we present extensive benchmark results for two different inchworm Monte Carlo expansions for the spin-boson model. Our results are compared to previously developed numerically exact approaches for this problem. A detailed discussion of convergence and error propagation is presented. Our results and analysis allow for an understanding of the benefits and drawbacks of inchworm Monte Carlo compared to other approaches for exact real-time non-adiabatic quantum dynamics.
Sign problem in quantum Monte Carlo (QMC) simulation appears to be an extremely hard yet interesting problem. In this article, we present a pedagogical overview on the origin of the sign problem in various quantum Monte Carlo simulation techniques, ranging from the world-line and stochastic series expansion Monte Carlo for boson and spin systems to the determinant and momentum-space quantum Monte Carlo for interacting fermions. We point out the basis dependency of the sign problem and summarize the progresses to cure, ease and even make use of the sign problem over the years, such as symmetry analysis of the underlying Hamiltonian, basis optimization in writting down the partition functions and many others. Moreover, we state that although traditional lore saying that in case of sign problem, the average sign in QMC simulation approaches zero exponentially fast with the space-time volume of the configurational space, there are recent breakthroughs showing this is not always the case and based on the properties of the partition function for finite size systems, one could distinguish when the average sign has the usual exponential scaling and when it is bestowed with an algebraic scaling at the low temperature limit. Fermionic QMC simulations with such algebraic sign problems have been successfully carried out for extended Hubbard-type and quantum Moiré lattice models.