Hybridized Methods for Quantum Simulation in the Interaction Picture

Abhishek Rajput1, Alessandro Roggero2,3, and Nathan Wiebe1,4,5

1Department of Physics, University of Washington, Seattle, WA 98195, USA
2InQubator for Quantum Simulation (IQuS), Department of Physics, University of Washington, Seattle, WA 98195, USA
3Dipartimento di Fisica, University of Trento, via Sommarive 14, I–38123, Povo, Trento, Italy
4Department of Computer Science, University of Toronto, Toronto, ON M5S 2E4, Canada
5Pacific Northwest National Laboratory, Richland, WA 99354, USA

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


Conventional methods of quantum simulation involve trade-offs that limit their applicability to specific contexts where their use is optimal. In particular, the interaction picture simulation has been found to provide substantial asymptotic advantages for some Hamiltonians, but incurs prohibitive constant factors and is incompatible with methods like qubitization. We provide a framework that allows different simulation methods to be hybridized and thereby improve performance for interaction picture simulations over known algorithms. These approaches show asymptotic improvements over the individual methods that comprise them and further make interaction picture simulation methods practical in the near term. Physical applications of these hybridized methods yield a gate complexity scaling as $\log^2 \Lambda$ in the electric cutoff $\Lambda$ for the Schwinger Model and independent of the electron density for collective neutrino oscillations, outperforming the scaling for all current algorithms with these parameters. For the general problem of Hamiltonian simulation subject to dynamical constraints, these methods yield a query complexity independent of the penalty parameter $\lambda$ used to impose an energy cost on time-evolution into an unphysical subspace.

Previous work in quantum simulation algorithms primarily involved developing new algorithms or optimizing existing ones in specific contexts where they could be used. A general framework for combining multiple simulation algorithms to leverage their best features for generic Hamiltonians was lacking. This paper provides one such framework by hybridizing different simulation protocols in the interaction picture and demonstrates asymptotic improvements for these new methods over the individual ones comprising them in certain types of simulation problems. These include an optimal scaling over known algorithms in the energy cutoff $\Lambda$ for the Schwinger model, the electron density for collective neutrino oscillations, and the penalty parameter for the general problem of Hamiltonian simulation subject to dynamical constraints.

► BibTeX data

► References

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

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

[3] Alán Aspuru-Guzik, Anthony D Dutoi, Peter J Love, and Martin Head-Gordon. Simulated quantum computation of molecular energies. Science, 309 (5741): 1704–1707, 2005. 10.1126/​science.1113479.

[4] Markus Reiher, Nathan Wiebe, Krysta M Svore, Dave Wecker, and Matthias Troyer. Elucidating reaction mechanisms on quantum computers. Proceedings of the National Academy of Sciences, 114 (29): 7555–7560, 2017. 10.1073/​pnas.1619152114.

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

[6] Alessandro Roggero, Andy C. Y. Li, Joseph Carlson, Rajan Gupta, and Gabriel N. Perdue. Quantum computing for neutrino-nucleus scattering. Phys. Rev. D, 101: 074038, Apr 2020. 10.1103/​PhysRevD.101.074038.

[7] 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–371, 2007. https:/​/​doi.org/​10.1007/​s00220-006-0150-x.

[8] Nathan Wiebe, Dominic Berry, Peter Høyer, 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.

[9] David Poulin, Angie Qarry, Rolando Somma, and Frank Verstraete. Quantum simulation of time-dependent hamiltonians and the convenient illusion of hilbert space. Physical Review Letters, 106 (17), Apr 2011. ISSN 1079-7114. 10.1103/​physrevlett.106.170501.

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

[11] Guang Hao Low and Isaac L. Chuang. Optimal hamiltonian simulation by quantum signal processing. Phys. Rev. Lett., 118: 010501, Jan 2017. 10.1103/​PhysRevLett.118.010501.

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

[13] András Gilyén, 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–204, 2019. 10.1145/​3313276.3316366.

[14] Dominic W Berry, Mária Kieferová, Artur Scherer, Yuval R Sanders, Guang Hao Low, Nathan Wiebe, Craig Gidney, and Ryan Babbush. Improved techniques for preparing eigenstates of fermionic hamiltonians. npj Quantum Information, 4 (1): 1–7, 2018. 10.1038/​s41534-018-0071-5.

