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:2103.01423 · New Journal of Physics

Inclusion–exclusion principle for open quantum systems with bosonic bath

Siyao Yang, Zhenning Cai, Jianfeng Lu

Published May 19, 2021• 15 citations
arXivHTMLPDF

Abstract

Abstract We present two fast algorithms which apply inclusion–exclusion principle to sum over the bosonic diagrams in bare diagrammatic quantum Monte Carlo and inchworm Monte Carlo method, respectively. In the case of inchworm Monte Carlo, the proposed fast algorithm gives an extension to the work [2018 Inclusion–exclusion principle for many-body diagrammatics Phys. Rev. B 98 115152] from fermionic to bosonic systems. We prove that the proposed fast algorithms reduce the computational complexity from double factorial to exponential. Numerical experiments are carried out to verify the theoretical results and to compare the efficiency of the methods.

DOI
10.1088/1367-2630/ac02e1

Related papers

Inclusion-exclusion principle for many-body diagrammatics

Aviel Boag, Emanuel Gull, Guy Cohen

Diagrammatic resummation techniques have recently enabled new classes of quantum Monte Carlo algorithms, but are restricted by the need to sum over factorially large sets of diagrams. Here, the authors present a fast algorithm for summing over the diagrams appearing in Inchworm hybridization expansions. The method relies on the inclusion-exclusion principle to reduce the scaling from factorial to exponential. For the Inchworm hybridization expansion, when compared to the previous state of the art, the new algorithm is shown to provide practical performance gains of approximately two orders of magnitude.

arXiv:1807.00290•Physical review. B./Physical review. B•Sep 26, 2018•38 citations

The Bold-Thin-Bold Diagrammatic Monte Carlo Method for Open Quantum Systems

Zhenning Cai, Geshuo Wang, Siyao Yang

Abstract. We present two diagrammatic Monte Carlo methods for quantum systems coupled with harmonic baths, whose dynamics are described by integro-differential equations. The first approach can be considered as a reformulation of the Dyson series, and the second one, called “bold-thin-bold diagrammatic Monte Carlo,” is based on resummation of the diagrams in the Dyson series to accelerate its convergence. The underlying mechanism of the governing equations associated with the two methods lies in the recurrence relation of the path integrals, which is the most costly part in the numerical methods. The proposed algorithms give an extension to the work of Cai, Lu, and Yang [ Comput. Phys. Commun. 278 (2022), 108417], where the algorithms are designed based on reusing the previous calculations of bath influence functionals. Compared with the algorithms therein, our methods further include the reuse of system-associated functionals and show better performance in terms of computational efficiency and memory cost. We demonstrate the two methods in the framework of spin-boson model, and numerical experiments are carried out to verify the validity of the methods.

arXiv:2205.10896•SIAM Journal on Scientific Computing•Jul 19, 2023•8 citations

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

Fast principal minor algorithms for diagrammatic Monte Carlo

Fedor Šimkovic, Michel Ferrero

The computation of determinants plays a central role in diagrammatic Monte Carlo algorithms for strongly correlated systems. The evaluation of large numbers of determinants can often be the limiting computational factor determining the number of attainable diagrammatic expansion orders. In this work we build on the algorithm presented in [K. Griffin and M. J. Tsatsomeros, Principal minors, part i: A method for computing all the principal minors of a matrix, Linear Algebra Appl. 419, 107 (2006)] which computes all principal minors of a matrix in $O({2}^{n})$ operations. We present multiple generalizations of the algorithm to the efficient evaluation of certain subsets of all principal minors with immediate applications to connected determinant diagrammatic Monte Carlo within the normal and symmetry-broken phases as well as continuous-time quantum Monte Carlo. Additionally, we improve the asymptotic scaling of diagrammatic Monte Carlo formulated in real time to $O({2}^{n})$ and report speedups of up to a factor 25 at computationally realistic expansion orders. We further show that all permanent principal minors, corresponding to sums of bosonic Feynman diagrams, can be computed in $O({3}^{n})$, thus encouraging the investigation of bosonic and mixed systems by means of diagrammatic Monte Carlo.

arXiv:2104.07638•Physical review. B./Physical review. B•Mar 3, 2022•10 citations

Diagrammatic Monte Carlo for dissipative quantum impurity models

Matthieu Vanhoecke, Marco Schirò

We develop a diagrammatic Monte Carlo method for the real-time dynamics of dissipative quantum impurity models. These are small open quantum systems with interaction and local Markovian dissipation, coupled to a large quantum bath. Our algorithm samples the hybridization expansion formulated on a single real-time contour, rather than on the double Keldysh one, as it naturally arises in the thermofield/vectorized representation of the Lindblad dynamics. We show that local Markovian dissipation generally helps the convergence of the diagrammatic Monte Carlo sampling by reducing the sign problem, thus allowing to reach longer timescales as compared to the conventional unitary case. We apply our method to an Anderson impurity model in the presence of local dephasing and discuss its effect on the charge and spin dynamics of the impurity.

arXiv:2311.17839•Physical review. B./Physical review. B•Mar 18, 2024•14 citations

