Quantum Algorithm for Simulating Hamiltonian Dynamics with an Off-diagonal Series Expansion

Amir Kalev1 and Itay Hen2,3

1Information Sciences Institute, University of Southern California, Arlington, VA 22203, USA
2Information Sciences Institute, University of Southern California, Marina del Rey, CA 90292, USA
3Department of Physics and Astronomy, and Center for Quantum Information Science & Technology, University of Southern California, Los Angeles, California 90089, USA

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

Abstract

We propose an efficient quantum algorithm for simulating the dynamics of general Hamiltonian systems. Our technique is based on a power series expansion of the time-evolution operator in its off-diagonal terms. The expansion decouples the dynamics due to the diagonal component of the Hamiltonian from the dynamics generated by its off-diagonal part, which we encode using the linear combination of unitaries technique. Our method has an optimal dependence on the desired precision and, as we illustrate, generally requires considerably fewer resources than the current state-of-the-art. We provide an analysis of resource costs for several sample models.

Simulating the dynamics of quantum many-body systems is a central challenge in Physics, Chemistry and the Material Sciences as well as in other areas of science and technology. While for classical algorithms this task is in general intractable, quantum circuits offer a way around the classical bottlenecks by way of `circuitizing' the time evolution of the system in question. However, present-day quantum computing devices allow for the programming of only small and noisy quantum circuits, a state of matters that places severe constraints on the types of applications these devices may be used for in practice. The qubit and gate costs of circuitization procedures have therefore rightfully become key factors in determining the feasibility of any potential application and increasingly more efficient algorithms are continuously being devised. We propose a novel approach to resource-efficient Hamiltonian dynamics simulations on quantum circuits that we argue offers certain advantages, which directly translate to a shorter algorithm runtime, over state-of-the-art quantum simulation algorithms. We accomplish this by utilizing a series expansion of the quantum time-evolution operator in its off-diagonal elements wherein the operator is expanded around its diagonal component. This expansion allows one to effectively integrate out the diagonal component of the evolution, thereby reducing the overall gate and qubit complexities of the algorithm as compared to existing methods.

► BibTeX data

► References

[1] D. W. Berry, A. M. Childs, R. Cleve, R. Kothari, and R. D. Somma. Simulating hamiltonian dynamics with a truncated taylor series. Phys. Rev. Lett., 114: 090502, Mar 2015. https:/​/​doi.org/​10.1103/​PhysRevLett.114.090502.
https:/​/​doi.org/​10.1103/​PhysRevLett.114.090502

[2] G. Hao Low and N. Wiebe. Hamiltonian Simulation in the Interaction Picture. arXiv e-prints, art. arXiv:1805.00675, May 2018.
arXiv:1805.00675

[3] T. Albash, G. Wagenbreth, and I. Hen. Off-diagonal expansion quantum monte carlo. Phys. Rev. E, 96: 063309, Dec 2017. https:/​/​doi.org/​10.1103/​PhysRevE.96.063309.
https:/​/​doi.org/​10.1103/​PhysRevE.96.063309

[4] I. Hen. Off-diagonal series expansion for quantum partition functions. Journal of Statistical Mechanics: Theory and Experiment, 2018 (5): 053102, 2018. https:/​/​doi.org/​10.1088/​1742-5468/​aabbe4.
https:/​/​doi.org/​10.1088/​1742-5468/​aabbe4

[5] L. Gupta, T. Albash, and I. Hen. Permutation matrix representation quantum monte carlo. Journal of Statistical Mechanics: Theory and Experiment, 2020 (7): 073105, jul 2020a. https:/​/​doi.org/​10.1088/​1742-5468/​ab9e64.
https:/​/​doi.org/​10.1088/​1742-5468/​ab9e64

[6] Y.-H. Chen, A. Kalev, and I. Hen. A quantum algorithm for time-dependent Hamiltonian simulation by permutation expansion. arXiv e-prints, art. arXiv:2103.15334, March 2021.
arXiv:2103.15334

[7] E. T. Whittaker and G. Robinson. Divided differences. In The Calculus of Observations: A Treatise on Numerical Mathematics. New York: Dover, New York, 1967.

[8] C. de Boor. Divided differences. Surveys in Approximation Theory, 1: 46–69, 2005. https:/​​/​​arxiv.org/​​abs/​​math/​​0502036.
https:/​​/​​arxiv.org/​​abs/​​math/​​0502036

[9] M. A. Nielsen and I. L. Chuang. Quantum Computation and Quantum Information. Cambridge University Press, USA, 10th edition, 2011. ISBN 1107002176.

[10] R. M. Corless, G. H. Gonnet, D. E. G. Hare, D. J. Jeffrey, and D. E. Knuth. On the lambertw function. Advances in Computational Mathematics, 5 (1): 329–359, Dec 1996. ISSN 1572-9044. https:/​/​doi.org/​10.1007/​BF02124750.
https:/​/​doi.org/​10.1007/​BF02124750

[11] V. V. Shende, S. S. Bullock, and I. L. Markov. Synthesis of quantum-logic circuits. IEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems, 25 (6): 1000–1010, 2006. https:/​/​doi.org/​10.1109/​TCAD.2005.855930.
https:/​/​doi.org/​10.1109/​TCAD.2005.855930

[12] A. Barenco, C. H. Bennett, R. Cleve, D. P. DiVincenzo, N. Margolus, P. Shor, T. Sleator, J. A. Smolin, and H. Weinfurter. Elementary gates for quantum computation. Phys. Rev. A, 52: 3457–3467, Nov 1995. https:/​/​doi.org/​10.1103/​PhysRevA.52.3457.
https:/​/​doi.org/​10.1103/​PhysRevA.52.3457

[13] A. Kalev and I. Hen. An integral-free representation of the Dyson series using divided differences. arXiv e-prints, art. arXiv:2010.09888, October 2020.
arXiv:2010.09888

[14] J. Hubbard and B. H. Flowers. Electron correlations in narrow energy bands. Proceedings of the Royal Society of London. Series A. Mathematical and Physical Sciences, 276 (1365): 238–257, 1963. https:/​/​doi.org/​10.1098/​rspa.1963.0204.
https:/​/​doi.org/​10.1098/​rspa.1963.0204

[15] A. Tranter, P. J. Love, F. Mintert, and P. V. Coveney. A comparison of the bravyi-kitaev and jordan-wigner transformations for the quantum simulation of quantum chemistry. Journal of chemical theory and computation, 14 (11): 5617–5630, 11 2018. https:/​/​doi.org/​10.1021/​acs.jctc.8b00450.
https:/​/​doi.org/​10.1021/​acs.jctc.8b00450

[16] S. B. Bravyi and A. Yu. Kitaev. Fermionic quantum computation. Annals of Physics, 298 (1): 210 – 226, 2002. ISSN 0003-4916. https:/​/​doi.org/​10.1006/​aphy.2002.6254.
https:/​/​doi.org/​10.1006/​aphy.2002.6254

[17] F. Verstraete and J. I. Cirac. Mapping local hamiltonians of fermions to local hamiltonians of spins. Journal of Statistical Mechanics: Theory and Experiment, 2005 (09): P09012–P09012, sep 2005. https:/​/​doi.org/​10.1088/​1742-5468/​2005/​09/​p09012.
https:/​/​doi.org/​10.1088/​1742-5468/​2005/​09/​p09012

[18] C. Derby and J. Klassen. A Compact Fermion to Qubit Mapping. arXiv e-prints, art. arXiv:2003.06939, March 2020.
arXiv:2003.06939

[19] R. Babbush, N. Wiebe, J. McClean, J. McClain, H. Neven, and G. K.-L. Chan. Low-depth quantum simulation of materials. Phys. Rev. X, 8: 011044, Mar 2018. https:/​/​doi.org/​10.1103/​PhysRevX.8.011044.
https:/​/​doi.org/​10.1103/​PhysRevX.8.011044

[20] J. Schwinger. Gauge invariance and mass. ii. Phys. Rev., 128: 2425–2429, Dec 1962. https:/​/​doi.org/​10.1103/​PhysRev.128.2425.
https:/​/​doi.org/​10.1103/​PhysRev.128.2425

[21] Z. Davoudi, M. Hafezi, C. Monroe, G. Pagano, A. Seif, and A. Shaw. Towards analog quantum simulations of lattice gauge theories with trapped ions. Phys. Rev. Research, 2: 023015, Apr 2020. https:/​/​doi.org/​10.1103/​PhysRevResearch.2.023015.
https:/​/​doi.org/​10.1103/​PhysRevResearch.2.023015

[22] J. Kogut and L. Susskind. Hamiltonian formulation of wilson's lattice gauge theories. Phys. Rev. D, 11: 395–408, Jan 1975. https:/​/​doi.org/​10.1103/​PhysRevD.11.395.
https:/​/​doi.org/​10.1103/​PhysRevD.11.395

[23] T. Banks, L. Susskind, and J. Kogut. Strong-coupling calculations of lattice gauge theories: (1 + 1)-dimensional exercises. Phys. Rev. D, 13: 1043–1053, Feb 1976. https:/​/​doi.org/​10.1103/​PhysRevD.13.1043.
https:/​/​doi.org/​10.1103/​PhysRevD.13.1043

[24] E. Rieffel and W. Polak. Quantum Computing: A Gentle Introduction. MIT Press, Cambridge, MA, 2011.

[25] L. Gupta, L. Barash, and I. Hen. Calculating the divided differences of the exponential function by addition and removal of inputs. Computer Physics Communications, 254: 107385, 2020b. ISSN 0010-4655. https:/​/​doi.org/​10.1016/​j.cpc.2020.107385.
https:/​/​doi.org/​10.1016/​j.cpc.2020.107385

[26] T. Häner, M. Roetteler, and K. M. Svore. Optimizing Quantum Circuits for Arithmetic. arXiv e-prints, art. arXiv:1805.12445, May 2018.
arXiv:1805.12445

Cited by

[1] William M. Kirby, Sultana Hadi, Michael Kreshchuk, and Peter J. Love, "Quantum simulation of second-quantized Hamiltonians in compact encoding", Physical Review A 104 4, 042607 (2021).

[2] Yi-Hsiang Chen, Amir Kalev, and Itay Hen, "Quantum Algorithm for Time-Dependent Hamiltonian Simulation by Permutation Expansion", PRX Quantum 2 3, 030342 (2021).

[3] Zohreh Davoudi, Norbert M. Linke, and Guido Pagano, "Toward simulating quantum field theories with controlled phonon-ion dynamics: A hybrid analog-digital approach", arXiv:2104.09346.

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

[5] Amir Kalev and Itay Hen, "An integral-free representation of the Dyson series using divided differences", arXiv:2010.09888.

[6] Daan Camps, Efekan Kökcü, Lindsay Bassman, Wibe A. de Jong, Alexander F. Kemper, and Roel Van Beeumen, "An Algebraic Quantum Circuit Compression Algorithm for Hamiltonian Simulation", arXiv:2108.03283.

[7] Efekan Kökcü, Daan Camps, Lindsay Bassman, James K. Freericks, Wibe A. de Jong, Roel Van Beeumen, and Alexander F. Kemper, "Algebraic Compression of Quantum Circuits for Hamiltonian Evolution", arXiv:2108.03282.

[8] Kyle Sherbert, Frank Cerasoli, and Marco Buongiorno Nardelli, "A systematic variational approach to band theory in a quantum computer", arXiv:2104.03409.

The above citations are from Crossref's cited-by service (last updated successfully 2021-10-22 08:27:31) and SAO/NASA ADS (last updated successfully 2021-10-22 08:27:32). The list may be incomplete as not all publishers provide suitable and complete citation data.