[15] David Poulin, Alexei Kitaev, Damian S Steiger, Matthew B Hastings, and Matthias Troyer. Quantum algorithm for spectral measurement with a lower gate count. Physical review letters, 121 (1): 010501, 2018. 10.1103/​PhysRevLett.121.010501.

[16] John M. Martyn, Zane M. Rossi, Andrew K. Tan, and Isaac L. Chuang. Grand unification of quantum algorithms. PRX Quantum, 2 (4), dec 2021. 10.1103/​prxquantum.2.040203.

[17] Yulong Dong, Xiang Meng, K Birgitta Whaley, and Lin Lin. Efficient phase-factor evaluation in quantum signal processing. Physical Review A, 103 (4): 042419, 2021. 10.1103/​PhysRevA.103.042419.

[18] Andrew M Childs and Nathan Wiebe. Hamiltonian simulation using linear combinations of unitary operations. Quantum Information & Computation, 12 (11-12): 901–924, 2012. 10.26421/​qic12.11-12.

[19] 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–292, 2014. 10.1145/​2591796.2591854.

[20] Mária Kieferová, Artur Scherer, and Dominic W Berry. Simulating the dynamics of time-dependent hamiltonians with a truncated dyson series. Physical Review A, 99 (4): 042314, 2019. 10.1103/​PhysRevA.99.042314.

[21] Guang Hao Low and Nathan Wiebe. Hamiltonian simulation in the interaction picture. arXiv preprint arXiv:1805.00675, 2018. 10.48550/​ARXIV.1805.00675.

[22] Yuan Su, Dominic W Berry, Nathan Wiebe, Nicholas Rubin, and Ryan Babbush. Fault-tolerant quantum simulations of chemistry in first quantization. arXiv preprint arXiv:2105.12767, 2021. URL https:/​/​doi.org/​10.48550/​arXiv.2105.12767.

[23] Earl Campbell. Random compiler for fast hamiltonian simulation. Physical Review Letters, 123 (7), Aug 2019. ISSN 1079-7114. 10.1103/​physrevlett.123.070503. URL http:/​/​dx.doi.org/​10.1103/​PhysRevLett.123.070503.

[24] Dominic W Berry, Andrew M Childs, Yuan Su, Xin Wang, and Nathan Wiebe. Time-dependent hamiltonian simulation with $l1$-norm scaling. Quantum, 4: 254, 2020. 10.22331/​q-2020-04-20-254.

[25] 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. Physical Review X, 8 (4), Oct 2018. ISSN 2160-3308. 10.1103/​physrevx.8.041015. URL http:/​/​dx.doi.org/​10.1103/​PhysRevX.8.041015.

[26] Camille Jordan. Essai sur la géométrie à $n$ dimensions. Bulletin de la Société Mathématique de France, 3: 103–174, 1875. URL http:/​/​eudml.org/​doc/​85325.

[27] Guang Hao Low, Theodore J. Yoder, and Isaac L. Chuang. Methodology of resonant equiangular composite quantum gates. Physical Review X, 6 (4), Dec 2016. ISSN 2160-3308. 10.1103/​physrevx.6.041067. URL http:/​/​dx.doi.org/​10.1103/​PhysRevX.6.041067.

[28] Rui Chao, Dawei Ding, Andras Gilyen, Cupjin Huang, and Mario Szegedy. Finding angles for quantum signal processing with machine precision. arXiv preprint arXiv:2003.02831, 2020. URL https:/​/​doi.org/​10.48550/​arXiv.2003.02831.

[29] Jeongwan Haah. Product decomposition of periodic functions in quantum signal processing. Quantum, 3: 190, 2019. 10.22331/​q-2019-10-07-190.

[30] J. J. Sakurai and Jim Napolitano. Modern Quantum Mechanics. Cambridge University Press, 2 edition, 2017. 10.1017/​9781108499996.

[31] Steven Weinberg. The Quantum Theory of Fields, volume 1. Cambridge University Press, 1995. 10.1017/​CBO9781139644167.

[32] Michael A. Nielsen and Isaac L. Chuang. Quantum Computation and Quantum Information: 10th Anniversary Edition. Cambridge University Press, USA, 10th edition, 2011. ISBN 1107002176.

[33] Dave Wecker, Matthew B Hastings, Nathan Wiebe, Bryan K Clark, Chetan Nayak, and Matthias Troyer. Solving strongly correlated electron models on a quantum computer. Physical Review A, 92 (6): 062318, 2015. 10.1103/​PhysRevA.92.062318.

