{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,4,22]],"date-time":"2026-04-22T05:45:00Z","timestamp":1776836700843,"version":"3.51.2"},"reference-count":46,"publisher":"American Mathematical Society (AMS)","issue":"341","license":[{"start":{"date-parts":[[2023,11,21]],"date-time":"2023-11-21T00:00:00Z","timestamp":1700524800000},"content-version":"am","delay-in-days":365,"URL":"https:\/\/www.ams.org\/publications\/copyright-and-permissions"}],"funder":[{"DOI":"10.13039\/501100001461","name":"Ministry of National Development - Singapore","doi-asserted-by":"publisher","award":["A-0004272-00-00"],"award-info":[{"award-number":["A-0004272-00-00"]}],"id":[{"id":"10.13039\/501100001461","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/501100001461","name":"Ministry of National Development - Singapore","doi-asserted-by":"publisher","award":["DMS-1454939"],"award-info":[{"award-number":["DMS-1454939"]}],"id":[{"id":"10.13039\/501100001461","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/501100001461","name":"Ministry of National Development - Singapore","doi-asserted-by":"publisher","award":["DMS-2012286"],"award-info":[{"award-number":["DMS-2012286"]}],"id":[{"id":"10.13039\/501100001461","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/100000001","name":"National Science Foundation","doi-asserted-by":"publisher","award":["A-0004272-00-00"],"award-info":[{"award-number":["A-0004272-00-00"]}],"id":[{"id":"10.13039\/100000001","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/100000001","name":"National Science Foundation","doi-asserted-by":"publisher","award":["DMS-1454939"],"award-info":[{"award-number":["DMS-1454939"]}],"id":[{"id":"10.13039\/100000001","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/100000001","name":"National Science Foundation","doi-asserted-by":"publisher","award":["DMS-2012286"],"award-info":[{"award-number":["DMS-2012286"]}],"id":[{"id":"10.13039\/100000001","id-type":"DOI","asserted-by":"publisher"}]}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Math. Comp."],"abstract":"<p>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.<\/p>","DOI":"10.1090\/mcom\/3785","type":"journal-article","created":{"date-parts":[[2022,11,21]],"date-time":"2022-11-21T10:39:01Z","timestamp":1669027141000},"page":"1141-1209","source":"Crossref","is-referenced-by-count":13,"title":["Numerical analysis for inchworm Monte Carlo method: Sign problem and error growth"],"prefix":"10.1090","volume":"92","author":[{"given":"Zhenning","family":"Cai","sequence":"first","affiliation":[]},{"given":"Jianfeng","family":"Lu","sequence":"additional","affiliation":[]},{"given":"Siyao","family":"Yang","sequence":"additional","affiliation":[]}],"member":"14","published-online":{"date-parts":[[2022,11,21]]},"reference":[{"key":"1","doi-asserted-by":"crossref","unstructured":"M. Asano, Basieva I., Khrennikov A., Ohya M., Tanaka Y., and Yamato I., Quantum information biology: From theory of open quantum systems to adaptive dynamics, ch. 18, pp. 399\u2013414, World Scientific, 2016.","DOI":"10.1142\/9789814730617_0018"},{"key":"2","doi-asserted-by":"crossref","unstructured":"G. A. Bird, Approach to translational equilibrium in a rigid sphere gas, Phys. Fluids 6 (1963), no. 10, 1518\u20131519.","DOI":"10.1063\/1.1710976"},{"key":"3","doi-asserted-by":"crossref","unstructured":"G. A. Bird, Molecular Gas Dynamics and the Direct Simulation of Gas Flows, Clarendon Press, Oxford, 1994.","DOI":"10.1093\/oso\/9780198561958.001.0001"},{"issue":"3","key":"4","doi-asserted-by":"publisher","first-page":"B706--B722","DOI":"10.1137\/17M1145446","article-title":"A quantum kinetic Monte Carlo method for quantum many-body spin dynamics","volume":"40","author":"Cai, Zhenning","year":"2018","journal-title":"SIAM J. Sci. Comput.","ISSN":"https:\/\/id.crossref.org\/issn\/1064-8275","issn-type":"print"},{"issue":"11","key":"5","doi-asserted-by":"publisher","first-page":"2430","DOI":"10.1002\/cpa.21888","article-title":"Inchworm Monte Carlo method for open quantum systems","volume":"73","author":"Cai, Zhenning","year":"2020","journal-title":"Comm. Pure Appl. Math.","ISSN":"https:\/\/id.crossref.org\/issn\/0010-3640","issn-type":"print"},{"key":"6","doi-asserted-by":"crossref","unstructured":"E. Campbell, Random compiler for fast Hamiltonian simulation, Phys. Rev. Lett. 123 (2019), 070503.","DOI":"10.1103\/PhysRevLett.123.070503"},{"key":"7","doi-asserted-by":"crossref","unstructured":"H.-T. Chen, G. Cohen, and D. R. Reichman, Inchworm Monte Carlo for exact non-adiabatic dynamics. I. Theory and algorithms, J. Chem. Phys. 146 (2017), 054105.","DOI":"10.1063\/1.4974328"},{"key":"8","doi-asserted-by":"crossref","unstructured":"H.-T Chen, G. Cohen, and D. R. Reichman, Inchworm Monte Carlo for exact non-adiabatic dynamics. II. Benchmarks and comparison with established methods, J. Chem. Phys. 146 (2017), 054106.","DOI":"10.1063\/1.4974329"},{"key":"9","doi-asserted-by":"crossref","unstructured":"G. Cohen, E. Gull, D. R. Reichman, and A. J. Millis, Taming the dynamical sign problem in real-time evolution of quantum many-body problems, Phys. Rev. Lett. 115 (2015), no. 26, 266802.","DOI":"10.1103\/PhysRevLett.115.266802"},{"key":"10","doi-asserted-by":"crossref","unstructured":"M. Cristoforetti, F. Di Renzo, and L. Scorzato, New approach to the sign problem in quantum field theories: high density QCD on a Lefschetz thimble, Phys. Rev. D 86 (2012), 074506.","DOI":"10.1103\/PhysRevD.86.074506"},{"key":"11","doi-asserted-by":"crossref","unstructured":"Q. Dong, I. Krivenko, J. Kleinhenz, A. E. Antipov, G. Cohen, and E. Gull, Quantum Monte Carlo solution of the dynamical mean field equations in real time, Phys. Rev. B 96 (2017), 155126.","DOI":"10.1103\/PhysRevB.96.155126"},{"key":"12","doi-asserted-by":"crossref","unstructured":"C. Duan, Z. Tang, J. Cao, and J. Wu, Zero-temperature localization in a sub-ohmic spin-boson model investigated by an extended hierarchy equation of motion, Phys. Rev. B 95 (2017), no. 21, 214308.","DOI":"10.1103\/PhysRevB.95.214308"},{"key":"13","doi-asserted-by":"crossref","unstructured":"E. Eidelstein, E. Gull, and G. Cohen, Multiorbital quantum impurity solver for general interactions and hybridizations, Phys. Rev. Lett. 124 (2020), no. 20, 206405.","DOI":"10.1103\/PhysRevLett.124.206405"},{"issue":"4","key":"14","doi-asserted-by":"publisher","first-page":"1665","DOI":"10.1103\/RevModPhys.81.1665","article-title":"Nonequilibrium fluctuations, fluctuation theorems, and counting statistics in quantum systems","volume":"81","author":"Esposito, Massimiliano","year":"2009","journal-title":"Rev. Modern Phys.","ISSN":"https:\/\/id.crossref.org\/issn\/0034-6861","issn-type":"print"},{"key":"15","series-title":"Springer Series in Computational Mathematics","isbn-type":"print","volume-title":"Solving ordinary differential equations. I","volume":"8","author":"Hairer, E.","year":"1993","ISBN":"https:\/\/id.crossref.org\/isbn\/3540566708","edition":"2"},{"issue":"1","key":"16","doi-asserted-by":"publisher","first-page":"3","DOI":"10.4310\/AMSA.2019.v4.n1.a1","article-title":"On the diffusion approximation of nonconvex stochastic gradient descent","volume":"4","author":"Hu, Wenqing","year":"2019","journal-title":"Ann. Math. Sci. Appl.","ISSN":"https:\/\/id.crossref.org\/issn\/2380-288X","issn-type":"print"},{"key":"17","doi-asserted-by":"crossref","unstructured":"A. Ishizaki and Y. Tanimura, Quantum dynamics of system strongly coupled to low-temperature colored noise bath: reduced hierarchy equations approach, J. Phys. Soc. Jpn. 74 (2005), no. 12, 3131\u20133134.","DOI":"10.1143\/JPSJ.74.3131"},{"key":"18","doi-asserted-by":"publisher","first-page":"108877","DOI":"10.1016\/j.jcp.2019.108877","article-title":"Random batch methods (RBM) for interacting particle systems","volume":"400","author":"Jin, Shi","year":"2020","journal-title":"J. Comput. Phys.","ISSN":"https:\/\/id.crossref.org\/issn\/0021-9991","issn-type":"print"},{"key":"19","first-page":"1515","article-title":"Diagram technique for nonequilibrium processes","volume":"47","author":"Keldysh, L. V.","journal-title":"\\v{Z}. \\`Eksper. Teoret. Fiz."},{"key":"20","doi-asserted-by":"crossref","unstructured":"D. Mac Kernan, G. Ciccotti, and R. Kapral, Surface-hopping dynamics of a spin-boson system, J. Chem. Phys. 116 (2002), no. 6, 2346\u20132353.","DOI":"10.1063\/1.1433502"},{"issue":"3","key":"21","doi-asserted-by":"publisher","first-page":"A1486--A1509","DOI":"10.1137\/19M1302077","article-title":"A random-batch Monte Carlo method for many-body systems with singular kernels","volume":"42","author":"Li, Lei","year":"2020","journal-title":"SIAM J. Sci. Comput.","ISSN":"https:\/\/id.crossref.org\/issn\/1064-8275","issn-type":"print"},{"key":"22","unstructured":"Q. Li, C. Tai, and W. E, Stochastic modified equations and adaptive stochastic gradient algorithms, Proceedings of the 34th International Conference on Machine Learning (International Convention Centre, Sydney, Australia) (D. Precup and Y. W. Teh, eds.), Proceedings of Machine Learning Research, vol. 70, 2017, pp. 2101\u20132110."},{"key":"23","doi-asserted-by":"crossref","unstructured":"Y. Li and J. Lu, Bold diagrammatic Monte Carlo in the lens of stochastic iterative methods, Trans. Math. Appl. 3 (2019), 1\u201317.","DOI":"10.1093\/imatrm\/tnz001"},{"issue":"2","key":"24","doi-asserted-by":"crossref","first-page":"119","DOI":"10.1007\/BF01608499","article-title":"On the generators of quantum dynamical semigroups","volume":"48","author":"Lindblad, G.","year":"1976","journal-title":"Comm. Math. Phys.","ISSN":"https:\/\/id.crossref.org\/issn\/0010-3616","issn-type":"print"},{"key":"25","doi-asserted-by":"crossref","unstructured":"E. Y. Loh Jr., J. E. Gubernatis, R. T. Scalettar, S. R. White, D. J. Scalapino, and R. L. Sugar, Sign problem in the numerical simulation of many-electron systems, Phys. Rev. B 41 (1990), no. 13, 9301\u20139307.","DOI":"10.1103\/PhysRevB.41.9301"},{"key":"26","doi-asserted-by":"crossref","unstructured":"D. MacKernan, R. Kapral, and G. Ciccotti, Sequential short-time propagation of quantum-classical dynamics, J. Phys. Condens. Matter 14 (2002), no. 40, 9069\u20139076.","DOI":"10.1088\/0953-8984\/14\/40\/301"},{"key":"27","doi-asserted-by":"crossref","unstructured":"N. Makri, Improved Feynman propagators on a grid and non-adiabatic corrections within the path integral framework, Chem. Phys. Lett. 193 (1992), no. 5, 435\u2013445.","DOI":"10.1016\/0009-2614(92)85654-S"},{"key":"28","doi-asserted-by":"crossref","unstructured":"N. Makri, On smooth Feynman propagators for real time path integrals, J. Phys. Chem. 97 (1993), no. 10, 2417\u20132424.","DOI":"10.1021\/j100112a050"},{"issue":"5","key":"29","doi-asserted-by":"publisher","first-page":"2430","DOI":"10.1063\/1.531046","article-title":"Numerical path integral techniques for long time dynamics of quantum dissipative systems","volume":"36","author":"Makri, Nancy","year":"1995","journal-title":"J. Math. Phys.","ISSN":"https:\/\/id.crossref.org\/issn\/0022-2488","issn-type":"print"},{"key":"30","doi-asserted-by":"crossref","unstructured":"N. Makri, Quantum dissipative dynamics: a numerically exact methodology, J. Phys. Chem. A 102 (1998), no. 24, 4414\u20134427.","DOI":"10.1021\/jp980359y"},{"key":"31","doi-asserted-by":"crossref","unstructured":"N. Makri, Iterative blip-summed path integral for quantum dynamics in strongly dissipative environments, J. Chem. Phys. 146 (2017), no. 13, 134101.","DOI":"10.1063\/1.4979197"},{"key":"32","doi-asserted-by":"crossref","unstructured":"N. Makri and D. E. Makarov, Tensor propagator for iterative quantum time evolution of reduced density matrices. I. Theory, J. Chem. Phys. 102 (1995), no. 11, 4600\u20134610.","DOI":"10.1063\/1.469508"},{"key":"33","doi-asserted-by":"crossref","unstructured":"L. Mancino, V. Cavina, A. De Pasquale, M. Sbroscia, R. I. Booth, E. Roccia, I. Gianani, V. Giovannetti, and M. Barbieri, Geometrical bounds on irreversibility in open quantum systems, Phys. Rev. Lett. 121 (2018), no. 16, 160602.","DOI":"10.1103\/PhysRevLett.121.160602"},{"key":"34","doi-asserted-by":"crossref","unstructured":"L. M\u00fchlbacher and E. Rabani, Real-time path integral approach to nonequilibrium many-body quantum systems, Phys. Rev. Lett. 100 (2008), no. 17, 176403.","DOI":"10.1103\/PhysRevLett.100.176403"},{"key":"35","doi-asserted-by":"crossref","unstructured":"L. M\u00fchlbacher and E. Rabani, Diagrammatic Monte Carlo simulation of nonequilibrium systems, Phys. Rev. B 79 (2009), no. 3, 035320.","DOI":"10.1103\/PhysRevB.79.035320"},{"key":"36","doi-asserted-by":"publisher","first-page":"948","DOI":"10.1143\/PTP.20.948","article-title":"On quantum theory of transport phenomena: steady diffusion","volume":"20","author":"Nakajima, Sadao","year":"1958","journal-title":"Progr. Theoret. Phys.","ISSN":"https:\/\/id.crossref.org\/issn\/0033-068X","issn-type":"print"},{"key":"37","series-title":"Frontiers in Physics","isbn-type":"print","doi-asserted-by":"publisher","DOI":"10.1142\/S0218001488000273","volume-title":"Quantum many-particle systems","volume":"68","author":"Negele, John W.","year":"1988","ISBN":"https:\/\/id.crossref.org\/isbn\/0201125935"},{"key":"38","doi-asserted-by":"crossref","unstructured":"N. Prokof\u2019ev and B. Svistunov, Bold diagrammatic Monte Carlo technique: when the sign problem is welcome, Phys. Rev. Lett. 99 (2007), no. 25, 250201.","DOI":"10.1103\/PhysRevLett.99.250201"},{"key":"39","doi-asserted-by":"crossref","unstructured":"M. Ridley, V. N. Singh, E. Gull, and G. Cohen, Numerically exact full counting statistics of the nonequilibrium Anderson impurity model, Phys. Rev. B 97 (2018), no. 11, 115109.","DOI":"10.1103\/PhysRevB.97.115109"},{"key":"40","doi-asserted-by":"crossref","unstructured":"M. Schir\u00f3, Real-time dynamics in quantum impurity models with diagrammatic Monte Carlo, Phys. Rev. B 81 (2010), no. 8, 085126.","DOI":"10.1103\/PhysRevB.81.085126"},{"key":"41","doi-asserted-by":"crossref","unstructured":"P. W. Shor, Scheme for reducing decoherence in quantum computer memory, Phys. Rev. A 52 (1995), no. 4, R2493\u2013R2496.","DOI":"10.1103\/PhysRevA.52.R2493"},{"issue":"3","key":"42","doi-asserted-by":"publisher","first-page":"309","DOI":"10.1016\/0012-365X(78)90162-0","article-title":"On a class of linked diagrams. II. Asymptotics","volume":"21","author":"Stein, P. R.","year":"1978","journal-title":"Discrete Math.","ISSN":"https:\/\/id.crossref.org\/issn\/0012-365X","issn-type":"print"},{"issue":"3","key":"43","doi-asserted-by":"publisher","first-page":"1191","DOI":"10.1137\/S0036142996313154","article-title":"The error in linear interpolation at the vertices of a simplex","volume":"35","author":"Waldron, Shayne","year":"1998","journal-title":"SIAM J. Numer. Anal.","ISSN":"https:\/\/id.crossref.org\/issn\/0036-1429","issn-type":"print"},{"key":"44","doi-asserted-by":"crossref","unstructured":"H. Wang, Basis set approach to the quantum dissipative dynamics: application of the multiconfiguration time-dependent Hartree method to the spin-boson problem, J. Chem. Phys. 113 (2000), no. 22, 9948\u20139956.","DOI":"10.1063\/1.1323746"},{"key":"45","doi-asserted-by":"crossref","unstructured":"T. Zhang, Solving large scale linear prediction problems using stochastic gradient descent algorithms, Proceedings of the Twenty-First International Conference on Machine Learning (New York, NY, USA), Association for Computing Machinery, 2004, p. 116.","DOI":"10.1145\/1015330.1015332"},{"key":"46","doi-asserted-by":"publisher","first-page":"1338","DOI":"10.1063\/1.1731409","article-title":"Ensemble method in the theory of irreversibility","volume":"33","author":"Zwanzig, Robert","year":"1960","journal-title":"J. Chem. Phys.","ISSN":"https:\/\/id.crossref.org\/issn\/0021-9606","issn-type":"print"}],"container-title":["Mathematics of Computation"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/www.ams.org\/mcom\/2023-92-341\/S0025-5718-2022-03785-6\/mcom3785_AM.pdf","content-type":"application\/pdf","content-version":"am","intended-application":"syndication"},{"URL":"https:\/\/www.ams.org\/mcom\/2023-92-341\/S0025-5718-2022-03785-6\/S0025-5718-2022-03785-6.pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2026,4,22]],"date-time":"2026-04-22T04:53:49Z","timestamp":1776833629000},"score":1,"resource":{"primary":{"URL":"https:\/\/www.ams.org\/mcom\/2023-92-341\/S0025-5718-2022-03785-6\/"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2022,11,21]]},"references-count":46,"journal-issue":{"issue":"341","published-print":{"date-parts":[[2023,5]]}},"alternative-id":["S0025-5718-2022-03785-6"],"URL":"https:\/\/doi.org\/10.1090\/mcom\/3785","archive":["CLOCKSS","Portico"],"relation":{},"ISSN":["1088-6842","0025-5718"],"issn-type":[{"value":"1088-6842","type":"electronic"},{"value":"0025-5718","type":"print"}],"subject":[],"published":{"date-parts":[[2022,11,21]]}}}