{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,3,17]],"date-time":"2026-03-17T23:48:31Z","timestamp":1773791311250,"version":"3.50.1"},"reference-count":52,"publisher":"Verein zur Forderung des Open Access Publizierens in den Quantenwissenschaften","license":[{"start":{"date-parts":[[2024,8,27]],"date-time":"2024-08-27T00:00:00Z","timestamp":1724716800000},"content-version":"unspecified","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0\/"}],"content-domain":{"domain":["quantum-journal.org"],"crossmark-restriction":false},"short-container-title":["Quantum"],"abstract":"<jats:p>We consider the task of simulating time evolution under a Hamiltonian <mml:math xmlns:mml=\"http:\/\/www.w3.org\/1998\/Math\/MathML\"><mml:mi>H<\/mml:mi><\/mml:math> within its low-energy subspace. Assuming access to a block-encoding of  <mml:math xmlns:mml=\"http:\/\/www.w3.org\/1998\/Math\/MathML\"><mml:msup><mml:mi>H<\/mml:mi><mml:mo>&amp;#x2032;<\/mml:mo><\/mml:msup><mml:mo>:=<\/mml:mo><mml:mo stretchy=\"false\">(<\/mml:mo><mml:mi>H<\/mml:mi><mml:mo>&amp;#x2212;<\/mml:mo><mml:mi>E<\/mml:mi><mml:mo stretchy=\"false\">)<\/mml:mo><mml:mrow class=\"MJX-TeXAtom-ORD\"><mml:mo>\/<\/mml:mo><\/mml:mrow><mml:mi>&amp;#x03BB;<\/mml:mi><\/mml:math>, for some <mml:math xmlns:mml=\"http:\/\/www.w3.org\/1998\/Math\/MathML\"><mml:mi>&amp;#x03BB;<\/mml:mi><mml:mo>&amp;#x003E;<\/mml:mo><mml:mn>0<\/mml:mn><\/mml:math> and <mml:math xmlns:mml=\"http:\/\/www.w3.org\/1998\/Math\/MathML\"><mml:mi>E<\/mml:mi><mml:mo>&amp;#x2208;<\/mml:mo><mml:mrow class=\"MJX-TeXAtom-ORD\"><mml:mi mathvariant=\"double-struck\">R<\/mml:mi><\/mml:mrow><\/mml:math>, the goal is to implement an <mml:math xmlns:mml=\"http:\/\/www.w3.org\/1998\/Math\/MathML\"><mml:mi>&amp;#x03F5;<\/mml:mi><\/mml:math>-approximation to the evolution operator <mml:math xmlns:mml=\"http:\/\/www.w3.org\/1998\/Math\/MathML\"><mml:msup><mml:mi>e<\/mml:mi><mml:mrow class=\"MJX-TeXAtom-ORD\"><mml:mo>&amp;#x2212;<\/mml:mo><mml:mi>i<\/mml:mi><mml:mi>t<\/mml:mi><mml:mi>H<\/mml:mi><\/mml:mrow><\/mml:msup><\/mml:math> when the initial state is confined to the subspace corresponding to eigenvalues <mml:math xmlns:mml=\"http:\/\/www.w3.org\/1998\/Math\/MathML\"><mml:mo stretchy=\"false\">[<\/mml:mo><mml:mo>&amp;#x2212;<\/mml:mo><mml:mn>1<\/mml:mn><mml:mo>,<\/mml:mo><mml:mo>&amp;#x2212;<\/mml:mo><mml:mn>1<\/mml:mn><mml:mo>+<\/mml:mo><mml:mi mathvariant=\"normal\">&amp;#x0394;<\/mml:mi><mml:mrow class=\"MJX-TeXAtom-ORD\"><mml:mo>\/<\/mml:mo><\/mml:mrow><mml:mi>&amp;#x03BB;<\/mml:mi><mml:mo stretchy=\"false\">]<\/mml:mo><\/mml:math> of <mml:math xmlns:mml=\"http:\/\/www.w3.org\/1998\/Math\/MathML\"><mml:msup><mml:mi>H<\/mml:mi><mml:mo>&amp;#x2032;<\/mml:mo><\/mml:msup><\/mml:math>, for <mml:math xmlns:mml=\"http:\/\/www.w3.org\/1998\/Math\/MathML\"><mml:mi mathvariant=\"normal\">&amp;#x0394;<\/mml:mi><mml:mo>&amp;#x2264;<\/mml:mo><mml:mi>&amp;#x03BB;<\/mml:mi><\/mml:math>. We present a quantum algorithm that requires <mml:math xmlns:mml=\"http:\/\/www.w3.org\/1998\/Math\/MathML\"><mml:mrow class=\"MJX-TeXAtom-ORD\"><mml:mi class=\"MJX-tex-caligraphic\" mathvariant=\"script\">O<\/mml:mi><\/mml:mrow><mml:mo stretchy=\"false\">(<\/mml:mo><mml:mi>t<\/mml:mi><mml:msqrt><mml:mi>&amp;#x03BB;<\/mml:mi><mml:mi mathvariant=\"normal\">&amp;#x0393;<\/mml:mi><\/mml:msqrt><mml:mo>+<\/mml:mo><mml:msqrt><mml:mi>&amp;#x03BB;<\/mml:mi><mml:mrow class=\"MJX-TeXAtom-ORD\"><mml:mo>\/<\/mml:mo><\/mml:mrow><mml:mi mathvariant=\"normal\">&amp;#x0393;<\/mml:mi><\/mml:msqrt><mml:mi>log<\/mml:mi><mml:mo>&amp;#x2061;<\/mml:mo><mml:mo stretchy=\"false\">(<\/mml:mo><mml:mn>1<\/mml:mn><mml:mrow class=\"MJX-TeXAtom-ORD\"><mml:mo>\/<\/mml:mo><\/mml:mrow><mml:mi>&amp;#x03F5;<\/mml:mi><mml:mo stretchy=\"false\">)<\/mml:mo><mml:mo stretchy=\"false\">)<\/mml:mo><\/mml:math> queries to the block-encoding for any choice of <mml:math xmlns:mml=\"http:\/\/www.w3.org\/1998\/Math\/MathML\"><mml:mi mathvariant=\"normal\">&amp;#x0393;<\/mml:mi><\/mml:math> such that <mml:math xmlns:mml=\"http:\/\/www.w3.org\/1998\/Math\/MathML\"><mml:mi mathvariant=\"normal\">&amp;#x0394;<\/mml:mi><mml:mo>&amp;#x2264;<\/mml:mo><mml:mi mathvariant=\"normal\">&amp;#x0393;<\/mml:mi><mml:mo>&amp;#x2264;<\/mml:mo><mml:mi>&amp;#x03BB;<\/mml:mi><\/mml:math>. When the parameters satisfy <mml:math xmlns:mml=\"http:\/\/www.w3.org\/1998\/Math\/MathML\"><mml:mi>log<\/mml:mi><mml:mo>&amp;#x2061;<\/mml:mo><mml:mo stretchy=\"false\">(<\/mml:mo><mml:mn>1<\/mml:mn><mml:mrow class=\"MJX-TeXAtom-ORD\"><mml:mo>\/<\/mml:mo><\/mml:mrow><mml:mi>&amp;#x03F5;<\/mml:mi><mml:mo stretchy=\"false\">)<\/mml:mo><mml:mo>=<\/mml:mo><mml:mi>o<\/mml:mi><mml:mo stretchy=\"false\">(<\/mml:mo><mml:mi>t<\/mml:mi><mml:mi>&amp;#x03BB;<\/mml:mi><mml:mo stretchy=\"false\">)<\/mml:mo><\/mml:math> and <mml:math xmlns:mml=\"http:\/\/www.w3.org\/1998\/Math\/MathML\"><mml:mi mathvariant=\"normal\">&amp;#x0394;<\/mml:mi><mml:mrow class=\"MJX-TeXAtom-ORD\"><mml:mo>\/<\/mml:mo><\/mml:mrow><mml:mi>&amp;#x03BB;<\/mml:mi><mml:mo>=<\/mml:mo><mml:mi>o<\/mml:mi><mml:mo stretchy=\"false\">(<\/mml:mo><mml:mn>1<\/mml:mn><mml:mo stretchy=\"false\">)<\/mml:mo><\/mml:math>, this result improves over generic methods with query complexity <mml:math xmlns:mml=\"http:\/\/www.w3.org\/1998\/Math\/MathML\"><mml:mi mathvariant=\"normal\">&amp;#x03A9;<\/mml:mi><mml:mo stretchy=\"false\">(<\/mml:mo><mml:mi>t<\/mml:mi><mml:mi>&amp;#x03BB;<\/mml:mi><mml:mo stretchy=\"false\">)<\/mml:mo><\/mml:math>. Our quantum algorithm leverages spectral gap amplification and the quantum singular value transform.For a given <mml:math xmlns:mml=\"http:\/\/www.w3.org\/1998\/Math\/MathML\"><mml:mi>H<\/mml:mi><\/mml:math>,  the block-encoding of its <mml:math xmlns:mml=\"http:\/\/www.w3.org\/1998\/Math\/MathML\"><mml:msup><mml:mi>H<\/mml:mi><mml:mo>&amp;#x2032;<\/mml:mo><\/mml:msup><\/mml:math> must be prepared efficiently to achieve an asymptotic speedup in simulating the low-energy subspace; we refer to these Hamiltonians as <mml:math xmlns:mml=\"http:\/\/www.w3.org\/1998\/Math\/MathML\"><mml:mi>g<\/mml:mi><mml:mi>a<\/mml:mi><mml:mi>p<\/mml:mi><mml:mo>&amp;#x2212;<\/mml:mo><mml:mi>a<\/mml:mi><mml:mi>m<\/mml:mi><mml:mi>p<\/mml:mi><mml:mi>l<\/mml:mi><mml:mi>i<\/mml:mi><mml:mi>f<\/mml:mi><mml:mi>i<\/mml:mi><mml:mi>a<\/mml:mi><mml:mi>b<\/mml:mi><mml:mi>l<\/mml:mi><mml:mi>e<\/mml:mi><\/mml:math>. We show necessary and sufficient conditions for gap amplifiability in terms of an operationally useful decomposition of <mml:math xmlns:mml=\"http:\/\/www.w3.org\/1998\/Math\/MathML\"><mml:mi>H<\/mml:mi><\/mml:math> 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 <mml:math xmlns:mml=\"http:\/\/www.w3.org\/1998\/Math\/MathML\"><mml:mi>t<\/mml:mi><\/mml:math>, <mml:math xmlns:mml=\"http:\/\/www.w3.org\/1998\/Math\/MathML\"><mml:mi mathvariant=\"normal\">&amp;#x0394;<\/mml:mi><\/mml:math>, and <mml:math xmlns:mml=\"http:\/\/www.w3.org\/1998\/Math\/MathML\"><mml:mi>&amp;#x03BB;<\/mml:mi><\/mml:math>. In the practically relevant regime where <mml:math xmlns:mml=\"http:\/\/www.w3.org\/1998\/Math\/MathML\"><mml:mi>log<\/mml:mi><mml:mo>&amp;#x2061;<\/mml:mo><mml:mo stretchy=\"false\">(<\/mml:mo><mml:mn>1<\/mml:mn><mml:mrow class=\"MJX-TeXAtom-ORD\"><mml:mo>\/<\/mml:mo><\/mml:mrow><mml:mi>&amp;#x03F5;<\/mml:mi><mml:mo stretchy=\"false\">)<\/mml:mo><mml:mo>=<\/mml:mo><mml:mi>o<\/mml:mi><mml:mo stretchy=\"false\">(<\/mml:mo><mml:mi>t<\/mml:mi><mml:mi mathvariant=\"normal\">&amp;#x0394;<\/mml:mi><mml:mo stretchy=\"false\">)<\/mml:mo><\/mml:math> and <mml:math xmlns:mml=\"http:\/\/www.w3.org\/1998\/Math\/MathML\"><mml:mi mathvariant=\"normal\">&amp;#x0394;<\/mml:mi><mml:mrow class=\"MJX-TeXAtom-ORD\"><mml:mo>\/<\/mml:mo><\/mml:mrow><mml:mi>&amp;#x03BB;<\/mml:mi><mml:mo>=<\/mml:mo><mml:mi>o<\/mml:mi><mml:mo stretchy=\"false\">(<\/mml:mo><mml:mn>1<\/mml:mn><mml:mo stretchy=\"false\">)<\/mml:mo><\/mml:math>, 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 <mml:math xmlns:mml=\"http:\/\/www.w3.org\/1998\/Math\/MathML\"><mml:mrow class=\"MJX-TeXAtom-ORD\"><mml:mi mathvariant=\"normal\">P<\/mml:mi><mml:mi mathvariant=\"normal\">A<\/mml:mi><mml:mi mathvariant=\"normal\">R<\/mml:mi><mml:mi mathvariant=\"normal\">I<\/mml:mi><mml:mi mathvariant=\"normal\">T<\/mml:mi><mml:mi mathvariant=\"normal\">Y<\/mml:mi><\/mml:mrow><mml:mo>&amp;#x2218;<\/mml:mo><mml:mrow class=\"MJX-TeXAtom-ORD\"><mml:mi mathvariant=\"normal\">O<\/mml:mi><mml:mi mathvariant=\"normal\">R<\/mml:mi><\/mml:mrow><\/mml:math>, 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 \u201cclock Hamiltonian'' acting on a low-energy state can simulate any quantum circuit.<\/jats:p>","DOI":"10.22331\/q-2024-08-27-1449","type":"journal-article","created":{"date-parts":[[2024,8,27]],"date-time":"2024-08-27T16:11:34Z","timestamp":1724775094000},"page":"1449","update-policy":"https:\/\/doi.org\/10.22331\/q-crossmark-policy-page","source":"Crossref","is-referenced-by-count":10,"title":["Hamiltonian simulation for low-energy states with optimal time dependence"],"prefix":"10.22331","volume":"8","author":[{"given":"Alexander","family":"Zlokapa","sequence":"first","affiliation":[{"name":"Center for Theoretical Physics, MIT, 02139, USA"},{"name":"Google Quantum AI, Venice, CA 90291, USA"}]},{"given":"Rolando D.","family":"Somma","sequence":"additional","affiliation":[{"name":"Google Quantum AI, Venice, CA 90291, USA"}]}],"member":"9598","published-online":{"date-parts":[[2024,8,27]]},"reference":[{"key":"0","doi-asserted-by":"publisher","unstructured":"Tameem Albash and Daniel A Lidar. Adiabatic quantum computation. Reviews of Modern Physics, 90 (1): 015002, 2018. 10.1103\/RevModPhys.90.015002.","DOI":"10.1103\/RevModPhys.90.015002"},{"key":"1","doi-asserted-by":"publisher","unstructured":"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.","DOI":"10.1103\/PhysRevLett.131.150603"},{"key":"2","doi-asserted-by":"publisher","unstructured":"Al\u00e1n Aspuru-Guzik, Anthony D Dutoi, Peter J Love, and Martin Head-Gordon. Simulated quantum computation of molecular energies. Science, 309 (5741): 1704\u20131707, 2005. 10.1126\/science.1113479.","DOI":"10.1126\/science.1113479"},{"key":"3","doi-asserted-by":"publisher","unstructured":"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.","DOI":"10.1038\/s41467-017-01637-7"},{"key":"4","doi-asserted-by":"publisher","unstructured":"Ryan Babbush, Dominic W Berry, Ian D Kivlichan, Annie Y Wei, Peter J Love, and Al\u00e1n 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.","DOI":"10.1088\/1367-2630\/18\/3\/033032"},{"key":"5","doi-asserted-by":"publisher","unstructured":"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.","DOI":"10.1088\/2058-9565\/aa9463"},{"key":"6","doi-asserted-by":"publisher","unstructured":"Dominic W Berry and Andrew M. Childs. Black-box hamiltonian simulation and unitary implementation. Quantum Information & Computation, 12 (1-2): 29\u201362, (2012). 10.26421\/QIC12.1-2-4.","DOI":"10.26421\/QIC12.1-2-4"},{"key":"7","doi-asserted-by":"publisher","unstructured":"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\u2013371, (2007). 10.1007\/s00220-006-0150-x.","DOI":"10.1007\/s00220-006-0150-x"},{"key":"8","doi-asserted-by":"publisher","unstructured":"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.","DOI":"10.1103\/PhysRevLett.114.090502"},{"key":"9","doi-asserted-by":"publisher","unstructured":"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\u2013292, 2014. 10.1145\/2591796.2591854.","DOI":"10.1145\/2591796.2591854"},{"key":"10","doi-asserted-by":"publisher","unstructured":"Sergio Boixo, Emanuel Knill, and Rolando D Somma. Eigenpath traversal by phase randomization. Quantum Inf. Comput., 9 (9&10): 833\u2013855, 2009. 10.26421\/QIC9.9-10-7.","DOI":"10.26421\/QIC9.9-10-7"},{"key":"11","doi-asserted-by":"publisher","unstructured":"Peter Borwein and Tam\u00e1s Erd\u00e9lyi. Polynomials and polynomial inequalities, volume 161. Springer Science & Business Media, 2012. 10.1007\/978-1-4612-0793-1.","DOI":"10.1007\/978-1-4612-0793-1"},{"key":"12","doi-asserted-by":"publisher","unstructured":"Michel Boyer, Gilles Brassard, Peter H\u00f8yer, and Alain Tapp. Tight bounds on quantum searching. Fortschritte der Physik: Progress of Physics, 46 (4-5): 493\u2013505, 1998. 10.1002\/3527603093.ch10.","DOI":"10.1002\/3527603093.ch10"},{"key":"13","doi-asserted-by":"publisher","unstructured":"Sergey Bravyi and Barbara Terhal. Complexity of stoquastic frustration-free hamiltonians. Siam journal on computing, 39 (4): 1462\u20131485, (2010). 10.1137\/08072689X.","DOI":"10.1137\/08072689X"},{"key":"14","doi-asserted-by":"publisher","unstructured":"Earl Campbell. A random compiler for fast hamiltonian simulation. Physical review letters, 123: 070503, (2019). 10.1103\/PhysRevLett.123.070503.","DOI":"10.1103\/PhysRevLett.123.070503"},{"key":"15","doi-asserted-by":"publisher","unstructured":"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.","DOI":"10.1063\/1.4748527"},{"key":"16","doi-asserted-by":"publisher","unstructured":"Andrew M Childs and Jeffrey Goldstone. Spatial search by quantum walk. Physical Review A, 70 (2): 022314, 2004. 10.1103\/PhysRevA.70.022314.","DOI":"10.1103\/PhysRevA.70.022314"},{"key":"17","doi-asserted-by":"publisher","unstructured":"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\u20131950, (2017). 10.1137\/16M1087072.","DOI":"10.1137\/16M1087072"},{"key":"18","doi-asserted-by":"publisher","unstructured":"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.","DOI":"10.1103\/PhysRevX.11.011020"},{"key":"19","doi-asserted-by":"publisher","unstructured":"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.","DOI":"10.1145\/3313276.3316366"},{"key":"20","doi-asserted-by":"publisher","unstructured":"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.","DOI":"10.1103\/PhysRevLett.105.060504"},{"key":"21","doi-asserted-by":"publisher","unstructured":"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.","DOI":"10.48550\/arXiv.quant-ph\/0001106"},{"key":"22","doi-asserted-by":"publisher","unstructured":"Richard P Feynman. Simulating physics with computers. International Journal of Theoretical Physics, 21 (6\u20137): 467\u2013488, 1982. 10.1007\/BF02650179.","DOI":"10.1007\/BF02650179"},{"key":"23","unstructured":"Andr\u00e1s Gily\u00e9n. personal communication, 2023."},{"key":"24","doi-asserted-by":"publisher","unstructured":"Andr\u00e1s Gily\u00e9n, 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\u2013204, 2019. 10.1145\/3313276.3316366.","DOI":"10.1145\/3313276.3316366"},{"key":"25","doi-asserted-by":"publisher","unstructured":"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.","DOI":"10.22331\/q-2024-07-15-1409"},{"key":"26","doi-asserted-by":"publisher","unstructured":"Shouzhen Gu, Rolando D Somma, and Burak \u015eahino\u011flu. Fast-forwarding quantum evolution. Quantum, 5: 577, November 2021. 10.22331\/q-2021-11-15-577.","DOI":"10.22331\/q-2021-11-15-577"},{"key":"27","doi-asserted-by":"publisher","unstructured":"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\u2013360. IEEE, (2018). 10.1137\/18M1231511.","DOI":"10.1137\/18M1231511"},{"key":"28","doi-asserted-by":"publisher","unstructured":"Zoe Holmes, Gopikrishnan Muraleedharan, Rolando D Somma, Yigit Subasi, and Burak \u015eahino\u011flu. Quantum algorithms from fluctuation theorems: Thermal-state preparation. Quantum, 6: 825, 2022. 10.22331\/q-2022-10-06-825.","DOI":"10.22331\/q-2022-10-06-825"},{"key":"29","doi-asserted-by":"publisher","unstructured":"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\u2013535, 2007. 10.1145\/1250790.1250867.","DOI":"10.1145\/1250790.1250867"},{"key":"30","doi-asserted-by":"publisher","unstructured":"Stephen P. Jordan. Fast quantum computation at arbitrarily low energy. Phys. Rev. A, 95: 032305, Mar 2017. 10.1103\/PhysRevA.95.032305.","DOI":"10.1103\/PhysRevA.95.032305"},{"key":"31","doi-asserted-by":"publisher","unstructured":"Stephen P Jordan, Keith S.M. Lee, and John Preskill. Quantum algorithms for quantum field theories. Science, 336: 1130, (2012). 10.1126\/science.1217069.","DOI":"10.1126\/science.1217069"},{"key":"32","doi-asserted-by":"publisher","unstructured":"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\u2013111, 2010. 10.1038\/nchem.483.","DOI":"10.1038\/nchem.483"},{"key":"33","doi-asserted-by":"publisher","unstructured":"Seth Lloyd. Universal quantum simulators. Science, 273 (5278): 1073\u20131078, (1996). 10.1126\/science.273.5278.1073.","DOI":"10.1126\/science.273.5278.1073"},{"key":"34","doi-asserted-by":"publisher","unstructured":"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\u2013502, New York, NY, USA, 2019. 10.1145\/3313276.3316386.","DOI":"10.1145\/3313276.3316386"},{"key":"35","doi-asserted-by":"publisher","unstructured":"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.","DOI":"10.1103\/PhysRevLett.118.010501"},{"key":"36","doi-asserted-by":"publisher","unstructured":"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.","DOI":"10.48550\/arXiv.1707.05391"},{"key":"37","doi-asserted-by":"publisher","unstructured":"Guang Hao Low and Isaac L Chuang. Hamiltonian simulation by qubitization. Quantum, 3: 163, 2019. 10.22331\/q-2019-07-12-163.","DOI":"10.22331\/q-2019-07-12-163"},{"key":"38","doi-asserted-by":"publisher","unstructured":"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.","DOI":"10.48550\/arXiv.2305.04908"},{"key":"39","doi-asserted-by":"publisher","unstructured":"Michael A Nielsen and Isaac L Chuang. Quantum computation and quantum information. Cambridge university press, 2010. 10.1119\/1.1463744.","DOI":"10.1119\/1.1463744"},{"key":"40","doi-asserted-by":"publisher","unstructured":"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.","DOI":"10.22331\/q-2021-11-08-573"},{"key":"41","doi-asserted-by":"publisher","unstructured":"Ben W Reichardt. Span programs are equivalent to quantum query algorithms. SIAM Journal on Computing, 43 (3): 1206\u20131219, 2014. 10.1137\/100792640.","DOI":"10.1137\/100792640"},{"key":"42","doi-asserted-by":"publisher","unstructured":"Subir Sachdev. Quantum phase transitions. Physics world, 12 (4): 33, 1999. 10.1002\/9780470022184.hmm108.","DOI":"10.1002\/9780470022184.hmm108"},{"key":"43","doi-asserted-by":"publisher","unstructured":"Burak \u015eahino\u011flu and Rolando D Somma. Hamiltonian simulation in the low-energy subspace. npj Quantum Information, 7 (1): 119, 2021. 10.1038\/s41534-021-00451-w.","DOI":"10.1038\/s41534-021-00451-w"},{"key":"44","doi-asserted-by":"publisher","unstructured":"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.","DOI":"10.1103\/PhysRevLett.100.250501"},{"key":"45","doi-asserted-by":"publisher","unstructured":"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.","DOI":"10.1103\/PhysRevA.65.042323"},{"key":"46","doi-asserted-by":"publisher","unstructured":"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.","DOI":"10.1063\/1.4952761"},{"key":"47","unstructured":"Rolando D. Somma. Quantum simulations of one dimensional quantum systems. Quantum Info. Comput., 16 (13\u201314): 1125\u20131168, oct 2016. ISSN 1533-7146."},{"key":"48","doi-asserted-by":"publisher","unstructured":"Rolando D Somma and Sergio Boixo. Spectral gap amplification. SIAM Journal on Computing, 42 (2): 593\u2013610, 2013. 10.1137\/120871997.","DOI":"10.1137\/120871997"},{"key":"49","doi-asserted-by":"publisher","unstructured":"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.","DOI":"10.22331\/q-2023-08-16-1084"},{"key":"50","doi-asserted-by":"publisher","unstructured":"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.","DOI":"10.1103\/PRXQuantum.2.010323"},{"key":"51","doi-asserted-by":"publisher","unstructured":"Nathan Wiebe, Dominic Berry, Peter H\u00f8yer, 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.","DOI":"10.1088\/1751-8113\/43\/6\/065203"}],"container-title":["Quantum"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/quantum-journal.org\/papers\/q-2024-08-27-1449\/pdf\/","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"}],"deposited":{"date-parts":[[2024,8,27]],"date-time":"2024-08-27T16:11:43Z","timestamp":1724775103000},"score":1,"resource":{"primary":{"URL":"https:\/\/quantum-journal.org\/papers\/q-2024-08-27-1449\/"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2024,8,27]]},"references-count":52,"URL":"https:\/\/doi.org\/10.22331\/q-2024-08-27-1449","archive":["CLOCKSS"],"relation":{},"ISSN":["2521-327X"],"issn-type":[{"value":"2521-327X","type":"electronic"}],"subject":[],"published":{"date-parts":[[2024,8,27]]},"article-number":"1449"}}