Hamiltonian simulation for low-energy states with optimal time dependence

Alexander Zlokapa; Rolando D. Somma

doi:10.22331/q-2024-08-27-1449

Hamiltonian simulation for low-energy states with optimal time dependence

Alexander Zlokapa^1,2 and Rolando D. Somma²

¹Center for Theoretical Physics, MIT, 02139, USA
²Google Quantum AI, Venice, CA 90291, USA

Published:	2024-08-27, volume 8, page 1449
Eprint:	arXiv:2404.03644v2
Doi:	https://doi.org/10.22331/q-2024-08-27-1449
Citation:	Quantum 8, 1449 (2024).

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

Abstract

We consider the task of simulating time evolution under a Hamiltonian $H$ within its low-energy subspace. Assuming access to a block-encoding of $H':=(H-E)/\lambda$, for some $\lambda \gt 0$ and $E \in \mathbb R$, the goal is to implement an $\epsilon$-approximation to the evolution operator $e^{-itH}$ when the initial state is confined to the subspace corresponding to eigenvalues $[-1, -1+\Delta/\lambda]$ of $H'$, for $\Delta \leq \lambda$. We present a quantum algorithm that requires $\mathcal{O}(t\sqrt{\lambda\Gamma} + \sqrt{\lambda/\Gamma}\log(1/\epsilon))$ queries to the block-encoding for any choice of $\Gamma$ such that $\Delta \leq \Gamma \leq \lambda$. When the parameters satisfy $\log(1/\epsilon) = o(t\lambda)$ and $\Delta/\lambda = o(1)$, this result improves over generic methods with query complexity $\Omega(t\lambda)$. Our quantum algorithm leverages spectral gap amplification and the quantum singular value transform.

For a given $H$, the block-encoding of its $H'$ must be prepared efficiently to achieve an asymptotic speedup in simulating the low-energy subspace; we refer to these Hamiltonians as $gap-amplifiable$. We show necessary and sufficient conditions for gap amplifiability in terms of an operationally useful decomposition of $H$ into a sum of squares. Gap-amplifiable Hamiltonians include physically relevant examples such as frustration-free systems, and it encompasses all previously considered settings of low energy simulation algorithms. Any Hamiltonian can be expressed as a gap-amplifiable Hamiltonian after simple transformations, and our algorithm retains the asymptotic improvement over generic methods as long as the conditions on the parameters are met.

We also provide lower bounds for simulating dynamics of low-energy states. In the worst case, we show that the low-energy condition cannot be used to improve the runtime of Hamiltonian simulation methods. For gap-amplifiable Hamiltonians, we prove that our algorithm is tight in the query model with respect to $t$, $\Delta$, and $\lambda$. In the practically relevant regime where $\log (1/\epsilon) = o(t\Delta)$ and $\Delta/\lambda = o(1)$, we also prove a matching lower bound in gate complexity (up to logarithmic factors). To establish the query lower bounds, we consider oracular problems including search and $\mathrm{PARITY}\circ\mathrm{OR}$, and also bounds on the degrees of trigonometric polynomials. To establish the lower bound on gate complexity, we use a circuit-to-Hamiltonian reduction, where a “clock Hamiltonian'' acting on a low-energy state can simulate any quantum circuit.

Popular summary

The simulation of the dynamics of quantum systems is regarded as one of the most important applications of quantum computers. However, improvements in quantum simulation algorithms will be required to make quantum simulation more feasible. In this study, we present a quantum algorithm for simulating the time dynamics of quantum states of low-energy. This is relevant for many applications, like studying properties of quantum systems at low temperatures. For specific classes of physical systems, which we refer to as gap-amplifiable, the algorithm offers significant advantages over conventional quantum simulation algorithms. Additionally, we demonstrate that our quantum algorithm is optimal and that it is not always possible to gain an advantage from simulating states of low-energy.

► BibTeX data

