{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,3,17]],"date-time":"2026-03-17T04:46:03Z","timestamp":1773722763583,"version":"3.50.1"},"reference-count":42,"publisher":"Verein zur Forderung des Open Access Publizierens in den Quantenwissenschaften","license":[{"start":{"date-parts":[[2022,9,19]],"date-time":"2022-09-19T00:00:00Z","timestamp":1663545600000},"content-version":"unspecified","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0\/"}],"funder":[{"DOI":"10.13039\/501100022235","name":"ARC Centre of Excellence for Quantum Computation and Communication Technology","doi-asserted-by":"crossref","award":["CE170100012"],"award-info":[{"award-number":["CE170100012"]}],"id":[{"id":"10.13039\/501100022235","id-type":"DOI","asserted-by":"crossref"}]},{"name":"BMWK","award":["01MK20005G"],"award-info":[{"award-number":["01MK20005G"]}]},{"name":"BMWK","award":["01MQ22007D"],"award-info":[{"award-number":["01MQ22007D"]}]},{"name":"BMBF","award":["13N15892"],"award-info":[{"award-number":["13N15892"]}]},{"name":"BMBF","award":["13N115892"],"award-info":[{"award-number":["13N115892"]}]},{"name":"Bayrisches Staatsministerium fuer Wissenschaft und Kunst","award":["Z.5-F5121.17.1\/6\/26"],"award-info":[{"award-number":["Z.5-F5121.17.1\/6\/26"]}]},{"name":"EUROPEAN COMMISSION Directorate-General Communications Networks, Content and Technology Digital Excellence & Science infrastructure High Performance Computing & Quantum Technology","award":["817482"],"award-info":[{"award-number":["817482"]}]}],"content-domain":{"domain":["quantum-journal.org"],"crossmark-restriction":false},"short-container-title":["Quantum"],"abstract":"<jats:p>Quantum simulation, the simulation of quantum processes on quantum computers, suggests a path forward for the efficient simulation of problems in condensed-matter physics, quantum chemistry, and materials science. While the majority of quantum simulation algorithms are deterministic, a recent surge of ideas has shown that randomization can greatly benefit algorithmic performance. In this work, we introduce a scheme for quantum simulation that unites the advantages of randomized compiling on the one hand and higher-order multi-product formulas, as they are used for example in linear-combination-of-unitaries (LCU) algorithms or quantum error mitigation, on the other hand. In doing so, we propose a framework of randomized sampling that is expected to be useful for programmable quantum simulators and present two new multi-product formula algorithms tailored to it. Our framework reduces the circuit depth by circumventing the need for oblivious amplitude amplification required by the implementation of multi-product formulas using standard LCU methods, rendering it especially useful for early quantum computers used to estimate the dynamics of quantum systems instead of performing full-fledged quantum phase estimation. Our algorithms achieve a simulation error that shrinks exponentially with the circuit depth. To corroborate their functioning, we prove rigorous performance bounds as well as the concentration of the randomized sampling procedure. We demonstrate the functioning of the approach for several physically meaningful examples of Hamiltonians, including fermionic systems and the Sachdev\u2013Ye\u2013Kitaev model, for which the method provides a favorable scaling in the effort.<\/jats:p>","DOI":"10.22331\/q-2022-09-19-806","type":"journal-article","created":{"date-parts":[[2022,9,19]],"date-time":"2022-09-19T10:20:04Z","timestamp":1663582804000},"page":"806","update-policy":"https:\/\/doi.org\/10.22331\/q-crossmark-policy-page","source":"Crossref","is-referenced-by-count":38,"title":["Randomizing multi-product formulas for Hamiltonian simulation"],"prefix":"10.22331","volume":"6","author":[{"given":"Paul K.","family":"Faehrmann","sequence":"first","affiliation":[{"name":"Dahlem Center for Complex Quantum Systems, Freie Universit\u00e4t Berlin, 14195 Berlin, Germany"}]},{"given":"Mark","family":"Steudtner","sequence":"additional","affiliation":[{"name":"Dahlem Center for Complex Quantum Systems, Freie Universit\u00e4t Berlin, 14195 Berlin, Germany"}]},{"given":"Richard","family":"Kueng","sequence":"additional","affiliation":[{"name":"Institute for Integrated Circuits, Johannes Kepler University Linz, Austria"}]},{"given":"Maria","family":"Kieferova","sequence":"additional","affiliation":[{"name":"Centre for Quantum Computation and Communication Technology, Centre for Quantum Software and Information, University of Technology Sydney, NSW 2007, Australia"}]},{"given":"Jens","family":"Eisert","sequence":"additional","affiliation":[{"name":"Dahlem Center for Complex Quantum Systems, Freie Universit\u00e4t Berlin, 14195 Berlin, Germany"},{"name":"Helmholtz-Zentrum Berlin f\u00fcr Materialien und Energie, Hahn-Meitner-Platz 1, 14109 Berlin, Germany"}]}],"member":"9598","published-online":{"date-parts":[[2022,9,19]]},"reference":[{"key":"0","doi-asserted-by":"publisher","unstructured":"A. Ac\u00edn, I. Bloch, H. Buhrman, T. Calarco, C. Eichler, J. Eisert, D. Esteve, N. Gisin, S. J. Glaser, F. Jelezko, S. Kuhr, M. Lewenstein, M. F. Riedel, P. O. Schmidt, R. Thew, A. Wallraff, I. Walmsley, and F. K. Wilhelm. ``The quantum technologies roadmap: A European community view&apos;&apos;. New J. Phys. 20, 080201 (2018).","DOI":"10.1088\/1367-2630\/aad1ea"},{"key":"1","doi-asserted-by":"publisher","unstructured":"S. Lloyd. ``Universal quantum simulators&apos;&apos;. Science 273, 1073\u20131078 (1996).","DOI":"10.1126\/science.273.5278.1073"},{"key":"2","doi-asserted-by":"publisher","unstructured":"D. Aharonov and A. Ta-Shma. ``Adiabatic Quantum State Generation and Statistical Zero Knowledge&apos;&apos;. arXiv:quant-ph\/0301023. (2003).","DOI":"10.48550\/arXiv.quant-ph\/0301023"},{"key":"3","doi-asserted-by":"publisher","unstructured":"D. W. Berry, G. Ahokas, R. Cleve, and B. C. Sanders. ``Efficient Quantum algorithms for simulating sparse Hamiltonians&apos;&apos;. Commun. Math. Phys. 270, 359\u2013371 (2007).","DOI":"10.1007\/s00220-006-0150-x"},{"key":"4","doi-asserted-by":"publisher","unstructured":"N. Wiebe, D. Berry, P. H\u00f8yer, and B. C. Sanders. ``Higher order decompositions of ordered operator exponentials&apos;&apos;. J. Phys. A 43, 065203 (2010).","DOI":"10.1088\/1751-8113\/43\/6\/065203"},{"key":"5","doi-asserted-by":"publisher","unstructured":"N. Wiebe, D. W. Berry, P. H\u00f8yer, and B. C. Sanders. ``Simulating quantum dynamics on a quantum computer&apos;&apos;. J. Phys. A 44, 445308 (2011).","DOI":"10.1088\/1751-8113\/44\/44\/445308"},{"key":"6","doi-asserted-by":"publisher","unstructured":"D. Poulin, A. Qarry, R. Somma, and F. Verstraete. ``Quantum simulation of time-dependent Hamiltonians and the convenient illusion of Hilbert space&apos;&apos;. Phys. Rev. Lett. 106, 170501 (2011).","DOI":"10.1103\/PhysRevLett.106.170501"},{"key":"7","doi-asserted-by":"publisher","unstructured":"M. Kliesch, T. Barthel, C. Gogolin, M. Kastoryano, and J. Eisert. ``Dissipative quantum Church-Turing theorem&apos;&apos;. Phys. Rev. Lett. 107, 120501 (2011).","DOI":"10.1103\/PhysRevLett.107.120501"},{"key":"8","doi-asserted-by":"publisher","unstructured":"R. Sweke, M. Sanz, I. Sinayskiy, F. Petruccione, and E. Solano. ``Digital quantum simulation of many-body non-Markovian dynamics&apos;&apos;. Phys. Rev. A 94, 022317 (2016).","DOI":"10.1103\/PhysRevA.94.022317"},{"key":"9","doi-asserted-by":"publisher","unstructured":"A. M. Childs, D. Maslov, Y. Nam, N. J. Ross, and Y. Su. ``Toward the first quantum simulation with quantum speedup&apos;&apos;. PNAS 115, 9456\u20139461 (2018).","DOI":"10.1073\/pnas.1801723115"},{"key":"10","doi-asserted-by":"publisher","unstructured":"A. M. Childs, Y. Su, M. C. Tran, N. Wiebe, and S. Zhu. ``Theory of Trotter error with commutator scaling&apos;&apos;. Phys. Rev. X 11, 011020 (2021).","DOI":"10.1103\/PhysRevX.11.011020"},{"key":"11","doi-asserted-by":"publisher","unstructured":"A. M. Childs and Y. Su. ``Nearly optimal lattice simulation by product formulas&apos;&apos;. Phys. Rev. Lett. 123, 050503 (2019).","DOI":"10.1103\/PhysRevLett.123.050503"},{"key":"12","doi-asserted-by":"publisher","unstructured":"A. M. Childs and N. Wiebe. ``Hamiltonian simulation using linear combinations of unitary operations&apos;&apos;. Quant. Inf. Comp. 12, 901\u2013924 (2012).","DOI":"10.26421\/QIC12.11-12-1"},{"key":"13","doi-asserted-by":"publisher","unstructured":"G. H. Low, V. Kliuchnikov, and N. Wiebe. ``Well-conditioned multiproduct Hamiltonian simulation&apos;&apos;. arXiv:1907.11679. (2019).","DOI":"10.48550\/arXiv.1907.11679"},{"key":"14","doi-asserted-by":"publisher","unstructured":"D. W. Berry, A. M. Childs, and R. Kothari. ``Hamiltonian simulation with nearly optimal dependence on all parameters&apos;&apos;. 2015 IEEE 56th Annual Symposium on Foundations of Computer Science (2015).","DOI":"10.1109\/focs.2015.54"},{"key":"15","doi-asserted-by":"publisher","unstructured":"D. W. Berry, A. M. Childs, R. Cleve, R. Kothari, and R. D. Somma. ``Exponential improvement in precision for simulating sparse hamiltonians&apos;&apos;. Proceedings of the forty-sixth annual ACM symposium on Theory of computing (2014).","DOI":"10.1145\/2591796.2591854"},{"key":"16","doi-asserted-by":"publisher","unstructured":"D. W. Berry, A. M. Childs, R. Cleve, R. Kothari, and R. D. Somma. ``Simulating Hamiltonian dynamics with a truncated Taylor series&apos;&apos;. Phys. Rev. Lett. 114, 090502 (2015).","DOI":"10.1103\/PhysRevLett.114.090502"},{"key":"17","doi-asserted-by":"publisher","unstructured":"G. H. Low and I. L. Chuang. ``Hamiltonian simulation by qubitization&apos;&apos;. Quantum 3, 163 (2019).","DOI":"10.22331\/q-2019-07-12-163"},{"key":"18","doi-asserted-by":"publisher","unstructured":"S. Endo, Z. Cai, S. C. Benjamin, and X. Yuan. ``Hybrid quantum-classical algorithms and quantum error mitigation&apos;&apos;. J. Phys. Soc. Jap. 90, 032001 (2021).","DOI":"10.7566\/JPSJ.90.032001"},{"key":"19","doi-asserted-by":"publisher","unstructured":"E. T. Campbell. ``Shorter gate sequences for quantum computing by mixing unitaries&apos;&apos;. Phys. Rev. A 95, 042306 (2017).","DOI":"10.1103\/PhysRevA.95.042306"},{"key":"20","doi-asserted-by":"publisher","unstructured":"E. T. Campbell. ``Random compiler for fast Hamiltonian simulation&apos;&apos;. Phys. Rev. Lett. 123, 070503 (2019).","DOI":"10.1103\/PhysRevLett.123.070503"},{"key":"21","doi-asserted-by":"publisher","unstructured":"A. M. Childs, A. Ostrander, and Y. Su. ``Faster quantum simulation by randomization&apos;&apos;. Quantum 3, 182 (2019).","DOI":"10.22331\/q-2019-09-02-182"},{"key":"22","doi-asserted-by":"publisher","unstructured":"Y. Ouyang, D. R. White, and E. T. Campbell. ``Compilation by stochastic Hamiltonian sparsification&apos;&apos;. Quantum 4, 235 (2020).","DOI":"10.22331\/q-2020-02-27-235"},{"key":"23","doi-asserted-by":"publisher","unstructured":"C.-F. Chen, H.-Y. Huang, R. Kueng, and J. A. Tropp. ``Concentration for random product formulas&apos;&apos;. PRX Quantum 2, 040305 (2021).","DOI":"10.1103\/PRXQuantum.2.040305"},{"key":"24","doi-asserted-by":"publisher","unstructured":"J. Preskill. ``Quantum computing in the NISQ era and beyond&apos;&apos;. Quantum 2, 79 (2018).","DOI":"10.22331\/q-2018-08-06-79"},{"key":"25","doi-asserted-by":"publisher","unstructured":"M. Suzuki. ``General theory of fractal path integrals with applications to many-body theories and statistical physics&apos;&apos;. J. Math. Phys. 32, 400\u2013407 (1991).","DOI":"10.1063\/1.529425"},{"key":"26","doi-asserted-by":"publisher","unstructured":"S. Blanes, F. Casas, and J. Ros. ``Extrapolation of symplectic Integrators&apos;&apos;. Cel. Mech. Dyn. Astr. 75, 149\u2013161 (1999).","DOI":"10.1023\/A:1008364504014"},{"key":"27","doi-asserted-by":"publisher","unstructured":"S. A. Chin. ``Multi-product splitting and Runge-Kutta-Nystr\u00f6m integrators&apos;&apos;. Cel. Mech. Dyn. Astr. 106, 391\u2013406 (2010).","DOI":"10.1007\/s10569-010-9255-9"},{"key":"28","doi-asserted-by":"publisher","unstructured":"H. Yoshida. ``Construction of higher order symplectic integrators&apos;&apos;. Physics Letters A 150, 262\u2013268 (1990).","DOI":"10.1016\/0375-9601(90)90092-3"},{"key":"29","doi-asserted-by":"publisher","unstructured":"W. Hoeffding. ``Probability inequalities for sums of bounded random variables&apos;&apos;. J. Am. Stat. Ass. 58, 13\u201330 (1963).","DOI":"10.1080\/01621459.1963.10500830"},{"key":"30","doi-asserted-by":"publisher","unstructured":"Q. Sheng. ``Solving linear partial differential equations by exponential splitting&apos;&apos;. IMA Journal of Numerical Analysis 9, 199\u2013212 (1989).","DOI":"10.1093\/imanum\/9.2.199"},{"key":"31","doi-asserted-by":"publisher","unstructured":"T. A. Bespalova and O. Kyriienko. ``Hamiltonian operator approximation for energy measurement and ground-state preparation&apos;&apos;. PRX Quantum 2, 030318 (2021).","DOI":"10.1103\/PRXQuantum.2.030318"},{"key":"32","doi-asserted-by":"publisher","unstructured":"H.-Y. Huang, R. Kueng, and J. Preskill. ``Predicting many properties of a quantum system from very few measurements&apos;&apos;. Nature Phys. 16, 1050\u20131057 (2020).","DOI":"10.1038\/s41567-020-0932-7"},{"key":"33","unstructured":"L. Le Cam. ``Locally asymptotically normal families of distributions. Certain approximations to families of distributions and their use in the theory of estimation and testing hypotheses&apos;&apos;. Univ. California Publ. Statist. 3, 37\u201398 (1960)."},{"key":"34","doi-asserted-by":"publisher","unstructured":"F. S. V. Baz\u00e1n. ``Conditioning of rectangular Vandermonde matrices with nodes in the unit disk&apos;&apos;. SIAM J. Mat. An. App. 21, 679\u2013693 (2000).","DOI":"10.1137\/S0895479898336021"},{"key":"35","doi-asserted-by":"publisher","unstructured":"M. E. A. El-Mikkawy. ``Explicit inverse of a generalized Vandermonde matrix&apos;&apos;. Appl. Math. Comp. 146, 643\u2013651 (2003).","DOI":"10.1016\/S0096-3003(02)00609-4"},{"key":"36","unstructured":"D.E. Knuth. ``The art of computer programming: Fundamental algorithms&apos;&apos;. Number v. 1-2 in Addison-Wesley Series in Computer Science and Information Processing. Addison-Wesley. (1973). subsequent edition."},{"key":"37","doi-asserted-by":"publisher","unstructured":"R. Babbush, D. W. Berry, and H. Neven. ``Quantum simulation of the Sachdev-Ye-Kitaev model by asymmetric qubitization&apos;&apos;. Phys. Rev. A 99, 040301 (2019).","DOI":"10.1103\/PhysRevA.99.040301"},{"key":"38","doi-asserted-by":"publisher","unstructured":"J. R. McClean, N. C. Rubin, K. J. Sung, I. D. Kivlichan, X. Bonet-Monroig, Y. Cao, C. Dai, E. S. Fried, C. Gidney, B. Gimby, P. Gokhale, T. H\u00e4ner, T. Hardikar, V. Havl\u00ed\u010dek, O. Higgott, C. Huang, J. Izaac, Z. Jiang, X. Liu, S. McArdle, M. Neeley, T. O&apos;Brien, B. O&apos;Gorman, I. Ozfidan, M. D. Radin, J. Romero, N. P. D. Sawaya, B. Senjean, K. Setia, S. Sim, D. S. Steiger, M. Steudtner, Q. Sun, W. Sun, D. Wang, F. Zhang, and R. Babbush. ``OpenFermion: The electronic structure package for quantum computers&apos;&apos;. Quant. Sc. Tech. 5, 034014 (2020).","DOI":"10.1088\/2058-9565\/ab8ebc"},{"key":"39","doi-asserted-by":"publisher","unstructured":"S. Trotzky, Y.-A. Chen, A. Flesch, I. P. McCulloch, U. Schollw\u00f6ck, J. Eisert, and I. Bloch. ``Probing the relaxation towards equilibrium in an isolated strongly correlated one-dimensional Bose gas&apos;&apos;. Nature Phys. 8, 325\u2013330 (2012).","DOI":"10.1038\/nphys2232"},{"key":"40","doi-asserted-by":"publisher","unstructured":"A. Parra-Rodriguez, P. Lougovski, L. Lamata, E. Solano, and M. Sanz. ``Digital-analog quantum computation&apos;&apos;. Phys. Rev. A 101, 022305 (2020).","DOI":"10.1103\/PhysRevA.101.022305"},{"key":"41","doi-asserted-by":"publisher","unstructured":"R. Sweke, P. Boes, N. Ng, C. Sparaciari, J. Eisert, and M. Goihl. ``Transparent reporting of research-related greenhouse gas emissions through the scientific CO2nduct initiative&apos;&apos;. Communications Physics 5 (2022).","DOI":"10.1038\/s42005-022-00930-2"}],"container-title":["Quantum"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/quantum-journal.org\/papers\/q-2022-09-19-806\/pdf\/","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"}],"deposited":{"date-parts":[[2022,10,3]],"date-time":"2022-10-03T12:23:19Z","timestamp":1664799799000},"score":1,"resource":{"primary":{"URL":"https:\/\/quantum-journal.org\/papers\/q-2022-09-19-806\/"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2022,9,19]]},"references-count":42,"URL":"https:\/\/doi.org\/10.22331\/q-2022-09-19-806","archive":["CLOCKSS"],"relation":{},"ISSN":["2521-327X"],"issn-type":[{"value":"2521-327X","type":"electronic"}],"subject":[],"published":{"date-parts":[[2022,9,19]]},"article-number":"806"}}