[34] Julian Schwinger. Gauge invariance and mass. ii. Phys. Rev., 128: 2425–2429, Dec 1962. 10.1103/​PhysRev.128.2425.

[35] Sidney Coleman, R Jackiw, and Leonard Susskind. Charge shielding and quark confinement in the massive schwinger model. Annals of Physics, 93 (1): 267–275, 1975. ISSN 0003-4916. https:/​/​doi.org/​10.1016/​0003-4916(75)90212-2.

[36] M.C. Bañuls, K. Cichy, J.I. Cirac, and K. Jansen. The mass spectrum of the schwinger model with matrix product states. Journal of High Energy Physics, 2013 (11), Nov 2013. ISSN 1029-8479. 10.1007/​jhep11(2013)158. URL http:/​/​dx.doi.org/​10.1007/​JHEP11(2013)158.

[37] T. Pichler, M. Dalmonte, E. Rico, P. Zoller, and S. Montangero. Real-time dynamics in u(1) lattice gauge theories with tensor networks. Phys. Rev. X, 6: 011023, Mar 2016. 10.1103/​PhysRevX.6.011023.

[38] P. Hauke, D. Marcos, M. Dalmonte, and P. Zoller. Quantum simulation of a lattice schwinger model in a chain of trapped ions. Phys. Rev. X, 3: 041018, Nov 2013. 10.1103/​PhysRevX.3.041018.

[39] Esteban A. Martinez, Christine A. Muschik, Philipp Schindler, Daniel Nigg, Alexander Erhard, Markus Heyl, Philipp Hauke, Marcello Dalmonte, Thomas Monz, Peter Zoller, and et al. Real-time dynamics of lattice gauge theories with a few-qubit quantum computer. Nature, 534 (7608): 516–519, Jun 2016. ISSN 1476-4687. 10.1038/​nature18318. URL http:/​/​dx.doi.org/​10.1038/​nature18318.

[40] N. Klco, E. F. Dumitrescu, A. J. McCaskey, T. D. Morris, R. C. Pooser, M. Sanz, E. Solano, P. Lougovski, and M. J. Savage. Quantum-classical computation of schwinger model dynamics using quantum computers. Phys. Rev. A, 98: 032331, Sep 2018. 10.1103/​PhysRevA.98.032331.

[41] John Kogut and Leonard Susskind. Hamiltonian formulation of wilson's lattice gauge theories. Phys. Rev. D, 11: 395–408, Jan 1975. 10.1103/​PhysRevD.11.395.

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

[43] Yuval R. Sanders, Dominic W. Berry, Pedro C.S. Costa, Louis W. Tessler, Nathan Wiebe, Craig Gidney, Hartmut Neven, and Ryan Babbush. Compilation of fault-tolerant quantum heuristics for combinatorial optimization. PRX Quantum, 1 (2), Nov 2020. ISSN 2691-3399. 10.1103/​prxquantum.1.020312. URL http:/​/​dx.doi.org/​10.1103/​PRXQuantum.1.020312.

[44] Yong He, Mingxing Luo, E. Zhang, Hong-Ke Wang, and Xiao-Feng Wang. Decompositions of n-qubit toffoli gates with linear circuit complexity. International Journal of Theoretical Physics, 56, 07 2017. 10.1007/​s10773-017-3389-4.

[45] Johannes Bausch. Fast black-box quantum state preparation, 2020. URL https:/​/​arxiv.org/​abs/​2009.10709. URL https:/​/​doi.org/​10.22331/​q-2022-08-04-773.

[46] Cody Jones. Low-overhead constructions for the fault-tolerant toffoli gate. Physical Review A, 87 (2): 022328, 2013. 10.1103/​PhysRevA.87.022328.

[47] Steven A Cuccaro, Thomas G Draper, Samuel A Kutin, and David Petrie Moulton. A new quantum ripple-carry addition circuit. arXiv preprint quant-ph/​0410184, 2004. URL https:/​/​doi.org/​10.48550/​arXiv.quant-ph/​0410184.

[48] Alexander F. Shaw, Pavel Lougovski, Jesse R. Stryker, and Nathan Wiebe. Quantum algorithms for simulating the lattice schwinger model. Quantum, 4: 306, Aug 2020. ISSN 2521-327X. 10.22331/​q-2020-08-10-306. URL http:/​/​dx.doi.org/​10.22331/​q-2020-08-10-306.

