1Dahlem Center for Complex Quantum Systems, Freie Universität Berlin, 14195 Berlin, Germany
2Institute for Integrated Circuits, Johannes Kepler University Linz, Austria
3Centre for Quantum Computation and Communication Technology, Centre for Quantum Software and Information, University of Technology Sydney, NSW 2007, Australia
4Helmholtz-Zentrum Berlin für Materialien und Energie, Hahn-Meitner-Platz 1, 14109 Berlin, Germany
Find this paper interesting or want to discuss? Scite or leave a comment on SciRate.
Abstract
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.
Featured image: Overview of the introduced randomized sampling framework for estimating the dynamics of observables. After preparing a multi-product formula for importance sampling, we can run Algorithm 1 of our work to implement it in a simple, randomized fashion. While this overview already hints toward its use for time evolution and estimating the dynamics of observables, these results apply to general multi-product formulas.
Popular summary
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.
► BibTeX data
► References
[1] 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).
https://doi.org/10.1088/1367-2630/aad1ea
[2] S. Lloyd. ``Universal quantum simulators''. Science 273, 1073–1078 (1996).
https://doi.org/10.1126/science.273.5278.1073
[3] D. Aharonov and A. Ta-Shma. ``Adiabatic Quantum State Generation and Statistical Zero Knowledge''. arXiv:quant-ph/0301023. (2003).
https://doi.org/10.48550/arXiv.quant-ph/0301023
arXiv:quant-ph/0301023
[4] 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).
https://doi.org/10.1007/s00220-006-0150-x
[5] N. Wiebe, D. Berry, P. Høyer, and B. C. Sanders. ``Higher order decompositions of ordered operator exponentials''. J. Phys. A 43, 065203 (2010).
https://doi.org/10.1088/1751-8113/43/6/065203
[6] 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).
https://doi.org/10.1088/1751-8113/44/44/445308
[7] 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).
https://doi.org/10.1103/PhysRevLett.106.170501
[8] M. Kliesch, T. Barthel, C. Gogolin, M. Kastoryano, and J. Eisert. ``Dissipative quantum Church-Turing theorem''. Phys. Rev. Lett. 107, 120501 (2011).
https://doi.org/10.1103/PhysRevLett.107.120501
[9] 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).
https://doi.org/10.1103/PhysRevA.94.022317
[10] A. M. Childs, D. Maslov, Y. Nam, N. J. Ross, and Y. Su. ``Toward the first quantum simulation with quantum speedup''. PNAS 115, 9456–9461 (2018).
https://doi.org/10.1073/pnas.1801723115
[11] A. M. Childs, Y. Su, M. C. Tran, N. Wiebe, and S. Zhu. ``Theory of Trotter error with commutator scaling''. Phys. Rev. X 11, 011020 (2021).
https://doi.org/10.1103/PhysRevX.11.011020
[12] A. M. Childs and Y. Su. ``Nearly optimal lattice simulation by product formulas''. Phys. Rev. Lett. 123, 050503 (2019).
https://doi.org/10.1103/PhysRevLett.123.050503
[13] A. M. Childs and N. Wiebe. ``Hamiltonian simulation using linear combinations of unitary operations''. Quant. Inf. Comp. 12, 901–924 (2012).
https://doi.org/10.26421/QIC12.11-12-1
[14] G. H. Low, V. Kliuchnikov, and N. Wiebe. ``Well-conditioned multiproduct Hamiltonian simulation''. arXiv:1907.11679. (2019).
https://doi.org/10.48550/arXiv.1907.11679
arXiv:1907.11679
[15] 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).
https://doi.org/10.1109/focs.2015.54
[16] 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).
https://doi.org/10.1145/2591796.2591854
[17] 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).
https://doi.org/10.1103/PhysRevLett.114.090502
[18] G. H. Low and I. L. Chuang. ``Hamiltonian simulation by qubitization''. Quantum 3, 163 (2019).
https://doi.org/10.22331/q-2019-07-12-163
[19] 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).
https://doi.org/10.7566/JPSJ.90.032001
[20] E. T. Campbell. ``Shorter gate sequences for quantum computing by mixing unitaries''. Phys. Rev. A 95, 042306 (2017).
https://doi.org/10.1103/PhysRevA.95.042306
[21] E. T. Campbell. ``Random compiler for fast Hamiltonian simulation''. Phys. Rev. Lett. 123, 070503 (2019).
https://doi.org/10.1103/PhysRevLett.123.070503
[22] A. M. Childs, A. Ostrander, and Y. Su. ``Faster quantum simulation by randomization''. Quantum 3, 182 (2019).
https://doi.org/10.22331/q-2019-09-02-182
[23] Y. Ouyang, D. R. White, and E. T. Campbell. ``Compilation by stochastic Hamiltonian sparsification''. Quantum 4, 235 (2020).
https://doi.org/10.22331/q-2020-02-27-235
[24] C.-F. Chen, H.-Y. Huang, R. Kueng, and J. A. Tropp. ``Concentration for random product formulas''. PRX Quantum 2, 040305 (2021).
https://doi.org/10.1103/PRXQuantum.2.040305
[25] J. Preskill. ``Quantum computing in the NISQ era and beyond''. Quantum 2, 79 (2018).
https://doi.org/10.22331/q-2018-08-06-79
[26] M. Suzuki. ``General theory of fractal path integrals with applications to many-body theories and statistical physics''. J. Math. Phys. 32, 400–407 (1991).
https://doi.org/10.1063/1.529425
[27] S. Blanes, F. Casas, and J. Ros. ``Extrapolation of symplectic Integrators''. Cel. Mech. Dyn. Astr. 75, 149–161 (1999).
https://doi.org/10.1023/A:1008364504014
[28] S. A. Chin. ``Multi-product splitting and Runge-Kutta-Nyström integrators''. Cel. Mech. Dyn. Astr. 106, 391–406 (2010).
https://doi.org/10.1007/s10569-010-9255-9
[29] H. Yoshida. ``Construction of higher order symplectic integrators''. Physics Letters A 150, 262–268 (1990).
https://doi.org/10.1016/0375-9601(90)90092-3
[30] W. Hoeffding. ``Probability inequalities for sums of bounded random variables''. J. Am. Stat. Ass. 58, 13–30 (1963).
https://doi.org/10.1080/01621459.1963.10500830
[31] Q. Sheng. ``Solving linear partial differential equations by exponential splitting''. IMA Journal of Numerical Analysis 9, 199–212 (1989).
https://doi.org/10.1093/imanum/9.2.199
[32] T. A. Bespalova and O. Kyriienko. ``Hamiltonian operator approximation for energy measurement and ground-state preparation''. PRX Quantum 2, 030318 (2021).
https://doi.org/10.1103/PRXQuantum.2.030318
[33] 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).
https://doi.org/10.1038/s41567-020-0932-7
[34] 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).
[35] F. S. V. Bazán. ``Conditioning of rectangular Vandermonde matrices with nodes in the unit disk''. SIAM J. Mat. An. App. 21, 679–693 (2000).
https://doi.org/10.1137/S0895479898336021
[36] M. E. A. El-Mikkawy. ``Explicit inverse of a generalized Vandermonde matrix''. Appl. Math. Comp. 146, 643–651 (2003).
https://doi.org/10.1016/S0096-3003(02)00609-4
[37] 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.
[38] 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).
https://doi.org/10.1103/PhysRevA.99.040301
[39] 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).
https://doi.org/10.1088/2058-9565/ab8ebc
[40] 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).
https://doi.org/10.1038/nphys2232
[41] A. Parra-Rodriguez, P. Lougovski, L. Lamata, E. Solano, and M. Sanz. ``Digital-analog quantum computation''. Phys. Rev. A 101, 022305 (2020).
https://doi.org/10.1103/PhysRevA.101.022305
[42] 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).
https://doi.org/10.1038/s42005-022-00930-2
Cited by
[1] Andrew M. Childs, Yuan Su, Minh C. Tran, Nathan Wiebe, and Shuchen Zhu, "A Theory of Trotter Error", arXiv:1912.08854.
[2] 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).
[3] Troy J. Sewell and Christopher David White, "Mana and thermalization: probing the feasibility of near-Clifford Hamiltonian simulation", arXiv:2201.12367.
[4] Robert I. McLachlan, "Tuning Symplectic Integrators is Easy and Worthwhile", Communications in Computational Physics 31 3, 987 (2022).
[5] 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).
[6] Xiantao Li, "Some error analysis for the quantum phase estimation algorithms", Journal of Physics A Mathematical General 55 32, 325303 (2022).
[7] Chi-Fang Chen, Hsin-Yuan Huang, Richard Kueng, and Joel A. Tropp, "Concentration for Random Product Formulas", PRX Quantum 2 4, 040305 (2021).
[8] Jacob Watkins, Nathan Wiebe, Alessandro Roggero, and Dean Lee, "Time-dependent Hamiltonian Simulation Using Discrete Clock Constructions", arXiv:2203.11353.
[9] Mingxia Huo and Ying Li, "Error-resilient Monte Carlo quantum simulation of imaginary time", arXiv:2109.07807.
[10] Zhicheng Zhang, Qisheng Wang, and Mingsheng Ying, "Parallel Quantum Algorithm for Hamiltonian Simulation", arXiv:2105.11889.
[11] Lingling Lao and Dan E. Browne, "2QAN: A quantum compiler for 2-local qubit Hamiltonian simulation algorithms", arXiv:2108.02099.
[12] Changhao Yi, "Success of digital adiabatic simulation with large Trotter step", Physical Review A 104 5, 052603 (2021).
[13] 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).
[14] Matthew Hagan and Nathan Wiebe, "Composite Quantum Simulations", arXiv:2206.06409.
The above citations are from SAO/NASA ADS (last updated successfully 2022-09-19 22:19:07). 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-09-19 22:19:05).
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.
