Fast-forwarding quantum evolution

Shouzhen Gu1, Rolando D. Somma2, and Burak Şahinoğlu2

1Institute for Quantum Information and Matter, California Institute of Technology, Pasadena, CA 91125, USA
2Theoretical Division, Los Alamos National Laboratory, Los Alamos, NM 87545, USA

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


We investigate the problem of fast-forwarding quantum evolution, whereby the dynamics of certain quantum systems can be simulated with gate complexity that is sublinear in the evolution time. We provide a definition of fast-forwarding that considers the model of quantum computation, the Hamiltonians that induce the evolution, and the properties of the initial states. Our definition accounts for $any$ asymptotic complexity improvement of the general case and we use it to demonstrate fast-forwarding in several quantum systems. In particular, we show that some local spin systems whose Hamiltonians can be taken into block diagonal form using an efficient quantum circuit, such as those that are permutation-invariant, can be exponentially fast-forwarded. We also show that certain classes of positive semidefinite local spin systems, also known as frustration-free, can be polynomially fast-forwarded, provided the initial state is supported on a subspace of sufficiently low energies. Last, we show that all quadratic fermionic systems and number-conserving quadratic bosonic systems can be exponentially fast-forwarded in a model where quantum gates are exponentials of specific fermionic or bosonic operators, respectively. Our results extend the classes of physical Hamiltonians that were previously known to be fast-forwarded, while not necessarily requiring methods that diagonalize the Hamiltonians efficiently. We further develop a connection between fast-forwarding and precise energy measurements that also accounts for polynomial improvements.

► BibTeX data

► References

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

[2] Seth Lloyd. Universal quantum simulators. Science, 273 (5278): 1073–1078, 1996. 10.1126/​science.273.5278.1073.

[3] R. D. Somma, G. Ortiz, J. E. Gubernatis, E. Knill, and R. Laflamme. Simulating physical phenomena by quantum networks. Phys. Rev. A, 65: 042323, 2002. 10.1103/​PhysRevA.65.042323.

[4] D.W. Berry, G. Ahokas, R. Cleve, and B.C. Sanders. Efficient quantum algorithms for simulating sparse Hamiltonians. Comm. Math. Phys., 270: 359, 2007. 10.1007/​s00220-006-0150-x.

[5] N. Wiebe, D. Berry, P. Hoyer, and B.C. Sanders. Higher order decompositions of ordered operator exponentials. J. Phys. A: Math. Theor., 43: 065203, 2010. 10.1088/​1751-8113/​43/​6/​065203.

[6] A. M. Childs and N. Wiebe. Hamiltonian simulation using linear combinations of unitary operations. Quantum Information and Computation, 12: 901–924, 2012. 10.26421/​QIC12.11-12-1.

[7] Dominic W. Berry and Andrew M. Childs. Black-box Hamiltonian simulation and unitary implementation. Quantum Information and Computation, 12 (1–2): 29–62, 2012. 10.26421/​QIC12.1-2-4. arXiv:0910.4157.

[8] Dominic W. Berry, Andrew M. Childs, Richard Cleve, Robin Kothari, and Rolando D. Somma. Exponential improvement in precision for simulating sparse Hamiltonians. In Proc. of the 46th ACM Symposium on Theory of Computing, pages 283–292, 2014. 10.1145/​2591796.2591854.

[9] Dominic W. Berry, Andrew M. Childs, Richard Cleve, Robin Kothari, and Rolando D. Somma. Simulating Hamiltonian dynamics with a truncated Taylor series. Phys. Rev. Lett., 114: 090502, 2015a. 10.1103/​PhysRevLett.114.090502.

[10] Dominic W. Berry, Andrew M. Childs, and Robin Kothari. Hamiltonian simulation with nearly optimal dependence on all parameters. In Proceedings of the 56th Symposium on Foundations of Computer Science, 2015b. 10.1109/​FOCS.2015.54.

[11] G.H. Low and I.L. Chuang. Optimal Hamiltonian simulation by quantum signal processing. Phys. Rev. Lett., 118: 010501, 2017. 10.1103/​PhysRevLett.118.010501.

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