Real-Time Simulation of Open Quantum Spin Chains with the Inchworm Method

Geshuo Wang, Zhenning Cai

We study the real-time simulation of open quantum systems, where the system is modeled by a spin chain with each spin associated with its own harmonic bath. Our method couples the inchworm method for the spin-boson model and the modular path integral methodology for spin systems. In particular, the introduction of the inchworm method can significantly suppress the numerical sign problem. Both methods are tweaked to make them work seamlessly with each other. We represent our approach in the language of diagrammatic methods and analyze the asymptotic behavior of the computational cost. Extensive numerical experiments are performed to validate our method.

arXiv:2307.03924•Journal of Chemical Theory and Computation•Dec 1, 2023•8 citations
Abstract We present two fast algorithms which apply inclusion–exclusion principle to sum over the bosonic diagrams in bare diagrammatic quantum Monte Carlo and inchworm Monte Carlo method, respectively. In the case of inchworm Monte Carlo, the proposed fast algorithm gives an extension to the work [2018 Inclusion–exclusion principle for many-body diagrammatics Phys. Rev. B 98 115152] from fermionic to bosonic systems. We prove that the proposed fast algorithms reduce the computational complexity from double factorial to exponential. Numerical experiments are carried out to verify the theoretical results and to compare the efficiency of the methods.
Diagrammatic resummation techniques have recently enabled new classes of quantum Monte Carlo algorithms, but are restricted by the need to sum over factorially large sets of diagrams. Here, the authors present a fast algorithm for summing over the diagrams appearing in Inchworm hybridization expansions. The method relies on the inclusion-exclusion principle to reduce the scaling from factorial to exponential. For the Inchworm hybridization expansion, when compared to the previous state of the art, the new algorithm is shown to provide practical performance gains of approximately two orders of magnitude.
Abstract. We present two diagrammatic Monte Carlo methods for quantum systems coupled with harmonic baths, whose dynamics are described by integro-differential equations. The first approach can be considered as a reformulation of the Dyson series, and the second one, called “bold-thin-bold diagrammatic Monte Carlo,” is based on resummation of the diagrams in the Dyson series to accelerate its convergence. The underlying mechanism of the governing equations associated with the two methods lies in the recurrence relation of the path integrals, which is the most costly part in the numerical methods. The proposed algorithms give an extension to the work of Cai, Lu, and Yang [ Comput. Phys. Commun. 278 (2022), 108417], where the algorithms are designed based on reusing the previous calculations of bath influence functionals. Compared with the algorithms therein, our methods further include the reuse of system-associated functionals and show better performance in terms of computational efficiency and memory cost. We demonstrate the two methods in the framework of spin-boson model, and numerical experiments are carried out to verify the validity of the methods.
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.
The computation of determinants plays a central role in diagrammatic Monte Carlo algorithms for strongly correlated systems. The evaluation of large numbers of determinants can often be the limiting computational factor determining the number of attainable diagrammatic expansion orders. In this work we build on the algorithm presented in [K. Griffin and M. J. Tsatsomeros, Principal minors, part i: A method for computing all the principal minors of a matrix, Linear Algebra Appl. 419, 107 (2006)] which computes all principal minors of a matrix in O(2n)O({2}^{n})O(2n) operations. We present multiple generalizations of the algorithm to the efficient evaluation of certain subsets of all principal minors with immediate applications to connected determinant diagrammatic Monte Carlo within the normal and symmetry-broken phases as well as continuous-time quantum Monte Carlo. Additionally, we improve the asymptotic scaling of diagrammatic Monte Carlo formulated in real time to O(2n)O({2}^{n})O(2n) and report speedups of up to a factor 25 at computationally realistic expansion orders. We further show that all permanent principal minors, corresponding to sums of bosonic Feynman diagrams, can be computed in O(3n)O({3}^{n})O(3n), thus encouraging the investigation of bosonic and mixed systems by means of diagrammatic Monte Carlo.
We develop a diagrammatic Monte Carlo method for the real-time dynamics of dissipative quantum impurity models. These are small open quantum systems with interaction and local Markovian dissipation, coupled to a large quantum bath. Our algorithm samples the hybridization expansion formulated on a single real-time contour, rather than on the double Keldysh one, as it naturally arises in the thermofield/vectorized representation of the Lindblad dynamics. We show that local Markovian dissipation generally helps the convergence of the diagrammatic Monte Carlo sampling by reducing the sign problem, thus allowing to reach longer timescales as compared to the conventional unitary case. We apply our method to an Anderson impurity model in the presence of local dephasing and discuss its effect on the charge and spin dynamics of the impurity.
We study the real-time simulation of open quantum systems, where the system is modeled by a spin chain with each spin associated with its own harmonic bath. Our method couples the inchworm method for the spin-boson model and the modular path integral methodology for spin systems. In particular, the introduction of the inchworm method can significantly suppress the numerical sign problem. Both methods are tweaked to make them work seamlessly with each other. We represent our approach in the language of diagrammatic methods and analyze the asymptotic behavior of the computational cost. Extensive numerical experiments are performed to validate our method.