Complexity of Digital Quantum Simulation in the Low-Energy Subspace: Applications and a Lower Bound

Weiyuan Gong; Shuo Zhou; Tongyang Li

doi:10.22331/q-2024-07-15-1409

Complexity of Digital Quantum Simulation in the Low-Energy Subspace: Applications and a Lower Bound

Weiyuan Gong^1,2, Shuo Zhou^3,4, and Tongyang Li³

¹John A. Paulson School of Engineering and Applied Sciences, Harvard University
²Institute for Interdisciplinary Information Sciences, Tsinghua University
³Center on Frontiers of Computing Studies, School of Computer Science, Peking University
⁴Yuanpei College, Peking University

Published:	2024-07-15, volume 8, page 1409
Eprint:	arXiv:2312.08867v3
Doi:	https://doi.org/10.22331/q-2024-07-15-1409
Citation:	Quantum 8, 1409 (2024).

Find this paper interesting or want to discuss? Scite or leave a comment on SciRate.

Abstract

Digital quantum simulation has broad applications in approximating unitary evolution of Hamiltonians. In practice, many simulation tasks for quantum systems focus on quantum states in the low-energy subspace instead of the entire Hilbert space. In this paper, we systematically investigate the complexity of digital quantum simulation based on product formulas in the low-energy subspace. We show that the simulation error depends on the effective low-energy norm of the Hamiltonian for a variety of digital quantum simulation algorithms and quantum systems, allowing improvements over the previous complexities for full unitary simulations even for imperfect state preparations due to thermalization. In particular, for simulating spin models in the low-energy subspace, we prove that randomized product formulas such as qDRIFT and random permutation require smaller Trotter numbers. Such improvement also persists in symmetry-protected digital quantum simulations. We prove a similar improvement in simulating the dynamics of power-law quantum interactions. We also provide a query lower bound for general digital quantum simulations in the low-energy subspace.

Featured image: Full Hilbert space vs. low-energy subspace: simulation error induced by
the qDRIFT and random permutation algorithms for localized Heisenberg spin-$1/2$
models.

► BibTeX data