[13] Earl Campbell. Random compiler for fast Hamiltonian simulation. Physical review letters, 123 (7): 070503, 2019. 10.1103/​PhysRevLett.123.070503.

[14] Dominic W Berry, Andrew M Childs, Yuan Su, Xin Wang, and Nathan Wiebe. Time-dependent Hamiltonian simulation with $ {L}^1$-norm scaling. Quantum, 4: 254, 2020. 10.22331/​q-2020-04-20-254.

[15] Y. Atia and D. Aharonov. Fast-forwarding of Hamiltonians and exponentially precise measurements. Nat. Comm., 8: 1572, 2017. 10.1038/​s41467-017-01637-7.

[16] Jeongwan Haah, Matthew B. Hastings, Robin Kothari, and Guang Hao Low. Quantum algorithm for simulating real time evolution of lattice Hamiltonians. In Proceedings of the IEEE 59th Symposium on Foundations of Computer Science, page 350, 2018. 10.1109/​FOCS.2018.00041.

[17] Aram W. Harrow, Avinatan Hassidim, and Seth Lloyd. Quantum algorithm for linear systems of equations. Phys. Rev. Lett., 103 (15): 150502, 2009. 10.1103/​PhysRevLett.103.150502.

[18] Andrew M. Childs, Robin Kothari, and Rolando D. Somma. Quantum linear systems algorithm with exponentially improved dependence on precision. SIAM J. Comp., 46: 1920, 2017. 10.1137/​16M1087072.

[19] Frank Verstraete, J. Ignacio Cirac, and José I. Latorre. Quantum circuits for strongly correlated quantum systems. Phys. Rev. A, 79: 032316, 2009. 10.1103/​PhysRevA.79.032316.

[20] Ian D. Kivlichan, Jarrod McClean, Nathan Wiebe, Craig Gidney, Alán Aspuru-Guzik, Garnet Kin-Lic Chan, and Ryan Babbush. Quantum simulation of electronic structure with linear depth and connectivity. Phys. Rev. Lett., 120: 110501, 2018. 10.1103/​PhysRevLett.120.110501.

[21] Zhang Jiang, Kevin J. Sung, Kostyantyn Kechedzhi, Vadim N. Smelyanskiy, and Sergio Boixo. Quantum algorithms to simulate many-body physics of correlated fermions. Phys. Rev. Applied, 9: 044036, 2018. 10.1103/​PhysRevApplied.9.044036.

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

[23] Minh C. Tran, Yuan Su, Daniel Carney, and Jacob M. Taylor. Faster digital quantum simulation by symmetry protection. PRX Quantum, 2: 010323, 2021. 10.1103/​PRXQuantum.2.010323.

[24] Yuan Su, Hsin-Yuan Huang, and Earl T. Campbell. Nearly tight Trotterization of interacting electrons. Quantum, 5: 495, 2021. 10.22331/​q-2021-07-05-495.

[25] Dave Bacon, Isaac L. Chuang, and Aram W. Harrow. Efficient quantum circuits for Schur and Clebsch-Gordan transforms. Physical Review Letters, 97 (17): 170502, 2006. 10.1103/​PhysRevLett.97.170502.

[26] Dave Bacon, Isaac L. Chuang, and Aram W. Harrow. The quantum Schur transform: I. Efficient qudit circuits. arXiv:quant-ph/​0601001, 2005.

[27] David Perez-Garcia, Frank Verstraete, J. Ignacio Cirac, and Michael M. Wolf. PEPS as unique ground states of local Hamiltonians. Quantum Inf. Comp., 8: 0650, 2008. 10.26421/​QIC8.6-7-6.

[28] Sergey Bravyi and Barbara Terhal. Complexity of stoquastic frustration-free Hamiltonians. SIAM J. Comp., 39 (4): 1462, 2009. 10.1137/​08072689X.

[29] Rolando D. Somma and Sergio Boixo. Spectral gap amplification. SIAM J. Comp, 42: 593–610, 2013. 10.1137/​120871997.

