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

Abstract

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.

► References

[1] 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

[2] 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

[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.
https:/​/​doi.org/​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.
https:/​/​doi.org/​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.
https:/​/​doi.org/​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.
https:/​/​doi.org/​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.
https:/​/​doi.org/​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.
https:/​/​doi.org/​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.
https:/​/​doi.org/​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.
https:/​/​doi.org/​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.
https:/​/​doi.org/​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.
https:/​/​doi.org/​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.
https:/​/​doi.org/​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.
https:/​/​doi.org/​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.
https:/​/​doi.org/​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.
https:/​/​doi.org/​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.
https:/​/​doi.org/​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.
https:/​/​doi.org/​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.
https:/​/​doi.org/​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.
https:/​/​doi.org/​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.
https:/​/​doi.org/​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.
https:/​/​doi.org/​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.
https:/​/​doi.org/​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.
https:/​/​doi.org/​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.
https:/​/​doi.org/​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.
arXiv:quant-ph/0601001

[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.
https:/​/​doi.org/​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.
https:/​/​doi.org/​10.1137/​08072689X

[29] Rolando D. Somma and Sergio Boixo. Spectral gap amplification. SIAM J. Comp, 42: 593–610, 2013. 10.1137/​120871997.
https:/​/​doi.org/​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.
https:/​/​doi.org/​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.
https:/​/​doi.org/​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.
https:/​/​doi.org/​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.
https:/​/​doi.org/​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.
https:/​/​doi.org/​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.
https:/​/​doi.org/​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.
https:/​/​doi.org/​10.1109/​QCE49297.2020.00021

[38] M. Nielsen and I. Chuang. Quantum Computation and Quantum Information. Cambridge University Press, Cambridge, 2001. 10.1017/​CBO9780511976667.
https:/​/​doi.org/​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.
https:/​/​doi.org/​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.
https:/​/​doi.org/​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.
https:/​/​doi.org/​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.
https:/​/​doi.org/​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.
https:/​/​doi.org/​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.
arXiv:2104.00728

[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.
https:/​/​doi.org/​10.1090/​S0002-9939-1993-1151817-6

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

[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.
https:/​/​doi.org/​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.
https:/​/​doi.org/​10.1016/​0146-6410(83)90028-5

[50] Rodney J Baxter. Exactly solved models in statistical mechanics. Elsevier, 2016. 10.1142/​9789814415255_0002.
https:/​/​doi.org/​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.
https:/​/​doi.org/​10.1007/​BF02107233

[52] Bill Sutherland. Beautiful models: 70 years of exactly solved quantum many-body problems. World Scientific, 2004. 10.1142/​5552.
https:/​/​doi.org/​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.
https:/​/​doi.org/​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.
https:/​/​doi.org/​10.1103/​PhysRevB.86.045125

Cited by

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

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

[3] Efekan Kökcü, Daan Camps, Lindsay Bassman, 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).

[4] Yu Tong, Victor V. Albert, Jarrod R. McClean, John Preskill, and Yuan Su, "Provably accurate simulation of gauge theories and bosonic systems", arXiv:2110.06942.

[5] John Golden, Andreas Bärtschi, Stephan Eidenbenz, and Daniel O'Malley, "Evidence for Super-Polynomial Advantage of QAOA over Unstructured Search", arXiv:2202.00648.

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

[7] Zhicheng Zhang, Qisheng Wang, and Mingsheng Ying, "Parallel Quantum Algorithm for Hamiltonian Simulation", arXiv:2105.11889.

[8] 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.

The above citations are from Crossref's cited-by service (last updated successfully 2022-05-20 07:36:30) and SAO/NASA ADS (last updated successfully 2022-05-20 07:36:32). The list may be incomplete as not all publishers provide suitable and complete citation data.