[49] James Pantaleone. Neutrino oscillations at high densities. Physics Letters B, 287 (1): 128 – 132, 1992. ISSN 0370-2693. https:/​/​doi.org/​10.1016/​0370-2693(92)91887-F.

[50] Huaiyu Duan, George M. Fuller, J. Carlson, and Yong-Zhong Qian. Coherent development of neutrino flavor in the supernova environment. Phys. Rev. Lett., 97: 241101, Dec 2006. 10.1103/​PhysRevLett.97.241101.

[51] Huaiyu Duan, George M. Fuller, and Yong-Zhong Qian. Collective neutrino oscillations. Annual Review of Nuclear and Particle Science, 60 (1): 569–594, 2010. 10.1146/​annurev.nucl.012809.104524. URL https:/​/​doi.org/​10.1146/​annurev.nucl.012809.104524.

[52] Sovan Chakraborty, Rasmus Hansen, Ignacio Izaguirre, and Georg Raffelt. Collective neutrino flavor conversion: Recent developments. Nuclear Physics B, 908: 366 – 381, 2016. ISSN 0550-3213. https:/​/​doi.org/​10.1016/​j.nuclphysb.2016.02.012. Neutrino Oscillations: Celebrating the Nobel Prize in Physics 2015.

[53] Ermal Rrapaj. Exact solution of multiangle quantum many-body collective neutrino-flavor oscillations. Phys. Rev. C, 101: 065805, Jun 2020. 10.1103/​PhysRevC.101.065805.

[54] Michael J. Cervia, Amol V. Patwardhan, A. B. Balantekin, S. N. Coppersmith, and Calvin W. Johnson. Entanglement and collective flavor oscillations in a dense neutrino gas. Phys. Rev. D, 100: 083001, Oct 2019. 10.1103/​PhysRevD.100.083001.

[55] Alessandro Roggero. Entanglement and many-body effects in collective neutrino oscillations. Phys. Rev. D, 104: 103016, Nov 2021a. 10.1103/​PhysRevD.104.103016.

[56] Alessandro Roggero. Dynamical phase transitions in models of collective neutrino oscillations. Phys. Rev. D, 104: 123023, Dec 2021b. 10.1103/​PhysRevD.104.123023.

[57] Benjamin Hall, Alessandro Roggero, Alessandro Baroni, and Joseph Carlson. Simulation of collective neutrino oscillations on a quantum computer. Phys. Rev. D, 104: 063009, Sep 2021. 10.1103/​PhysRevD.104.063009.

[58] Kübra Yeter-Aydeniz, Shikha Bangar, George Siopsis, and Raphael C. Pooser. Collective neutrino oscillations on a quantum computer. Quantum Information Processing, 2021. URL https:/​/​doi.org/​10.1007/​s11128-021-03348-x.

[59] Y. Pehlivan, A. B. Balantekin, Toshitaka Kajino, and Takashi Yoshida. Invariants of collective neutrino oscillations. Phys. Rev. D, 84: 065008, Sep 2011. 10.1103/​PhysRevD.84.065008.

[60] 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, Mar 2018. 10.1103/​PhysRevLett.120.110501.

[61] Roberto Oliveira and Barbara M. Terhal. The complexity of quantum spin systems on a two-dimensional square lattice, 2005. URL https:/​/​doi.org/​10.48550/​ARXIV.QUANT-PH/​0504050.

[62] Yudong Cao and Sabre Kais. Efficient optimization of perturbative gadgets, 2017. URL https:/​/​doi.org/​10.48550/​arXiv.1709.02705.

[63] Roger A Horn and Charles R Johnson. Matrix analysis. Cambridge university press, 2012.

[64] Francisco Barahona. On the computational complexity of ising spin glass models. Journal of Physics A: Mathematical and General, 15 (10): 3241, 1982. 10.1088/​0305-4470/​15/​10/​028.

[65] Andrew M Childs, Richard Cleve, Enrico Deotto, Edward Farhi, Sam Gutmann, and Daniel A Spielman. Exponential algorithmic speedup by a quantum walk. In Proceedings of the thirty-fifth annual ACM symposium on Theory of computing, pages 59–68, 2003. 10.1145/​780542.780552.