[30] Anirban N. Chowdhury and Rolando D. Somma. Quantum algorithms for Gibbs sampling and hitting-time estimation. Quant. Inf. Comp., 17: 0041, 2017. 10.26421/​QIC17.1-2-3.

[31] Alexei Y. Kitaev. Quantum measurements and the Abelian stabilizer problem. Electron. Colloquium Comput. Complex., (3), 1996.

[32] R. Cleve, A. Ekert, C. Macchiavello, and M. Mosca. Quantum algorithms revisited. Proc. R. Soc. Lond. A, 454: 339–354, 1998. 10.1098/​rspa.1998.0164.

[33] Harry J Lipkin, N Meshkov, and AJ Glick. Validity of many-body approximation methods for a solvable model: (I). Exact solutions and perturbation theory. Nuclear Physics, 62 (2): 188–198, 1965. 10.1016/​0029-5582(65)90862-X.

[34] I. Affleck, T. Kennedy, E. H. Lieb, and H. Tasaki. Valence bond ground states in isotropic quantum antiferromagnets. Comm. Math. Phys., 115: 477, 1988. 10.1007/​978-3-662-06390-3_19.

[35] Stephen P Jordan, Keith SM Lee, and John Preskill. Quantum algorithms for quantum field theories. Science, 336 (6085): 1130–1133, 2012. 10.1126/​science.1217069.

[36] Paolo Zanardi. Symmetrizing evolutions. Physics Letters A, 258 (2-3): 77–82, 1999. 10.1016/​S0375-9601(99)00365-5.

[37] Jeremy Cook, Stephan Eidenbenz, and Andreas Bärtschi. The quantum alternating operator ansatz on maximum k-vertex cover. In 2020 IEEE International Conference on Quantum Computing and Engineering (QCE), pages 83–92. IEEE, 2020. 10.1109/​QCE49297.2020.00021.

[38] M. Nielsen and I. Chuang. Quantum Computation and Quantum Information. Cambridge University Press, Cambridge, 2001. 10.1017/​CBO9780511976667.

[39] Guang Hao Low and Isaac L Chuang. Hamiltonian simulation by qubitization. Quantum, 3: 163, 2019b. 10.22331/​q-2019-07-12-163.

[40] Andrew M Childs. On the relationship between continuous-and discrete-time quantum walk. Communications in Mathematical Physics, 294 (2): 581–603, 2010. 10.1007/​s00220-009-0930-1.

[41] Emanuel Knill, Gerardo Ortiz, and Rolando D. Somma. Optimal quantum measurements of expectation values of observables. Phys. Rev. A, 75: 012328, 2007. 10.1103/​PhysRevA.75.012328.

[42] Michael Reed and Barry Simon. Methods of modern mathematical physics. Academic press, 1978.

[43] R. D. Somma, G. Ortiz, E. Knill, and J. E. Gubernatis. Quantum simulations of physics problems. Int. J. Quant. Inf., 1: 189, 2003. 10.1142/​S0219749903000140.

[44] Cristina Cirstoiu, Zoe Holmes, Joseph Iosue, Lukasz Cincio, Patrick J Coles, and Andrew Sornborger. Variational fast forwarding for quantum simulation beyond the coherence time. npj Quantum Information, 6 (1): 1–10, 2020. 10.1038/​s41534-020-00302-0.

[45] Efekan Kökcü, Thomas Steckmann, J. K. Freericks, Eugene F. Dumitrescu, and Alexander F. Kemper. Fixed depth Hamiltonian simulation via Cartan decomposition. arXiv:2104.00728 [cond-mat, physics:quant-ph], 2021.

[46] N. J. Wildberger. Diagonalization in compact lie algebras and a new proof of a theorem of kostant. Proceedings of the American Mathematical Society, 119 (2): 649–655, 1993. 10.1090/​S0002-9939-1993-1151817-6.

[47] Rolando D Somma. Quantum computation, complexity, and many-body physics. arXiv quant-ph/​0512209, 2005.

[48] Rolando D Somma. Unitary circuit synthesis for tomography of generalized coherent states. Journal of Mathematical Physics, 60 (11): 112202, 2019. 10.1063/​1.5121549.