@article{Zlokapa2024hamiltonian,
  doi = {10.22331/q-2024-08-27-1449},
  url = {https://doi.org/10.22331/q-2024-08-27-1449},
  title = {Hamiltonian simulation for low-energy states with optimal time dependence},
  author = {Zlokapa, Alexander and Somma, Rolando D.},
  journal = {{Quantum}},
  issn = {2521-327X},
  publisher = {{Verein zur F{\"{o}}rderung des Open Access Publizierens in den Quantenwissenschaften}},
  volume = {8},
  pages = {1449},
  month = aug,
  year = {2024}
}

► References

[1] Tameem Albash and Daniel A Lidar. Adiabatic quantum computation. Reviews of Modern Physics, 90 (1): 015002, 2018. 10.1103/RevModPhys.90.015002.
https://doi.org/10.1103/RevModPhys.90.015002

[2] Dong An, Jin-Peng Liu, and Lin Lin. Linear combination of hamiltonian simulation for nonunitary dynamics with optimal state preparation cost. Phys. Rev. Lett., 131: 150603, Oct 2023. 10.1103/PhysRevLett.131.150603.
https://doi.org/10.1103/PhysRevLett.131.150603

[3] Alán Aspuru-Guzik, Anthony D Dutoi, Peter J Love, and Martin Head-Gordon. Simulated quantum computation of molecular energies. Science, 309 (5741): 1704–1707, 2005. 10.1126/science.1113479.
https://doi.org/10.1126/science.1113479

[4] Yosi Atia and Dorit Aharonov. Fast-forwarding of hamiltonians and exponentially precise measurements. Nature communications, 8 (1): 1572, 2017. 10.1038/s41467-017-01637-7.
https://doi.org/10.1038/s41467-017-01637-7

[5] Ryan Babbush, Dominic W Berry, Ian D Kivlichan, Annie Y Wei, Peter J Love, and Alán Aspuru-Guzik. Exponentially more precise quantum simulation of fermions in second quantization. New Journal of Physics, 18 (3): 033032, mar 2016. 10.1088/1367-2630/18/3/033032.
https://doi.org/10.1088/1367-2630/18/3/033032

[6] Ryan Babbush et al. Exponentially more precise quantum simulation of fermions in the configuration interaction representation. Quantum Science and Technology, 3 (1): 015006, (2017). 10.1088/2058-9565/aa9463.
https://doi.org/10.1088/2058-9565/aa9463

[7] Dominic W Berry and Andrew M. Childs. Black-box hamiltonian simulation and unitary implementation. Quantum Information & Computation, 12 (1-2): 29–62, (2012). 10.26421/QIC12.1-2-4.
https://doi.org/10.26421/QIC12.1-2-4

[8] Dominic W Berry, Graeme Ahokas, Richard Cleve, and Barry C. Sanders. Efficient quantum algorithms for simulating sparse hamiltonians. Communications in Mathematical Physics, 270 (2): 359–371, (2007). 10.1007/s00220-006-0150-x.
https://doi.org/10.1007/s00220-006-0150-x

[9] 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 (9): 090502, (2015). 10.1103/PhysRevLett.114.090502.
https://doi.org/10.1103/PhysRevLett.114.090502

[10] 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. 10.1145/2591796.2591854.
https://doi.org/10.1145/2591796.2591854

[11] Sergio Boixo, Emanuel Knill, and Rolando D Somma. Eigenpath traversal by phase randomization. Quantum Inf. Comput., 9 (9&10): 833–855, 2009. 10.26421/QIC9.9-10-7.
https://doi.org/10.26421/QIC9.9-10-7

[12] Peter Borwein and Tamás Erdélyi. Polynomials and polynomial inequalities, volume 161. Springer Science & Business Media, 2012. 10.1007/978-1-4612-0793-1.
https://doi.org/10.1007/978-1-4612-0793-1

[13] Michel Boyer, Gilles Brassard, Peter Høyer, and Alain Tapp. Tight bounds on quantum searching. Fortschritte der Physik: Progress of Physics, 46 (4-5): 493–505, 1998. 10.1002/3527603093.ch10.
https://doi.org/10.1002/3527603093.ch10

[14] Sergey Bravyi and Barbara Terhal. Complexity of stoquastic frustration-free hamiltonians. Siam journal on computing, 39 (4): 1462–1485, (2010). 10.1137/08072689X.
https://doi.org/10.1137/08072689X

[15] Earl Campbell. A random compiler for fast hamiltonian simulation. Physical review letters, 123: 070503, (2019). 10.1103/PhysRevLett.123.070503.
https://doi.org/10.1103/PhysRevLett.123.070503

[16] Jianxin Chen, Zhengfeng Ji, David Kribs, Zhaohui Wei, and Bei Zeng. Ground-state spaces of frustration-free hamiltonians. Journal of mathematical physics, 53 (10), 2012. 10.1063/1.4748527.
https://doi.org/10.1063/1.4748527

[17] Andrew M Childs and Jeffrey Goldstone. Spatial search by quantum walk. Physical Review A, 70 (2): 022314, 2004. 10.1103/PhysRevA.70.022314.
https://doi.org/10.1103/PhysRevA.70.022314

[18] Andrew M Childs, Robin Kothari, and Rolando D Somma. Quantum algorithm for systems of linear equations with exponentially improved dependence on precision. SIAM Journal on Computing, 46 (6): 1920–1950, (2017). 10.1137/16M1087072.
https://doi.org/10.1137/16M1087072

[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 (1): 011020, (2021). 10.1103/PhysRevX.11.011020.
https://doi.org/10.1103/PhysRevX.11.011020

[20] Anirban Narayan Chowdhury and Rolando D Somma. Quantum algorithms for gibbs sampling and hitting-time estimation. Quant. Inf. Comp., 17: 0041, 2017. 10.1145/3313276.3316366.
https://doi.org/10.1145/3313276.3316366

[21] Niel de Beaudrap, Matthias Ohliger, Tobias J Osborne, and Jens Eisert. Solving frustration-free spin systems. Physical review letters, 105: 060504, (2010). 10.1103/PhysRevLett.105.060504.
https://doi.org/10.1103/PhysRevLett.105.060504

[22] Edward Farhi, Jeffrey Goldstone, Sam Gutmann, and Michael Sipser. Quantum computation by adiabatic evolution. Preprint at https://arxiv.org/abs/quant-ph/0001106, 2000. 10.48550/arXiv.quant-ph/0001106.
https://doi.org/10.48550/arXiv.quant-ph/0001106
arXiv:quant-ph/0001106

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

[24] András Gilyén. personal communication, 2023.

[25] András Gilyén, Yuan Su, Guang Hao Low, and Nathan Wiebe. Quantum singular value transformation and beyond: exponential improvements for quantum matrix arithmetics. In Proceedings of the 51st Annual ACM SIGACT Symposium on Theory of Computing, pages 193–204, 2019. 10.1145/3313276.3316366.
https://doi.org/10.1145/3313276.3316366

[26] Weiyuan Gong, Shuo Zhou, and Tongyang Li. Complexity of Digital Quantum Simulation in the Low-Energy Subspace: Applications and a Lower Bound. Quantum, 8: 1409, July 2024. ISSN 2521-327X. 10.22331/q-2024-07-15-1409.
https://doi.org/10.22331/q-2024-07-15-1409

[27] Shouzhen Gu, Rolando D Somma, and Burak Şahinoğlu. Fast-forwarding quantum evolution. Quantum, 5: 577, November 2021. 10.22331/q-2021-11-15-577.
https://doi.org/10.22331/q-2021-11-15-577

[28] Jeongwan Haah, Matthew Hastings, Robin Kothari, and Guang Hao Low. Quantum algorithm for simulating real time evolution of lattice hamiltonians. In 2018 IEEE 59th Annual Symposium on Foundations of Computer Science (FOCS), pages 350–360. IEEE, (2018). 10.1137/18M1231511.
https://doi.org/10.1137/18M1231511

[29] Zoe Holmes, Gopikrishnan Muraleedharan, Rolando D Somma, Yigit Subasi, and Burak Şahinoğlu. Quantum algorithms from fluctuation theorems: Thermal-state preparation. Quantum, 6: 825, 2022. 10.22331/q-2022-10-06-825.
https://doi.org/10.22331/q-2022-10-06-825

[30] Peter Hoyer, Troy Lee, and Robert Spalek. Negative weights make adversaries stronger. In Proceedings of the thirty-ninth annual ACM symposium on Theory of computing, pages 526–535, 2007. 10.1145/1250790.1250867.
https://doi.org/10.1145/1250790.1250867

[31] Stephen P. Jordan. Fast quantum computation at arbitrarily low energy. Phys. Rev. A, 95: 032305, Mar 2017. 10.1103/PhysRevA.95.032305.
https://doi.org/10.1103/PhysRevA.95.032305

[32] Stephen P Jordan, Keith S.M. Lee, and John Preskill. Quantum algorithms for quantum field theories. Science, 336: 1130, (2012). 10.1126/science.1217069.
https://doi.org/10.1126/science.1217069

[33] Benjamin P Lanyon, James D Whitfield, Geoff G Gillett, Michael E Goggin, Marcelo P Almeida, Ivan Kassal, Jacob D Biamonte, Masoud Mohseni, Ben J Powell, Marco Barbieri, et al. Towards quantum chemistry on a quantum computer. Nature chemistry, 2 (2): 106–111, 2010. 10.1038/nchem.483.
https://doi.org/10.1038/nchem.483

[34] Seth Lloyd. Universal quantum simulators. Science, 273 (5278): 1073–1078, (1996). 10.1126/science.273.5278.1073.
https://doi.org/10.1126/science.273.5278.1073

[35] Guang Hao Low. Hamiltonian simulation with nearly optimal dependence on spectral norm. In Proceedings of the 51st Annual ACM SIGACT Symposium on Theory of Computing, STOC 2019, page 491–502, New York, NY, USA, 2019. 10.1145/3313276.3316386.
https://doi.org/10.1145/3313276.3316386

[36] Guang Hao Low and Isaac L. Chuang. Optimal hamiltonian simulation by quantum signal processing. Physical review letters, 118 (1): 010501, (2017). 10.1103/PhysRevLett.118.010501.
https://doi.org/10.1103/PhysRevLett.118.010501

[37] Guang Hao Low and Isaac L Chuang. Hamiltonian simulation by uniform spectral amplification. Preprint at https://arxiv.org/abs/1707.05391, 2017. 10.48550/arXiv.1707.05391.
https://doi.org/10.48550/arXiv.1707.05391
arXiv:1707.05391

[38] Guang Hao Low and Isaac L Chuang. Hamiltonian simulation by qubitization. Quantum, 3: 163, 2019. 10.22331/q-2019-07-12-163.
https://doi.org/10.22331/q-2019-07-12-163

[39] Nikhil S Mande and Ronald de Wolf. Tight bounds for quantum phase estimation and related problems. Preprint at https://arxiv.org/abs/2305.04908, 2023. 10.48550/arXiv.2305.04908.
https://doi.org/10.48550/arXiv.2305.04908
arXiv:2305.04908

[40] Michael A Nielsen and Isaac L Chuang. Quantum computation and quantum information. Cambridge university press, 2010. 10.1119/1.1463744.
https://doi.org/10.1119/1.1463744

[41] Davide Orsucci and Vedran Dunjko. On solving classes of positive-definite quantum linear systems with quadratically improved runtime in the condition number. Quantum, 5: 573, November 2021. ISSN 2521-327X. 10.22331/q-2021-11-08-573.
https://doi.org/10.22331/q-2021-11-08-573

[42] Ben W Reichardt. Span programs are equivalent to quantum query algorithms. SIAM Journal on Computing, 43 (3): 1206–1219, 2014. 10.1137/100792640.
https://doi.org/10.1137/100792640

[43] Subir Sachdev. Quantum phase transitions. Physics world, 12 (4): 33, 1999. 10.1002/9780470022184.hmm108.
https://doi.org/10.1002/9780470022184.hmm108

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

[45] Norbert Schuch, Ignacio Cirac, and Frank Verstraete. Computational difficulty of finding matrix product ground states. Physical review letters, 100 (25): 250501, 2008. 10.1103/PhysRevLett.100.250501.
https://doi.org/10.1103/PhysRevLett.100.250501

[46] Rolando Somma, Gerardo Ortiz, James E Gubernatis, Emanuel Knill, and Raymond Laflamme. Simulating physical phenomena by quantum networks. Physical Review A, 65 (4): 042323, (2002). 10.1103/PhysRevA.65.042323.
https://doi.org/10.1103/PhysRevA.65.042323

[47] Rolando D Somma. A trotter-suzuki approximation for lie groups with applications to hamiltonian simulation. Journal of Mathematical Physics, 57 (6): 062202, (2016). 10.1063/1.4952761.
https://doi.org/10.1063/1.4952761

[48] Rolando D. Somma. Quantum simulations of one dimensional quantum systems. Quantum Info. Comput., 16 (13–14): 1125–1168, oct 2016. ISSN 1533-7146.

[49] Rolando D Somma and Sergio Boixo. Spectral gap amplification. SIAM Journal on Computing, 42 (2): 593–610, 2013. 10.1137/120871997.
https://doi.org/10.1137/120871997

[50] Matthew Thibodeau and Bryan K. Clark. Nearly-frustration-free ground state preparation. Quantum, 7: 1084, August 2023. ISSN 2521-327X. 10.22331/q-2023-08-16-1084.
https://doi.org/10.22331/q-2023-08-16-1084

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

[52] Nathan Wiebe, Dominic Berry, Peter Høyer, and Barry C. Sanders. Higher order decompositions of ordered operator exponentials. Journal of Physics A: Mathematical and Theoretical, 43 (6): 065203, (2010). 10.1088/1751-8113/43/6/065203.
https://doi.org/10.1088/1751-8113/43/6/065203

Cited by

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

[2] Yuki Koizumi, Kaito Wada, Wataru Mizukami, and Nobuyuki Yoshioka, "Heisenberg-limited quantum algorithms for multiple observables estimation", Physical Review A 113 2, 022447 (2026).

[3] Rolando D. Somma, Robbie King, Robin Kothari, Thomas E. O’Brien, and Ryan Babbush, "Shadow hamiltonian simulation", Nature Communications 16 1, 2690 (2025).

[4] Guang Hao Low, Robbie King, Dominic W. Berry, Qiushi Han, A. Eugene DePrince, Alec F. White, Ryan Babbush, Rolando D. Somma, and Nicholas C. Rubin, "Fast Quantum Simulation of Electronic Structure by Spectral Amplification", Physical Review X 15 4, 041016 (2025).

[5] 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).

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

[7] Bence Bakó, Tenzan Araki, and Bálint Koczor, "Exponential Distillation of Dominant Eigenproperties", PRX Quantum 7 1, 010334 (2026).

[8] Robbie King, Guang Hao Low, Ryan Babbush, Rolando D. Somma, and Nicholas C. Rubin, "Quantum Simulation with Sum-of-Squares Spectral Amplification", Physical Review Letters 136 11, 110601 (2026).

[9] Christopher Kang and Yuan Su, "Quantum Matrix Arithmetics with Hamiltonian Evolution", ACM Transactions on Quantum Computing 7 4, 1 (2026).

[10] 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).

[11] James D. Watson and Jacob Watkins, "Exponentially Reduced Circuit Depths Using Trotter Error Mitigation", PRX Quantum 6 3, 030325 (2025).

[12] Angus Kan, Jessica Lemieux, Olga Okrut, and Burak Şahinoğlu, "Optimized quantum algorithms for simulating the Schwinger effect", Physical Review D 113 11, 114503 (2026).

[13] Yulong Dong and Lin Lin, "Multi-level quantum signal processing with applications to ground state preparation using fast-forwarded Hamiltonian evolution", arXiv:2406.02086, (2024).

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

[15] Christopher Kang and Yuan Su, "Quantum matrix arithmetics with Hamiltonian evolution", arXiv:2510.06316, (2025).

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

[17] 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).

[18] Torin Stetina and Nathan Wiebe, "First-Quantized Quantum Simulation of Non-Relativistic QED with Emergent Topologically Protected Coulomb Interactions", arXiv:2508.19343, (2025).

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

Could not fetch ADS cited-by data during last attempt 2026-08-19 11:40:41: Cannot retrieve data from ADS due to rate limitations.

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.