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 multiproduct 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–Ye–Kitaev model, for which the method provides a favorable scaling in the effort.
But there is a new key ingredient that enters here that renders the task of simulating quantum many-body systems easier: This is randomness. It is too much to ask of the algorithm to lead to the correct result in every run. Instead, being exact only on average is much more resource-efficient.
Consequently, we propose randomly applying gates, generating the desired superpositions required for higher-order schemes on average, giving rise to more precise implementations. We find that this random compilation avoids the need for complex quantum circuits while maintaining the benefits of more accurate, higher-order schemes.
This work introduces new techniques that make quantum simulators feasible already in the intermediate regime of programmable quantum devices. It is thus more suited for near- and intermediate-term devices. Due to its comparative simplicity, our scheme could also apply to programmable quantum simulators. Within the developed framework, there is a lot of potential for new methods, for example, more efficient ways of determining ground states.
 A. Acín, 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''. New J. Phys. 20, 080201 (2018).
 D. Aharonov and A. Ta-Shma. ``Adiabatic Quantum State Generation and Statistical Zero Knowledge''. arXiv:quant-ph/0301023. (2003).
 D. W. Berry, G. Ahokas, R. Cleve, and B. C. Sanders. ``Efficient Quantum algorithms for simulating sparse Hamiltonians''. Commun. Math. Phys. 270, 359–371 (2007).
 N. Wiebe, D. Berry, P. Høyer, and B. C. Sanders. ``Higher order decompositions of ordered operator exponentials''. J. Phys. A 43, 065203 (2010).
 N. Wiebe, D. W. Berry, P. Høyer, and B. C. Sanders. ``Simulating quantum dynamics on a quantum computer''. J. Phys. A 44, 445308 (2011).
 D. Poulin, A. Qarry, R. Somma, and F. Verstraete. ``Quantum simulation of time-dependent Hamiltonians and the convenient illusion of Hilbert space''. Phys. Rev. Lett. 106, 170501 (2011).
 M. Kliesch, T. Barthel, C. Gogolin, M. Kastoryano, and J. Eisert. ``Dissipative quantum Church-Turing theorem''. Phys. Rev. Lett. 107, 120501 (2011).
 R. Sweke, M. Sanz, I. Sinayskiy, F. Petruccione, and E. Solano. ``Digital quantum simulation of many-body non-Markovian dynamics''. Phys. Rev. A 94, 022317 (2016).
 A. M. Childs and Y. Su. ``Nearly optimal lattice simulation by product formulas''. Phys. Rev. Lett. 123, 050503 (2019).
 D. W. Berry, A. M. Childs, and R. Kothari. ``Hamiltonian simulation with nearly optimal dependence on all parameters''. 2015 IEEE 56th Annual Symposium on Foundations of Computer Science (2015).
 D. W. Berry, A. M. Childs, R. Cleve, R. Kothari, and R. D. Somma. ``Exponential improvement in precision for simulating sparse hamiltonians''. Proceedings of the forty-sixth annual ACM symposium on Theory of computing (2014).
 D. W. Berry, A. M. Childs, R. Cleve, R. Kothari, and R. D. Somma. ``Simulating Hamiltonian dynamics with a truncated Taylor series''. Phys. Rev. Lett. 114, 090502 (2015).
 S. Endo, Z. Cai, S. C. Benjamin, and X. Yuan. ``Hybrid quantum-classical algorithms and quantum error mitigation''. J. Phys. Soc. Jap. 90, 032001 (2021).
 E. T. Campbell. ``Random compiler for fast Hamiltonian simulation''. Phys. Rev. Lett. 123, 070503 (2019).
 W. Hoeffding. ``Probability inequalities for sums of bounded random variables''. J. Am. Stat. Ass. 58, 13–30 (1963).
 T. A. Bespalova and O. Kyriienko. ``Hamiltonian operator approximation for energy measurement and ground-state preparation''. PRX Quantum 2, 030318 (2021).
 H.-Y. Huang, R. Kueng, and J. Preskill. ``Predicting many properties of a quantum system from very few measurements''. Nature Phys. 16, 1050–1057 (2020).
 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''. Univ. California Publ. Statist. 3, 37–98 (1960).
 D.E. Knuth. ``The art of computer programming: Fundamental algorithms''. Number v. 1-2 in Addison-Wesley Series in Computer Science and Information Processing. Addison-Wesley. (1973). subsequent edition.
 R. Babbush, D. W. Berry, and H. Neven. ``Quantum simulation of the Sachdev-Ye-Kitaev model by asymmetric qubitization''. Phys. Rev. A 99, 040301 (2019).
 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äner, T. Hardikar, V. Havlíček, O. Higgott, C. Huang, J. Izaac, Z. Jiang, X. Liu, S. McArdle, M. Neeley, T. O'Brien, B. O'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''. Quant. Sc. Tech. 5, 034014 (2020).
 S. Trotzky, Y.-A. Chen, A. Flesch, I. P. McCulloch, U. Schollwöck, J. Eisert, and I. Bloch. ``Probing the relaxation towards equilibrium in an isolated strongly correlated one-dimensional Bose gas''. Nature Phys. 8, 325–330 (2012).
 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''. Communications Physics 5 (2022).
 Andrew M. Childs, Yuan Su, Minh C. Tran, Nathan Wiebe, and Shuchen Zhu, "A Theory of Trotter Error", arXiv:1912.08854.
 Natalie Klco, Alessandro Roggero, and Martin J. Savage, "Standard model physics and the digital quantum revolution: thoughts about the interface", Reports on Progress in Physics 85 6, 064301 (2022).
 Troy J. Sewell and Christopher David White, "Mana and thermalization: Probing the feasibility of near-Clifford Hamiltonian simulation", Physical Review B 106 12, 125130 (2022).
 Robert I. McLachlan, "Tuning Symplectic Integrators is Easy and Worthwhile", Communications in Computational Physics 31 3, 987 (2022).
 Yongdan Yang, Bing-Nan Lu, and Ying Li, "Accelerated Quantum Monte Carlo with Mitigated Error on Noisy Quantum Computer", PRX Quantum 2 4, 040361 (2021).
 Chi-Fang Chen, Hsin-Yuan Huang, Richard Kueng, and Joel A. Tropp, "Concentration for Random Product Formulas", PRX Quantum 2 4, 040305 (2021).
 Xiantao Li, "Some error analysis for the quantum phase estimation algorithms", Journal of Physics A Mathematical General 55 32, 325303 (2022).
 Jacob Watkins, Nathan Wiebe, Alessandro Roggero, and Dean Lee, "Time-dependent Hamiltonian Simulation Using Discrete Clock Constructions", arXiv:2203.11353.
 Mingxia Huo and Ying Li, "Error-resilient Monte Carlo quantum simulation of imaginary time", arXiv:2109.07807.
 Lingling Lao and Dan E. Browne, "2QAN: A quantum compiler for 2-local qubit Hamiltonian simulation algorithms", arXiv:2108.02099.
 Zhicheng Zhang, Qisheng Wang, and Mingsheng Ying, "Parallel Quantum Algorithm for Hamiltonian Simulation", arXiv:2105.11889.
 Changhao Yi, "Success of digital adiabatic simulation with large Trotter step", Physical Review A 104 5, 052603 (2021).
 Yi Hu, Fanxu Meng, Xiaojun Wang, Tian Luan, Yulong Fu, Zaichen Zhang, Xianchao Zhang, and Xutao Yu, "Greedy algorithm based circuit optimization for near-term quantum simulation", Quantum Science and Technology 7 4, 045001 (2022).
 Matthew Hagan and Nathan Wiebe, "Composite Quantum Simulations", arXiv:2206.06409.
The above citations are from SAO/NASA ADS (last updated successfully 2022-10-01 23:22:57). The list may be incomplete as not all publishers provide suitable and complete citation data.
On Crossref's cited-by service no data on citing works was found (last attempt 2022-10-01 23:22:56).
This Paper is published in Quantum under the Creative Commons Attribution 4.0 International (CC BY 4.0) license. Copyright remains with the original copyright holders such as the authors or their institutions.