@article{Gong2024complexityofdigital,
  doi = {10.22331/q-2024-07-15-1409},
  url = {https://doi.org/10.22331/q-2024-07-15-1409},
  title = {Complexity of {D}igital {Q}uantum {S}imulation in the {L}ow-{E}nergy {S}ubspace: {A}pplications and a {L}ower {B}ound},
  author = {Gong, Weiyuan and Zhou, Shuo and Li, Tongyang},
  journal = {{Quantum}},
  issn = {2521-327X},
  publisher = {{Verein zur F{\"{o}}rderung des Open Access Publizierens in den Quantenwissenschaften}},
  volume = {8},
  pages = {1409},
  month = jul,
  year = {2024}
}

► References

[1] Iulia M. Georgescu, Sahel Ashhab, and Franco Nori. ``Quantum simulation''. Reviews of Modern Physics 86, 153 (2014). arXiv:1308.6253.
https://doi.org/10.1103/RevModPhys.86.153
arXiv:1308.6253

[2] Richard P. Feynman. ``Simulating physics with computers''. International Journal of Theoretical Physics 21, 467–488 (1982).
https://doi.org/10.1007/BF02650179

[3] Youngseok Kim, Andrew Eddins, Sajant Anand, Ken Xuan Wei, Ewout Van Den Berg, Sami Rosenblatt, Hasan Nayfeh, Yantao Wu, Michael Zaletel, Kristan Temme, and Abhinav Kandala. ``Evidence for the utility of quantum computing before fault tolerance''. Nature 618, 500–505 (2023).
https://doi.org/10.1038/s41586-023-06096-3

[4] Masuo Suzuki. ``Decomposition formulas of exponential operators and Lie exponentials with some applications to quantum mechanics and statistical physics''. Journal of Mathematical Physics 26, 601–612 (1985).
https://doi.org/10.1063/1.526596

[5] Masuo Suzuki. ``General theory of fractal path integrals with applications to many-body theories and statistical physics''. Journal of Mathematical Physics 32, 400–407 (1991).
https://doi.org/10.1063/1.529425

[6] Masuo Suzuki. ``Fractal decomposition of exponential operators with applications to many-body theories and Monte Carlo simulations''. Physics Letters A 146, 319–323 (1990).
https://doi.org/10.1016/0375-9601(90)90962-N

[7] Jacky Huyghebaert and Hans De Raedt. ``Product formula methods for time-dependent Schrödinger problems''. Journal of Physics A: Mathematical and General 23, 5777 (1990).
https://doi.org/10.1088/0305-4470/23/24/019

[8] Andrew M. Childs and Yuan Su. ``Nearly optimal lattice simulation by product formulas''. Physical Review Letters 123, 050503 (2019). arXiv:1901.00564.
https://doi.org/10.1103/PhysRevLett.123.050503
arXiv:1901.00564

[9] Andrew M. Childs. ``Quantum information processing in continuous time''. PhD thesis. Massachusetts Institute of Technology. Cambridge, MA (2004).

[10] Dominic W. Berry, Graeme Ahokas, Richard Cleve, and Barry C. Sanders. ``Efficient quantum algorithms for simulating sparse Hamiltonians''. Communications in Mathematical Physics 270, 359–371 (2007). arXiv:quant-ph/0508139.
https://doi.org/10.1007/s00220-006-0150-x
arXiv:quant-ph/0508139

[11] Andrew M. Childs and Nathan Wiebe. ``Hamiltonian simulation using linear combinations of unitary operations''. Quantum Information & Computation 12, 901–924 (2012). arXiv:1202.5822.
https://doi.org/10.26421/qic12.11-12
arXiv:1202.5822

[12] Sergiy Zhuk, Niall Robertson, and Sergey Bravyi. ``Trotter error bounds and dynamic multi-product formulas for Hamiltonian simulation'' (2023) arXiv:2306.12569.
arXiv:2306.12569

[13] Guang Hao Low and Isaac L. Chuang. ``Hamiltonian simulation by qubitization''. Quantum 3, 163 (2019). arXiv:1610.06546.
https://doi.org/10.22331/q-2019-07-12-163
arXiv:1610.06546

[14] Dominic W. Berry, Andrew M. Childs, Richard Cleve, Robin Kothari, and Rolando D. Somma. ``Simulating Hamiltonian dynamics with a truncated Taylor series''. Physical Review Letters 114, 090502 (2015). arXiv:1412.4687.
https://doi.org/10.1103/PhysRevLett.114.090502
arXiv:1412.4687

[15] Guang Hao Low and Isaac L. Chuang. ``Optimal Hamiltonian simulation by quantum signal processing''. Physical Review Letters 118, 010501 (2017). arXiv:1606.02685.
https://doi.org/10.1103/PhysRevLett.118.010501
arXiv:1606.02685

[16] John M. Martyn, Zane M. Rossi, Andrew K. Tan, and Isaac L. Chuang. ``Grand unification of quantum algorithms''. PRX Quantum 2, 040203 (2021). arXiv:2105.02859.
https://doi.org/10.1103/PRXQuantum.2.040203
arXiv:2105.02859

[17] John Preskill. ``Quantum computing in the NISQ era and beyond''. Quantum 2, 79 (2018). arXiv:1801.00862.
https://doi.org/10.22331/q-2018-08-06-79
arXiv:1801.00862

[18] Andrew M. Childs, Dmitri Maslov, Yunseong Nam, Neil J. Ross, and Yuan Su. ``Toward the first quantum simulation with quantum speedup''. Proceedings of the National Academy of Sciences 115, 9456–9461 (2018). arXiv:1711.10980.
https://doi.org/10.1073/pnas.1801723115
arXiv:1711.10980

[19] Andrew M. Childs, Yuan Su, Minh C. Tran, Nathan Wiebe, and Shuchen Zhu. ``Theory of Trotter error with commutator scaling''. Physical Review X 11, 011020 (2021). arXiv:1912.08854.
https://doi.org/10.1103/PhysRevX.11.011020
arXiv:1912.08854

[20] Earl Campbell. ``Random compiler for fast Hamiltonian simulation''. Physical Review Letters 123, 070503 (2019). arXiv:1811.08017.
https://doi.org/10.1103/PhysRevLett.123.070503
arXiv:1811.08017

[21] Chi-Fang Chen, Hsin-Yuan Huang, Richard Kueng, and Joel A. Tropp. ``Concentration for random product formulas''. PRX Quantum 2, 040305 (2021). arXiv:2008.11751.
https://doi.org/10.1103/PRXQuantum.2.040305
arXiv:2008.11751

[22] Chi-Fang Chen and Fernando GSL Brandão. ``Average-case speedup for product formulas''. Communications in Mathematical Physics 405, 32 (2024). arXiv:2111.05324.
https://doi.org/10.1007/s00220-023-04912-5
arXiv:2111.05324

[23] Andrew M. Childs, Aaron Ostrander, and Yuan Su. ``Faster quantum simulation by randomization''. Quantum 3, 182 (2019). arXiv:1805.08385.
https://doi.org/10.22331/q-2019-12-16-182
arXiv:1805.08385

[24] Minh C. Tran, Yuan Su, Daniel Carney, and Jacob M. Taylor. ``Faster digital quantum simulation by symmetry protection''. PRX Quantum 2, 010323 (2021). arXiv:2006.16248.
https://doi.org/10.1103/PRXQuantum.2.010323
arXiv:2006.16248

[25] Guang Hao Low, Vadym Kliuchnikov, and Nathan Wiebe. ``Well-conditioned multiproduct Hamiltonian simulation'' (2019) arXiv:1907.11679.
arXiv:1907.11679

[26] W. Gong, Yaroslav Kharkov, Minh C. Tran, Przemyslaw Bienias, and Alexey V. Gorshkov. ``Improved digital quantum simulation by non-unitary channels'' (2023) arXiv:2307.13028.
arXiv:2307.13028

[27] Burak Şahinoğlu and Rolando D. Somma. ``Hamiltonian simulation in the low-energy subspace''. npj Quantum Information 7, 119 (2021). arXiv:2006.02660.
https://doi.org/10.1038/s41534-021-00451-w
arXiv:2006.02660

[28] Daniel Burgarth, Niklas Galke, Alexander Hahn, and Lauritz van Luijk. ``State-dependent Trotter limits and their approximations''. Physical Review A 107, L040201 (2023). arXiv:2209.14787.
https://doi.org/10.1103/PhysRevA.107.L040201
arXiv:2209.14787

[29] Daniel Burgarth, Paolo Facchi, Alexander Hahn, Mattias Johnsson, and Kazuya Yuasa. ``Strong error bounds for Trotter & Strang-splittings and their implications for quantum chemistry'' (2023). arXiv:2312.08044.
arXiv:2312.08044

[30] Changhao Yi and Elizabeth Crosson. ``Spectral analysis of product formulas for quantum simulation''. npj Quantum Information 8, 37 (2022). arXiv:2102.12655.
https://doi.org/10.1038/s41534-022-00548-w
arXiv:2102.12655

[31] Kasra Hejazi, Modjtaba Shokrian Zini, and Juan Miguel Arrazola. ``Better bounds for low-energy product formulas'' (2024). arXiv:2402.10362.
arXiv:2402.10362

[32] Mari Carmen Bañuls, David A. Huse, and J. Ignacio Cirac. ``Entanglement and its relation to energy variance for local one-dimensional Hamiltonians''. Physical Review B 101, 144305 (2020). arXiv:1912.07639.
https://doi.org/10.1103/PhysRevB.101.144305
arXiv:1912.07639

[33] Yimin Ge, Jordi Tura, and J. Ignacio Cirac. ``Faster ground state preparation and high-precision ground energy estimation with fewer qubits''. Journal of Mathematical Physics 60, 022202 (2019). arXiv:1712.03193.
https://doi.org/10.1063/1.5027484
arXiv:1712.03193

[34] Sirui Lu, Mari Carmen Banuls, and J. Ignacio Cirac. ``Algorithms for quantum simulation at finite energies''. PRX Quantum 2, 020321 (2021). arXiv:2006.03032.
https://doi.org/10.1103/PRXQuantum.2.020321
arXiv:2006.03032

[35] Chien Hung Cho, Dominic W. Berry, and Min-Hsiu Hsieh. ``Doubling the order of approximation via the randomized product formula''. Physical Review A 109, 062431 (2024). arXiv:2210.11281.
https://doi.org/10.1103/PhysRevA.109.062431
arXiv:2210.11281

[36] Dominic W. Berry, Andrew M. Childs, Richard Cleve, Robin Kothari, and Rolando D. Somma. ``Exponential improvement in precision for simulating sparse Hamiltonians''. In Proceedings of the Forty-sixth Annual ACM Symposium on Theory of Computing. Pages 283–292. (2014). arXiv:1312.1414.
https://doi.org/10.1145/2591796.2591854
arXiv:1312.1414

[37] Robert Beals, Harry Buhrman, Richard Cleve, Michele Mosca, and Ronald de Wolf. ``Quantum lower bounds by polynomials''. Journal of the ACM (JACM) 48, 778–797 (2001). arXiv:quant-ph/9802049.
https://doi.org/10.1145/502090.502097
arXiv:quant-ph/9802049

[38] Edward Farhi, Jeffrey Goldstone, Sam Gutmann, and Michael Sipser. ``Limit on the speed of quantum computation in determining parity''. Physical Review Letters 81, 5442 (1998). arXiv:quant-ph/9802045.
https://doi.org/10.1103/PhysRevLett.81.5442
arXiv:quant-ph/9802045

[39] Qi Zhao, You Zhou, Alexander F. Shaw, Tongyang Li, and Andrew M. Childs. ``Hamiltonian simulation with random inputs''. Physical Review Letters 129, 270502 (2022). arXiv:2111.04773.
https://doi.org/10.1103/PhysRevLett.129.270502
arXiv:2111.04773

[40] Itai Arad, Tomotaka Kuwahara, and Zeph Landau. ``Connecting global and local energy distributions in quantum spin models on a lattice''. Journal of Statistical Mechanics: Theory and Experiment 2016, 033301 (2016). arXiv:1406.3898.
https://doi.org/10.1088/1742-5468/2016/03/033301
arXiv:1406.3898

[41] Haruo Yoshida. ``Construction of higher order symplectic integrators''. Physics Letters A 150, 262–268 (1990).
https://doi.org/10.1016/0375-9601(90)90092-3

[42] De Huang, Jonathan Niles-Weed, Joel A. Tropp, and Rachel Ward. ``Matrix concentration for products''. Foundations of Computational Mathematics 22, 1767–1799 (2022). arXiv:2003.05437.
https://doi.org/10.1007/s10208-021-09533-9
arXiv:2003.05437

[43] Roberto Imbuzeiro Oliveira. ``The spectrum of random k-lifts of large graphs (with possibly large k)''. Journal of Combinatorics 1, 285–306 (2009). arXiv:0911.4741.
https://doi.org/10.4310/JOC.2010.v1.n3.a2
arXiv:0911.4741

[44] Joel A. Tropp. ``Freedman’s inequality for matrix martingales''. Electronic Communications in Probability 16, 262–270 (2011). arXiv:1101.3039.
https://doi.org/10.1214/ECP.v16-1624
arXiv:1101.3039

[45] Iosif Pinelis. ``Optimum bounds for the distributions of martingales in Banach spaces''. The Annals of Probability 22, 1679–1706 (1994).
https://doi.org/10.1214/aop/1176988477

[46] Tarun Kathuria, Satyaki Mukherjee, and Nikhil Srivastava. ``On concentration inequalities for random matrix products'' (2020) arXiv:2003.06319.
arXiv:2003.06319

[47] Joel A. Tropp. ``An introduction to matrix concentration inequalities''. Foundations and Trends® in Machine Learning 8, 1–230 (2015). arXiv:1501.01571.
https://doi.org/10.1561/2200000048
arXiv:1501.01571

[48] Willard Miller. ``Symmetry groups and their applications''. Academic Press. (1973).

Cited by

[1] Kaoru Mizuta and Tomotaka Kuwahara, "Trotterization is Substantially Efficient for Low-Energy States", Physical Review Letters 135 13, 130602 (2025).

[2] Daniel Burgarth, Paolo Facchi, Alexander Hahn, Mattias Johnsson, and Kazuya Yuasa, "Strong error bounds for Trotter and strang-splittings and their implications for quantum chemistry", Physical Review Research 6 4, 043155 (2024).

[3] Langyu Li, "Principal Trotter observation error with truncated commutators", Physical Review A 110 6, 062614 (2024).

[4] Alexander Zlokapa and Rolando D. Somma, "Hamiltonian simulation for low-energy states with optimal time dependence", Quantum 8, 1449 (2024).

[5] Yukun Zhang, Xiaoming Zhang, Jinzhao Sun, Heng Lin, Yifei Huang, Dingshun Lv, and Xiao Yuan, "Quantum Algorithms for Quantum Molecular Systems: A Survey", WIREs Computational Molecular Science 15 3, e70020 (2025).

[6] Hongzheng Zhao, Ao Chen, Shu-Wei Liu, Marin Bukov, Markus Heyl, and Roderich Moessner, "Learning effective Hamiltonians for adaptive time-evolution quantum algorithms", arXiv:2406.06198, (2024).

[7] Di Fang, Diyi Liu, and Rahul Sarkar, "Time-Dependent Hamiltonian Simulation via Magnus Expansion: Algorithm and Superconvergence", Communications in Mathematical Physics 406 6, 128 (2025).

[8] Yonah Borns-Weil, Di Fang, and Jiaqi Zhang, "Discrete Superconvergence Analysis for Quantum Magnus Algorithms of Unbounded Hamiltonian Simulation", Communications in Mathematical Physics 407 2, 29 (2026).

[9] Di Fang, Xiaoxu Wu, and Avy Soffer, "On the Trotter Error in Many-body Quantum Dynamics with Coulomb Potentials", Communications in Mathematical Physics 407 4, 83 (2026).

[10] Di Fang, David Lloyd George, and Yu Tong, "Qubit-Efficient Quantum Algorithm for Linear Differential Equations", arXiv:2507.16995, (2025).

[11] Jue Xu, Chu Zhao, Junyu Fan, and Qi Zhao, "Exponentially Decaying Quantum Simulation Error with Noisy Devices", arXiv:2504.10247, (2025).

[12] Shuo Zhou, Zhaokai Pan, Weiyuan Gong, and Tongyang Li, "Time-Dependent Low-Energy Simulation Accelerates Adiabatic State Preparation", arXiv:2601.01550, (2026).

[13] Seung Park, Dongkeun Lee, Jeongho Bang, Hoon Ryu, and Kyunghyun Baek, "Subspace Variational Quantum Simulation: Fidelity Lower Bounds as Measures of Training Success", arXiv:2509.06360, (2025).

[14] Di Fang and Xiaoxu Wu, "Trotterization with Many-body Coulomb Interactions: Convergence for General Initial Conditions and State-Dependent Improvements", arXiv:2604.07704, (2026).

[15] Di Fang and Jiaqi Zhang, "Splitting Analysis for Yukawa Potential", arXiv:2607.12153, (2026).

The above citations are from Crossref's cited-by service (last updated successfully 2026-08-13 19:20:24) and SAO/NASA ADS (last updated successfully 2026-08-13 19:20:25). The list may be incomplete as not all publishers provide suitable and complete citation data.

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.