[49] Robert Gilmore and Da Hsuan Feng. Coherent states for bosons and fermions: A tutorial. Progress in Particle and Nuclear Physics, 9: 479, 1983. 10.1016/​0146-6410(83)90028-5.

[50] Rodney J Baxter. Exactly solved models in statistical mechanics. Elsevier, 2016. 10.1142/​9789814415255_0002.

[51] Vladimir E Korepin, Nicholay M Bogoliubov, and Anatoli G Izergin. Quantum inverse scattering method and correlation functions, volume 3. Cambridge university press, 1997. 10.1007/​BF02107233.

[52] Bill Sutherland. Beautiful models: 70 years of exactly solved quantum many-body problems. World Scientific, 2004. 10.1142/​5552.

[53] Rolando Somma, Howard Barnum, Gerardo Ortiz, and Emanuel Knill. Efficient solvability of Hamiltonians and limits on the power of some quantum computational models. Physical review letters, 97 (19): 190501, 2006. 10.1103/​PhysRevLett.97.190501.

[54] Valentin Murg, Vladimir E Korepin, and Frank Verstraete. Algebraic Bethe ansatz and tensor networks. Physical Review B, 86 (4): 045125, 2012. 10.1103/​PhysRevB.86.045125.

Cited by

[1] Eric R. Anschuetz, Andreas Bauer, Bobak T. Kiani, and Seth Lloyd, "Efficient classical algorithms for simulating symmetric quantum systems", Quantum 7, 1189 (2023).

[2] Yulong Dong, Lin Lin, and Yu Tong, "Ground-State Preparation and Energy Estimation on Early Fault-Tolerant Quantum Computers via Quantum Eigenvalue Transformation of Unitary Matrices", PRX Quantum 3 4, 040305 (2022).

[3] Oriel Kiss, Michele Grossi, and Alessandro Roggero, "Importance sampling for stochastic quantum simulations", Quantum 7, 977 (2023).

[4] Jarrod R. McClean, Nicholas C. Rubin, Joonho Lee, Matthew P. Harrigan, Thomas E. O’Brien, Ryan Babbush, William J. Huggins, and Hsin-Yuan Huang, "What the foundations of quantum computer science teach us about chemistry", The Journal of Chemical Physics 155 15, 150901 (2021).

[5] Yu Tong, Victor V. Albert, Jarrod R. McClean, John Preskill, and Yuan Su, "Provably accurate simulation of gauge theories and bosonic systems", Quantum 6, 816 (2022).

[6] John Golden, Andreas Bärtschi, Daniel O'Malley, and Stephan Eidenbenz, 2023 IEEE International Conference on Quantum Computing and Engineering (QCE) 496 (2023) ISBN:979-8-3503-4323-6.

[7] Zhicheng Zhang, Qisheng Wang, and Mingsheng Ying, "Parallel Quantum Algorithm for Hamiltonian Simulation", Quantum 8, 1228 (2024).

[8] Hao-Nan Xie, Shi-Jie Wei, Fan Yang, Zheng-An Wang, Chi-Tong Chen, Heng Fan, and Gui-Lu Long, "Probabilistic imaginary-time evolution algorithm based on nonunitary quantum circuits", Physical Review A 109 5, 052414 (2024).

[9] Guang Hao Low, Yuan Su, Yu Tong, and Minh C. Tran, "Complexity of Implementing Trotter Steps", PRX Quantum 4 2, 020323 (2023).

[10] Guanlin Jian, Yuan Yang, Ze Liu, Zhen-Gang Zhu, and Zhengchuan Wang, "Towards simulating time evolution of specific quantum many-body system by lower counts of quantum gates", Europhysics Letters 141 1, 10003 (2023).

[11] Yuan Su, "Fast-Forwardable Quantum Evolution and Where to Find Them", Quantum Views 5, 62 (2021).

[12] Jeremy Hartse and Alessandro Roggero, "Faster spectral density calculation using energy moments", The European Physical Journal A 59 3, 41 (2023).

