Optimal Hamiltonian simulation for time-periodic systems
1RIKEN Center for Quantum Computing (RQC), Hirosawa 2-1, Wako, Saitama 351-0198, Japan
2Graduate School of Engineering Science, Osaka University, 1-3 Machikaneyama, Toyonaka, Osaka 560-8531, Japan.
3Center for Quantum Information and Quantum Biology, Osaka University, Japan.
4Fujitsu Quantum Computing Joint Research Division at QIQB, Osaka University, 1-2 Machikaneyama, Toyonaka 560-0043, Japan
Published: | 2023-03-28, volume 7, page 962 |
Eprint: | arXiv:2209.05048v3 |
Doi: | https://doi.org/10.22331/q-2023-03-28-962 |
Citation: | Quantum 7, 962 (2023). |
Find this paper interesting or want to discuss? Scite or leave a comment on SciRate.
Abstract
The implementation of time-evolution operators $U(t)$, called Hamiltonian simulation, is one of the most promising usage of quantum computers. For time-independent Hamiltonians, qubitization has recently established efficient realization of time-evolution $U(t)=e^{-iHt}$, with achieving the optimal computational resource both in time $t$ and an allowable error $\varepsilon$. In contrast, those for time-dependent systems require larger cost due to the difficulty of handling time-dependency. In this paper, we establish optimal/nearly-optimal Hamiltonian simulation for generic time-dependent systems with time-periodicity, known as Floquet systems. By using a so-called Floquet-Hilbert space equipped with auxiliary states labeling Fourier indices, we develop a way to certainly obtain the target time-evolved state without relying on either time-ordered product or Dyson-series expansion. Consequently, the query complexity, which measures the cost for implementing the time-evolution, has optimal and nearly-optimal dependency respectively in time $t$ and inverse error $\varepsilon$, and becomes sufficiently close to that of qubitization. Thus, our protocol tells us that, among generic time-dependent systems, time-periodic systems provides a class accessible as efficiently as time-independent systems despite the existence of time-dependency. As we also provide applications to simulation of nonequilibrium phenomena and adiabatic state preparation, our results will shed light on nonequilibrium phenomena in condensed matter physics and quantum chemistry, and quantum tasks yielding time-dependency in quantum computation.
![](https://quantum-journal.org/wp-content/uploads/2023/03/img_1679622349.jpg)
Featured image: Role of optimal quantum algorithm for time-periodic Hamiltonian simulation
Popular summary
► BibTeX data
► References
[1] Richard P. Feynman. ``Simulating Physics with Computers''. Int. J. Theor. Physics 21, 467 (1982).
https://doi.org/10.1007/BF02650179
[2] S Lloyd. ``Universal Quantum Simulators''. Science 273, 1073–1078 (1996).
https://doi.org/10.1126/science.273.5278.1073
[3] Adam Smith, M S Kim, Frank Pollmann, and Johannes Knolle. ``Simulating quantum many-body dynamics on a current digital quantum computer''. npj Quantum Information 5, 1–13 (2019).
https://doi.org/10.1038/s41534-019-0217-0
[4] Frank Arute et al. ``Observation of separated dynamics of charge and spin in the Fermi-Hubbard model'' (2020). arXiv:2010.07965.
arXiv:2010.07965
[5] A. Yu. Kitaev. ``Quantum measurements and the Abelian Stabilizer Problem'' (1995). arXiv:quant-ph/9511026.
arXiv:quant-ph/9511026
[6] Jiangfeng Du, Nanyang Xu, Xinhua Peng, Pengfei Wang, Sanfeng Wu, and Dawei Lu. ``NMR implementation of a molecular hydrogen quantum simulation with adiabatic state preparation''. Phys. Rev. Lett. 104, 030502 (2010).
https://doi.org/10.1103/PhysRevLett.104.030502
[7] B P Lanyon et al. ``Towards quantum chemistry on a quantum computer''. Nat. Chem. 2, 106–111 (2010).
https://doi.org/10.1038/nchem.483
[8] P. J. J O'Malley et al. ``Scalable Quantum Simulation of Molecular Energies''. Phys. Rev. X 6, 031007 (2016).
https://doi.org/10.1103/PhysRevX.6.031007
[9] Daniel S Abrams and Seth Lloyd. ``Simulation of Many-Body Fermi Systems on a Universal Quantum Computer''. Phys. Rev. Lett. 79, 2586–2589 (1997).
https://doi.org/10.1103/PhysRevLett.79.2586
[10] A T Sornborger and E D Stewart. ``Higher-order methods for simulations on quantum computers''. Phys. Rev. A 60, 1956–1965 (1999).
https://doi.org/10.1103/PhysRevA.60.1956
[11] Earl Campbell. ``Random Compiler for Fast Hamiltonian Simulation''. Phys. Rev. Lett. 123, 070503 (2019).
https://doi.org/10.1103/PhysRevLett.123.070503
[12] Andrew M. Childs, Yuan Su, Minh C. Tran, Nathan Wiebe, and Shuchen Zhu. ``Theory of Trotter Error with Commutator Scaling''. Phys. Rev. X 11, 011020 (2021).
https://doi.org/10.1103/PhysRevX.11.011020
[13] Andrew M Childs and Nathan Wiebe. ``Hamiltonian simulation using linear combinations of unitary operations''. Quantum Information & Computation 12, 901 (2012).
https://doi.org/10.26421/QIC12.11-12-1
[14] Dominic W Berry, Andrew M Childs, and Robin Kothari. ``Hamiltonian Simulation with Nearly Optimal Dependence on all Parameters''. In 2015 IEEE 56th Annual Symposium on Foundations of Computer Science. Pages 792–809. ieeexplore.ieee.org (2015).
https://doi.org/10.1109/FOCS.2015.54
[15] 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 (2015).
https://doi.org/10.1103/PhysRevLett.114.090502
[16] Dominic W Berry, Andrew M Childs, Richard Cleve, Robin Kothari, and Rolando D Somma. ``Exponential improvement in precision for simulating sparse Hamiltonians''. Forum of Mathematics, Sigma 5, E8 (2017).
https://doi.org/10.1017/fms.2017.2
[17] Guang Hao Low and Isaac L Chuang. ``Optimal Hamiltonian Simulation by Quantum Signal Processing''. Phys. Rev. Lett. 118, 010501 (2017).
https://doi.org/10.1103/PhysRevLett.118.010501
[18] Guang Hao Low and Isaac L Chuang. ``Hamiltonian simulation by qubitization''. Quantum 3, 163 (2019).
https://doi.org/10.22331/q-2019-07-12-163
[19] Guang Hao Low and Nathan Wiebe. ``Hamiltonian simulation in the interaction picture'' (2018). arXiv:1805.00675.
arXiv:1805.00675
[20] Mária Kieferová, Artur Scherer, and Dominic W Berry. ``Simulating the dynamics of time-dependent Hamiltonians with a truncated Dyson series''. Phys. Rev. A 99, 042314 (2019).
https://doi.org/10.1103/PhysRevA.99.042314
[21] 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).
https://doi.org/10.22331/q-2020-04-20-254
[22] Jeongwan Haah, Matthew B Hastings, Robin Kothari, and Guang Hao Low. ``Quantum algorithm for simulating real time evolution of lattice Hamiltonians''. SIAM J. Comput.Pages FOCS18–250–FOCS18–284 (2021).
https://doi.org/10.1137/18M1231511
[23] Yi-Hsiang Chen, Amir Kalev, and Itay Hen. ``Quantum Algorithm for Time-Dependent Hamiltonian Simulation by Permutation Expansion''. PRX Quantum 2, 030342 (2021).
https://doi.org/10.1103/PRXQuantum.2.030342
[24] Jacob Watkins, Nathan Wiebe, Alessandro Roggero, and Dean Lee. ``Time-dependent Hamiltonian Simulation Using Discrete Clock Constructions'' (2022). arXiv:2203.11353.
arXiv:2203.11353
[25] Takuya Kitagawa, Erez Berg, Mark Rudner, and Eugene Demler. ``Topological characterization of periodically driven quantum systems''. Phys. Rev. B 82, 235114 (2010).
https://doi.org/10.1103/PhysRevB.82.235114
[26] Mark S Rudner, Netanel H Lindner, Erez Berg, and Michael Levin. ``Anomalous edge states and the bulk-edge correspondence for periodically driven two-dimensional systems''. Physical Review X 3, 031005 (2013).
https://doi.org/10.1103/PhysRevX.3.031005
[27] Fenner Harper, Rahul Roy, Mark S. Rudner, and S.L. Sondhi. ``Topology and Broken Symmetry in Floquet Systems''. Annual Review of Condensed Matter Physics 11, 345–368 (2020).
https://doi.org/10.1146/annurev-conmatphys-031218-013721
[28] Vedika Khemani, Achilleas Lazarides, Roderich Moessner, and S L Sondhi. ``Phase Structure of Driven Quantum Systems''. Phys. Rev. Lett. 116, 250401 (2016).
https://doi.org/10.1103/PhysRevLett.116.250401
[29] Dominic V Else, Bela Bauer, and Chetan Nayak. ``Floquet Time Crystals''. Phys. Rev. Lett. 117, 090402 (2016).
https://doi.org/10.1103/PhysRevLett.117.090402
[30] Vedika Khemani, Roderich Moessner, and S L Sondhi. ``A Brief History of Time Crystals'' (2019). arXiv:1910.10745.
arXiv:1910.10745
[31] Feng Mei, Qihao Guo, Ya-Fei Yu, Liantuan Xiao, Shi-Liang Zhu, and Suotang Jia. ``Digital Simulation of Topological Matter on Programmable Quantum Processors''. Phys. Rev. Lett. 125, 160503 (2020).
https://doi.org/10.1103/PhysRevLett.125.160503
[32] J Randall et al. ``Many-body-localized discrete time crystal with a programmable spin-based quantum simulator''. Science 374, 1474 (2021).
https://doi.org/10.1126/science.abk0603
[33] Xiao Mi et al. ``Time-crystalline eigenstate order on a quantum processor''. Nature 601, 531–536 (2022).
https://doi.org/10.1038/s41586-021-04257-w
[34] R M Potvliege and R Shakeshaft. ``Multiphoton processes in an intense laser field: Harmonic generation and total ionization rates for atomic hydrogen''. Phys. Rev. A 40, 3061–3079 (1989).
https://doi.org/10.1103/PhysRevA.40.3061
[35] F H M Faisal and J Z Kamiński. ``Floquet-Bloch theory of high-harmonic generation in periodic structures''. Phys. Rev. A 56, 748–762 (1997).
https://doi.org/10.1103/PhysRevA.56.748
[36] Takashi Oka and Hideo Aoki. ``Photovoltaic Hall effect in graphene''. Phys. Rev. B 79, 081406 (2009).
https://doi.org/10.1103/PhysRevB.79.081406
[37] Takashi Oka and Sota Kitamura. ``Floquet Engineering of Quantum Materials''. Annual Review of Condensed Matter Physics 10, 387–408 (2019).
https://doi.org/10.1146/annurev-conmatphys-031218-013423
[38] D J Thouless. ``Quantization of particle transport''. Phys. Rev. B 27, 6083 (1983).
https://doi.org/10.1103/PhysRevB.27.6083
[39] M Lohse, C Schweizer, O Zilberberg, M Aidelsburger, and I Bloch. ``A Thouless quantum pump with ultracold bosonic atoms in an optical superlattice''. Nat. Phys. 12, 350–354 (2015).
https://doi.org/10.1038/nphys3584
[40] Shuta Nakajima, Takafumi Tomita, Shintaro Taie, Tomohiro Ichinose, Hideki Ozawa, Lei Wang, Matthias Troyer, and Yoshiro Takahashi. ``Topological Thouless pumping of ultracold fermions''. Nat. Phys. 12, 296–300 (2016).
https://doi.org/10.1038/nphys3622
[41] Alán Aspuru-Guzik, Anthony D Dutoi, Peter J Love, and Martin Head-Gordon. ``Simulated quantum computation of molecular energies''. Science 309, 1704–1707 (2005).
https://doi.org/10.1126/science.1113479
[42] Tameem Albash and Daniel A. Lidar. ``Adiabatic quantum computation''. Rev. Mod. Phys. 90, 015002 (2018).
https://doi.org/10.1103/RevModPhys.90.015002
[43] Elliott H Lieb and Derek W Robinson. ``The finite group velocity of quantum spin systems''. Commun. Math. Phys. 28, 251–257 (1972).
https://doi.org/10.1007/978-3-662-10018-9_25
[44] Hideo Sambe. ``Steady States and Quasienergies of a Quantum-Mechanical System in an Oscillating Field''. Phys. Rev. A 7, 2203–2213 (1973).
https://doi.org/10.1103/PhysRevA.7.2203
[45] T O Levante, M Baldus, B H Meier, and R R Ernst. ``Formalized quantum mechanical Floquet theory and its application to sample spinning in nuclear magnetic resonance''. Mol. Phys. 86, 1195–1212 (1995).
https://doi.org/10.1080/00268979500102671
[46] Ryan Babbush, Craig Gidney, Dominic W Berry, Nathan Wiebe, Jarrod McClean, Alexandru Paler, Austin Fowler, and Hartmut Neven. ``Encoding Electronic Spectra in Quantum Circuits with Linear T Complexity''. Phys. Rev. X 8, 041015 (2018).
https://doi.org/10.1103/PhysRevX.8.041015
[47] András Gilyén, Yuan Su, Guang Hao Low, and Nathan Wiebe. ``Quantum singular value transformation and beyond: exponential improvements for quantum matrix arithmetics''. Proceedings of the 51st Annual ACM SIGACT Symposium on Theory of Computing, 193–204 (2019).
https://doi.org/10.1145/3313276.3316366
[48] John M. Martyn, Zane M. Rossi, Andrew K. Tan, and Isaac L. Chuang. ``Grand Unification of Quantum Algorithms''. PRX Quantum 2, 040203 (2021).
https://doi.org/10.1103/PRXQuantum.2.040203
[49] Lov K. Grover. ``Quantum Mechanics Helps in Searching for a Needle in a Haystack''. Phys. Rev. Lett. 79, 325–328 (1997).
https://doi.org/10.1103/PhysRevLett.79.325
[50] Zongping Gong and Ryusuke Hamazaki. ``Bounds in Nonequilibrium Quantum Dynamics''. International Journal of Modern Physics B 36, 223007 (2022).
https://doi.org/10.1142/S0217979222300079
[51] Robert M Gray. ``Toeplitz and Circulant Matrices: A Review''. Foundations and Trends® in Communications and Information Theory 2, 155–239 (2006).
https://doi.org/10.1561/0100000006
[52] R M Corless, G H Gonnet, D E G Hare, D J Jeffrey, and D E Knuth. ``On the LambertW function''. Adv. Comput. Math. 5, 329–359 (1996).
https://doi.org/10.1007/BF02124750
[53] Steven A Cuccaro, Thomas G Draper, Samuel A Kutin, and David Petrie Moulton. ``A new quantum ripple-carry addition circuit'' (2004). arXiv:quant-ph/0410184.
arXiv:quant-ph/0410184
[54] Lov Grover and Terry Rudolph. ``Creating superpositions that correspond to efficiently integrable probability distributions'' (2002). arXiv:quant-ph/0208112.
arXiv:quant-ph/0208112
[55] Aram W. Harrow, Avinatan Hassidim, and Seth Lloyd. ``Quantum algorithm for linear systems of equations''. Phys. Rev. Lett. 103, 150502 (2009).
https://doi.org/10.1103/PhysRevLett.103.150502
[56] L K Grover. ``Synthesis of quantum superpositions by quantum computation''. Phys. Rev. Lett. 85, 1334–1337 (2000).
https://doi.org/10.1103/PhysRevLett.85.1334
[57] Yuval R Sanders, Guang Hao Low, Artur Scherer, and Dominic W Berry. ``Black-Box Quantum State Preparation without Arithmetic''. Phys. Rev. Lett. 122, 020502 (2019).
https://doi.org/10.1103/PhysRevLett.122.020502
[58] Arthur G Rattew and Bálint Koczor. ``Preparing Arbitrary Continuous Functions in Quantum Registers With Logarithmic Complexity'' (2022). arXiv:2205.00519.
arXiv:2205.00519
[59] Dmitry A Abanin, Wojciech De Roeck, and François Huveneers. ``Exponentially Slow Heating in Periodically Driven Many-Body Systems''. Phys. Rev. Lett. 115, 256803 (2015).
https://doi.org/10.1103/PhysRevLett.115.256803
[60] Tomotaka Kuwahara, Takashi Mori, and Keiji Saito. ``Floquet–Magnus theory and generic transient dynamics in periodically driven many-body quantum systems''. Ann. Phys. 367, 96–124 (2016).
https://doi.org/10.1016/j.aop.2016.01.012
[61] Takashi Mori, Tomotaka Kuwahara, and Keiji Saito. ``Rigorous Bound on Energy Absorption and Generic Relaxation in Periodically Driven Quantum Systems''. Phys. Rev. Lett. 116, 120401 (2016).
https://doi.org/10.1103/PhysRevLett.116.120401
[62] Dmitry A Abanin, Wojciech De Roeck, Wen Wei Ho, and François Huveneers. ``Effective Hamiltonians, prethermalization, and slow energy absorption in periodically driven many-body systems''. Phys. Rev. B 95, 014112 (2017).
https://doi.org/10.1103/PhysRevB.95.014112
[63] Dmitry Abanin, Wojciech De Roeck, Wen Wei Ho, and François Huveneers. ``A Rigorous Theory of Many-Body Prethermalization for Periodically Driven and Closed Quantum Systems''. Commun. Math. Phys. 354, 809–827 (2017).
https://doi.org/10.1007/s00220-017-2930-x
[64] Frank Verstraete, J Ignacio Cirac, and José I Latorre. ``Quantum circuits for strongly correlated quantum systems''. Phys. Rev. A 79, 032316 (2009).
https://doi.org/10.1103/PhysRevA.79.032316
[65] Andrew J Ferris. ``Fourier transform for fermionic systems and the spectral tensor network''. Phys. Rev. Lett. 113, 010401 (2014).
https://doi.org/10.1103/PhysRevLett.113.010401
[66] Ryan Babbush, Nathan Wiebe, Jarrod McClean, James McClain, Hartmut Neven, and Garnet Kin-Lic Chan. ``Low-Depth Quantum Simulation of Materials''. Phys. Rev. X 8, 011044 (2018).
https://doi.org/10.1103/PhysRevX.8.011044
[67] R E F Silva, Igor V Blinov, Alexey N Rubtsov, O Smirnova, and M Ivanov. ``High-harmonic spectroscopy of ultrafast many-body dynamics in strongly correlated systems''. Nat. Photonics 12, 266–270 (2018).
https://doi.org/10.1038/s41566-018-0129-0
[68] Yuta Murakami, Martin Eckstein, and Philipp Werner. ``High-Harmonic Generation in Mott Insulators''. Phys. Rev. Lett. 121, 057405 (2018).
https://doi.org/10.1103/PhysRevLett.121.057405
[69] Yuta Murakami, Shintaro Takayoshi, Akihisa Koga, and Philipp Werner. ``High-harmonic generation in one-dimensional Mott insulators''. Phys. Rev. B 103, 035110 (2021).
https://doi.org/10.1103/PhysRevB.103.035110
[70] In order to capture nontrivial phenomena in the steady states, we should attach a coupling with an external bath to the time-independent term $H_0$. While it alters the block-encoding of $H_0$, the scaling of the computational cost does not severely increase.
[71] Koki Chinzei and Tatsuhiko N. Ikeda. ``Time Crystals Protected by Floquet Dynamical Symmetry in Hubbard Models''. Phys. Rev. Lett. 125, 060601 (2020).
https://doi.org/10.1103/PhysRevLett.125.060601
[72] Jérémie Roland and Nicolas J. Cerf. ``Quantum search by local adiabatic evolution''. Phys. Rev. A 65, 042308 (2002).
https://doi.org/10.1103/PhysRevA.65.042308
[73] Daniel A Lidar, Ali T Rezakhani, and Alioscia Hamma. ``Adiabatic approximation with exponential accuracy for many-body systems and quantum computation''. J. Math. Phys. 50, 102106 (2009).
https://doi.org/10.1063/1.3236685
[74] Nathan Wiebe and Nathan S Babcock. ``Improved error-scaling for adiabatic quantum evolutions''. New J. Phys. 14, 013024 (2012).
https://doi.org/10.1088/1367-2630/14/1/013024
[75] Kianna Wan and Isaac H Kim. ``Fast digital methods for adiabatic state preparation'' (2020). arXiv:2004.04164.
arXiv:2004.04164
[76] Di Fang, Lin Lin, and Yu Tong. ``Time-marching based quantum solvers for time-dependent linear differential equations''. Quantum 7, 955 (2023).
https://doi.org/10.22331/q-2023-03-20-955
[77] Heinz-Peter Breuer, Francesco Petruccione, and School of Pure and Applied Physics Francesco Petruccione. ``The Theory of Open Quantum Systems''. Oxford University Press. (2002).
https://doi.org/10.1093/acprof:oso/9780199213900.001.0001
[78] Angel Rivas and Susana F Huelga. ``Open Quantum Systems''. Springer Berlin Heidelberg. (2012).
https://doi.org/10.1007/978-3-642-23354-8
[79] Derek W Robinson. ``Properties of propagation of quantum spin systems''. ANZIAM J. 19, 387–399 (1976).
https://doi.org/10.1017/S0334270000001260
[80] Bruno Nachtergaele and Robert Sims. ``Lieb-Robinson bounds and the exponential clustering theorem''. Commun. Math. Phys. 265, 119–130 (2006).
https://doi.org/10.1007/s00220-006-1556-1
[81] Bruno Nachtergaele, Yoshiko Ogata, and Robert Sims. ``Propagation of correlations in quantum lattice systems''. J. Stat. Phys. 124, 1 (2006).
https://doi.org/10.1007/s10955-006-9143-6
Cited by
[1] D. Woźniak, B. J. Spisak, M. Kalka, M. Wołoszyn, M. Wleklińska, P. Pigoń, and D. Kołaczek, "Interaction time of Schrödinger cat states with a periodically driven quantum system: Symplectic covariance approach", Physical Review A 110 2, 022416 (2024).
[2] Kaoru Mizuta, "Optimal and nearly optimal simulation of multiperiodic time-dependent Hamiltonians", Physical Review Research 5 3, 033067 (2023).
[3] Tatsuhiko N. Ikeda, Asir Abrar, Isaac L. Chuang, and Sho Sugiura, "Minimum Trotterization Formulas for a Time-Dependent Hamiltonian", Quantum 7, 1168 (2023).
[4] Marco Lewis, Paolo Zuliani, and Sadegh Soudjani, Lecture Notes in Computer Science 14287, 346 (2023) ISBN:978-3-031-43834-9.
[5] Alexander M. Dalzell, Sam McArdle, Mario Berta, Przemyslaw Bienias, Chi-Fang Chen, András Gilyén, Connor T. Hann, Michael J. Kastoryano, Emil T. Khabiboulline, Aleksander Kubica, Grant Salton, Samson Wang, and Fernando G. S. L. Brandão, "Quantum algorithms: A survey of applications and end-to-end complexities", arXiv:2310.03011, (2023).
[6] Yue Wang and Qi Zhao, "Faster Quantum Algorithms with "Fractional''-Truncated Series", arXiv:2402.05595, (2024).
[7] Yu Tanaka and Keisuke Fujii, "A Polynomial Time Quantum Algorithm for Exponentially Large Scale Nonlinear Differential Equations via Hamiltonian Simulation", arXiv:2305.00653, (2023).
[8] Xiao-Ming Zhang, Zixuan Huo, Kecheng Liu, Ying Li, and Xiao Yuan, "Unbiased random circuit compiler for time-dependent Hamiltonian simulation", arXiv:2212.09445, (2022).
The above citations are from Crossref's cited-by service (last updated successfully 2024-09-01 01:22:10) and SAO/NASA ADS (last updated successfully 2024-09-01 01:22:10). 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.