[66] Jesse R Stryker. Oracles for gauss's law on digital quantum computers. Physical Review A, 99 (4): 042301, 2019. 10.1103/​PhysRevA.99.042301.

[67] Julia Kempe and Oded Regev. 3-local hamiltonian is qma-complete. arXiv preprint quant-ph/​0302079, 2003. URL https:/​/​doi.org/​10.48550/​arXiv.quant-ph/​0302079.

[68] Dorit Aharonov, Wim Van Dam, Julia Kempe, Zeph Landau, Seth Lloyd, and Oded Regev. Adiabatic quantum computation is equivalent to standard quantum computation. SIAM review, 50 (4): 755–787, 2008. 10.1137/​080734479.

[69] Tobias J Osborne. Hamiltonian complexity. Reports on progress in physics, 75 (2): 022001, 2012. 10.1088/​0034-4885/​75/​2/​022001.

[70] Tamara Kohler, Stephen Piddock, Johannes Bausch, and Toby Cubitt. Translationally invariant universal quantum hamiltonians in 1d. In Annales Henri Poincaré, volume 23, pages 223–254. Springer, 2022. 10.1007/​s00023-021-01111-7.

Cited by

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

[2] Christian W. Bauer, Zohreh Davoudi, A. Baha Balantekin, Tanmoy Bhattacharya, Marcela Carena, Wibe A. de Jong, Patrick Draper, Aida El-Khadra, Nate Gemelke, Masanori Hanada, Dmitri Kharzeev, Henry Lamm, Ying-Ying Li, Junyu Liu, Mikhail Lukin, Yannick Meurice, Christopher Monroe, Benjamin Nachman, Guido Pagano, John Preskill, Enrico Rinaldi, Alessandro Roggero, David I. Santiago, Martin J. Savage, Irfan Siddiqi, George Siopsis, David Van Zanten, Nathan Wiebe, Yukari Yamauchi, Kübra Yeter-Aydeniz, and Silvia Zorzetti, "Quantum Simulation for High Energy Physics", arXiv:2204.03381.

[3] Joshua D. Martin, A. Roggero, Huaiyu Duan, J. Carlson, and V. Cirigliano, "Classical and quantum evolution in a simple coherent neutrino problem", Physical Review D 105 8, 083020 (2022).

[4] Nhung H. Nguyen, Minh C. Tran, Yingyue Zhu, Alaina M. Green, C. Huerta Alderete, Zohreh Davoudi, and Norbert M. Linke, "Digital Quantum Simulation of the Schwinger Model and Symmetry Protection with Trapped Ions", arXiv:2112.14262, PRX Quantum 3 2, 020324 (2021).

[5] Abhishek Rajput, Alessandro Roggero, and Nathan Wiebe, "Quantum Error Correction with Gauge Symmetries", arXiv:2112.05186.

[6] Jacob Bringewatt and Zohreh Davoudi, "Parallelization techniques for quantum simulation of fermionic systems", arXiv:2207.12470.

[7] Dong An, Di Fang, and Lin Lin, "Time-dependent Hamiltonian Simulation of Highly Oscillatory Dynamics and Superconvergence for Schrödinger Equation", arXiv:2111.03103.

[8] Valentina Amitrano, Alessandro Roggero, Piero Luchi, Francesco Turro, Luca Vespucci, and Francesco Pederiva, "Trapped-Ion Quantum Simulation of Collective Neutrino Oscillations", arXiv:2207.03189.

[9] Pablo A. M. Casares, Roberto Campos, and M. A. Martin-Delgado, "TFermion: A non-Clifford gate cost assessment library of quantum phase estimation algorithms for quantum chemistry", arXiv:2110.05899.

[10] Zohreh Davoudi, Niklas Mueller, and Connor Powers, "Toward Quantum Computing Phase Diagrams of Gauge Theories with Thermal Pure Quantum States", arXiv:2208.13112.

[11] Yonah Borns-Weil and Di Fang, "Uniform observable error bounds of Trotter formulae for the semiclassical Schrödinger equation", arXiv:2208.07957.

[12] Matthew Hagan and Nathan Wiebe, "Composite Quantum Simulations", arXiv:2206.06409.

The above citations are from Crossref's cited-by service (last updated successfully 2022-10-01 14:56:49) and SAO/NASA ADS (last updated successfully 2022-10-01 14:56:50). The list may be incomplete as not all publishers provide suitable and complete citation data.