[13] Efekan Kökcü, Thomas Steckmann, Yan Wang, J. K. Freericks, Eugene F. Dumitrescu, and Alexander F. Kemper, "Fixed Depth Hamiltonian Simulation via Cartan Decomposition", Physical Review Letters 129 7, 070501 (2022).

[14] Thomas Steckmann, Trevor Keen, Efekan Kökcü, Alexander F. Kemper, Eugene F. Dumitrescu, and Yan Wang, "Mapping the metal-insulator phase diagram by algebraically fast-forwarding dynamics on a cloud quantum computer", Physical Review Research 5 2, 023198 (2023).

[15] Cristian L. Cortes, A. Eugene DePrince, and Stephen K. Gray, "Fast-forwarding quantum simulation with real-time quantum Krylov subspace algorithms", Physical Review A 106 4, 042409 (2022).

[16] Mario Motta, William Kirby, Ieva Liepuoniute, Kevin J Sung, Jeffrey Cohn, Antonio Mezzacapo, Katherine Klymko, Nam Nguyen, Nobuyuki Yoshioka, and Julia E Rice, "Subspace methods for electronic structure simulations on quantum computers", Electronic Structure 6 1, 013001 (2024).

[17] Efekan Kökcü, Daan Camps, Lindsay Bassman Oftelie, J. K. Freericks, Wibe A. de Jong, Roel Van Beeumen, and Alexander F. Kemper, "Algebraic compression of quantum circuits for Hamiltonian evolution", Physical Review A 105 3, 032420 (2022).

[18] Duarte Magano, João Moutinho, and Bruno Coutinho, "On the quantum simulation of complex networks", SciPost Physics Core 6 3, 058 (2023).

[19] Guang Hao Low, Yuan Su, Yu Tong, and Minh C. Tran, "On the complexity of implementing Trotter steps", arXiv:2211.09133, (2022).

[20] Dong An, Jin-Peng Liu, Daochen Wang, and Qi Zhao, "A theory of quantum differential equation solvers: limitations and fast-forwarding", arXiv:2211.05246, (2022).

[21] John Golden, Andreas Bärtschi, Stephan Eidenbenz, and Daniel O'Malley, "Numerical Evidence for Exponential Speed-up of QAOA over Unstructured Search for Approximate Constrained Optimization", arXiv:2202.00648, (2022).

[22] Lindsay Bassman, Roel Van Beeumen, Ed Younis, Ethan Smith, Costin Iancu, and Wibe A. de Jong, "Constant-depth circuits for dynamic simulations of materials on quantum computers", Materials Theory 6 1, 13 (2022).

[23] Yen Ting Lin, Robert B. Lowrie, Denis Aslangil, Yiğit Subaşı, and Andrew T. Sornborger, "Koopman von Neumann mechanics and the Koopman representation: A perspective on solving nonlinear dynamical systems with quantum computers", arXiv:2202.02188, (2022).

[24] Efekan Kökcü, Daan Camps, Lindsay Bassman Oftelie, Wibe A. de Jong, Roel Van Beeumen, and A. F. Kemper, "Algebraic Compression of Free Fermionic Quantum Circuits: Particle Creation, Arbitrary Lattices and Controlled Evolution", arXiv:2303.09538, (2023).

[25] Tanmoy Bhattacharya, Shailesh Chandrasekharan, Rajan Gupta, Thomas R. Richardson, and Hersh Singh, "Topological terms with qubit regularization and relativistic quantum circuits", arXiv:2310.06805, (2023).

[26] Nai-Hui Chia, Kai-Min Chung, Yao-Ching Hsieh, Han-Hsuan Lin, Yao-Ting Lin, and Yu-Ching Shen, "On the Impossibility of General Parallel Fast-forwarding of Hamiltonian Simulation", arXiv:2305.12444, (2023).

The above citations are from Crossref's cited-by service (last updated successfully 2024-06-22 13:37:35) and SAO/NASA ADS (last updated successfully 2024-06-22 13:37:36). The list may be incomplete as not all publishers provide suitable and complete citation data.