Compilation by stochastic Hamiltonian sparsification

Yingkai Ouyang1, David R. White1, and Earl T. Campbell1,2

1Department of Physics and Astronomy, University of Sheffield, Sheffield, UK
2Riverlane, Cambridge, UK

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


Simulation of quantum chemistry is expected to be a principal application of quantum computing. In quantum simulation, a complicated Hamiltonian describing the dynamics of a quantum system is decomposed into its constituent terms, where the effect of each term during time-evolution is individually computed. For many physical systems, the Hamiltonian has a large number of terms, constraining the scalability of established simulation methods. To address this limitation we introduce a new scheme that approximates the actual Hamiltonian with a sparser Hamiltonian containing fewer terms. By stochastically sparsifying weaker Hamiltonian terms, we benefit from a quadratic suppression of errors relative to deterministic approaches. Relying on optimality conditions from convex optimisation theory, we derive an appropriate probability distribution for the weaker Hamiltonian terms, and compare its error bounds with other probability ansatzes for some electronic structure Hamiltonians. Tuning the sparsity of our approximate Hamiltonians allows our scheme to interpolate between two recent random compilers: qDRIFT and randomized first order Trotter. Our scheme is thus an algorithm that combines the strengths of randomised Trotterisation with the efficiency of qDRIFT, and for intermediate gate budgets, outperforms both of these prior methods.

► BibTeX data

► References

[1] A. Aspuru-Guzik. Simulated quantum computation of molecular energies. Science, 309 (5741): 1704–1707, September 2005. 10.1126/​science.1113479.

[2] Ryan Babbush, Jarrod McClean, Dave Wecker, Alán Aspuru-Guzik, and Nathan Wiebe. Chemical basis of Trotter-Suzuki errors in quantum chemistry simulation. Phys. Rev. A, 91: 022311, Feb 2015. 10.1103/​PhysRevA.91.022311.

[3] 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, Oct 2018a. 10.1103/​PhysRevX.8.041015.

[4] 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, Mar 2018b. 10.1103/​PhysRevX.8.011044.

[5] H. Beinert. Iron-sulfur clusters: Nature's modular, multipurpose structures. Science, 277 (5326): 653–659, August 1997. 10.1126/​science.277.5326.653.

[6] Dominic W Berry. A random approach to quantum simulation. Physics, 12: 91, 2019. 10.1103/​physics.12.91.

[7] 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, 2017. 10.1017/​fms.2017.2.

[8] Dominic W Berry, Andrew M Childs, Yuan Su, Xin Wang, and Nathan Wiebe. Time-dependent Hamiltonian simulation with ${L}^{1}$-norm scaling. arXiv preprint arXiv:1906.07115, 2019a.

[9] Dominic W. Berry, Craig Gidney, Mario Motta, Jarrod R. McClean, and Ryan Babbush. Qubitization of Arbitrary Basis Quantum Chemistry Leveraging Sparsity and Low Rank Factorization. Quantum, 3: 208, December 2019b. ISSN 2521-327X. 10.22331/​q-2019-12-02-208.

[10] Sergey Bravyi and Jeongwan Haah. Quantum Self-Correction in the 3D Cubic Code Model. Phys. Rev. Lett., 111 (20): 200501, November 2013. 10.1103/​PhysRevLett.111.200501.

[11] Earl Campbell. Shorter gate sequences for quantum computing by mixing unitaries. Phys. Rev. A, 95: 042306, Apr 2017. 10.1103/​PhysRevA.95.042306.

[12] Earl Campbell. Random compiler for fast Hamiltonian simulation. Phys. Rev. Lett., 123: 070503, Aug 2019. 10.1103/​PhysRevLett.123.070503.

[13] Andrew M. Childs and Dominic W. Berry. Black-box Hamiltonian simulation and unitary implementation. Quantum Information and Computation, 12 (1-2), 2012. 10.26421/​qic12.1-2.

[14] Andrew M. Childs, Dmitri Maslov, Yunseong Nam, Neil J. Ross, and Yuan Su. Toward the first quantum simulation with quantum speedup. Proceedings of the National Academy of Sciences, 115 (38): 9456–9461, 2018. ISSN 0027-8424. 10.1073/​pnas.1801723115.

[15] Andrew M. Childs, Aaron Ostrander, and Yuan Su. Faster quantum simulation by randomization. Quantum, 3: 182, September 2019. 10.22331/​q-2019-09-02-182.

[16] Matthew B. Hastings. Turning gate synthesis errors into incoherent errors. Quantum Info. Comput., 17 (5-6): 488–494, March 2017. ISSN 1533-7146. 10.26421/​QIC17.5-6.

[17] Cornelius Hempel, Christine Maier, Jonathan Romero, Jarrod McClean, Thomas Monz, Heng Shen, Petar Jurcevic, Ben P. Lanyon, Peter Love, Ryan Babbush, Alán Aspuru-Guzik, Rainer Blatt, and Christian F. Roos. Quantum chemistry calculations on a trapped-ion quantum simulator. Phys. Rev. X, 8: 031022, Jul 2018. 10.1103/​PhysRevX.8.031022.

[18] William J. Huggins, Jarrod McClean, Nicholas Rubin, Zhang Jiang, Nathan Wiebe, K. Birgitta Whaley, and Ryan Babbush. Efficient and noise resilient measurements for quantum chemistry on near-term quantum computers. arXiv:1907.13117, 2019.

[19] Alexei Yu Kitaev, Alexander Shen, Mikhail N Vyalyi, and Mikhail N Vyalyi. Classical and quantum computation. Number 47. American Mathematical Soc., 2002. 10.1090/​gsm/​047.

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

[21] Ian D. Kivlichan, Craig Gidney, Dominic W. Berry, Nathan Wiebe, Jarrod McClean, Wei Sun, Zhang Jiang, Nicholas Rubin, Austin Fowler, Alán Aspuru-Guzik, Hartmut Neven, and Ryan Babbush. Improved fault-tolerant quantum simulation of condensed-phase correlated electrons via Trotterization. arXiv:1902.10673, 2019a.

[22] Ian D. Kivlichan, Christopher E. Granade, and Nathan Wiebe. Phase estimation with randomized Hamiltonians. arXiv:1907.10070, 2019b.

[23] Zhaokai Li, Xiaomei Liu, Hefeng Wang, Sahel Ashhab, Jiangyu Cui, Hongwei Chen, Xinhua Peng, and Jiangfeng Du. Quantum simulation of resonant transitions for solving the eigenproblem of an effective water Hamiltonian. Phys. Rev. Lett., 122: 090504, Mar 2019. 10.1103/​PhysRevLett.122.090504.

[24] G Lindblad. On the generators of quantum dynamical semigroups. Communications in Mathematical Physics, 48 (2): 119–130, 1976. ISSN 0010-3616. 10.1007/​BF01608499.

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

[26] Guang Hao Low and Isaac L. Chuang. Optimal Hamiltonian simulation by quantum signal processing. Physical Review Letters, 118 (1), January 2017. 10.1103/​physrevlett.118.010501.

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

[28] Guang Hao Low and Nathan Wiebe. Hamiltonian simulation in the interaction picture. arXiv:1805.00675, 2018.

[29] Sam McArdle, Suguru Endo, Alan Aspuru-Guzik, Simon Benjamin, and Xiao Yuan. Quantum computational chemistry. arXiv preprint arXiv:1808.10402, 2018.

[30] Jarrod R McClean, Ian D Kivlichan, Kevin J Sung, Damian S Steiger, Yudong Cao, Chengyu Dai, E Schuyler Fried, Craig Gidney, Brendan Gimby, Pranav Gokhale, et al. OpenFermion: the electronic structure package for quantum computers. arXiv preprint arXiv:1710.07629, 2017.

[31] Jarrod R. McClean, Fabian M. Faulstich, Qinyi Zhu, Bryan O'Gorman, Yiheng Qiu, Steven R. White, Ryan Babbush, and Lin Lin. Discontinuous Galerkin discretization for quantum simulation of chemistry. arXiv:1909.00028, 2019.

[32] Jorge Nocedal and Stephen Wright. Numerical optimization. Springer Science & Business Media, 2006. 10.1007/​b98874.

[33] P. J. J. O'Malley, R. Babbush, I. D. Kivlichan, J. Romero, J. R. McClean, R. Barends, J. Kelly, P. Roushan, A. Tranter, N. Ding, B. Campbell, Y. Chen, Z. Chen, B. Chiaro, A. Dunsworth, A. G. Fowler, E. Jeffrey, E. Lucero, A. Megrant, J. Y. Mutus, M. Neeley, C. Neill, C. Quintana, D. Sank, A. Vainsencher, J. Wenner, T. C. White, P. V. Coveney, P. J. Love, H. Neven, A. Aspuru-Guzik, and J. M. Martinis. Scalable quantum simulation of molecular energies. Phys. Rev. X, 6: 031007, Jul 2016. 10.1103/​PhysRevX.6.031007.

[34] David Poulin, M. B. Hastings, D. Wecker, N. Wiebe, Andrew C. Doberty, and M. Troyer. The Trotter step size required for accurate quantum simulation of quantum chemistry. Quantum Information & Computation, 15 (5-6): 0361–0384, 2015. 10.26421/​qic15.5-6.

[35] 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, July 2017. 10.1073/​pnas.1619152114.

[36] Kanav Setia and James D. Whitfield. Bravyi-Kitaev superfast simulation of electronic structure on a quantum computer. The Journal of Chemical Physics, 148 (16): 164104, April 2018. 10.1063/​1.5019371.

[37] Rolando D. Somma. A Trotter-Suzuki approximation for lie groups with applications to Hamiltonian simulation. Journal of Mathematical Physics, 57 (6): 062202, June 2016. 10.1063/​1.4952761.

[38] Masuo Suzuki. Generalized Trotter's formula and systematic approximants of exponential operators and inner derivations with applications to many-body problems. Comm. Math. Phys., 51 (2): 183–190, 1976. 10.1007/​bf01609348.

[39] Masuo Suzuki. Fractal decomposition of exponential operators with applications to many-body theories and Monte Carlo simulations. Physics Letters A, 146 (6): 319–323, June 1990. 10.1016/​0375-9601(90)90962-n.

[40] Masuo Suzuki. General theory of fractal path integrals with applications to many-body theories and statistical physics. Journal of Mathematical Physics, 32 (2): 400–407, February 1991. 10.1063/​1.529425.

[41] Ryan Sweke, Frederik Wilde, Johannes Meyer, Maria Schuld, Paul K Fährmann, Barthélémy Meynard-Piganeau, and Jens Eisert. Stochastic gradient descent for hybrid quantum-classical optimization. arXiv preprint arXiv:1910.01155, 2019.

[42] Dave Wecker, Bela Bauer, Bryan K. Clark, Matthew B. Hastings, and Matthias Troyer. Gate-count estimates for performing quantum chemistry on small quantum computers. Phys. Rev. A, 90: 022305, Aug 2014a. 10.1103/​PhysRevA.90.022305.

[43] Dave Wecker, Bela Bauer, Bryan K. Clark, Matthew B. Hastings, and Matthias Troyer. Gate-count estimates for performing quantum chemistry on small quantum computers. Phys. Rev. A, 90: 022305, Aug 2014b. 10.1103/​PhysRevA.90.022305.

[44] James D. Whitfield, Jacob Biamonte, and Alán Aspuru-Guzik. Simulation of electronic structure Hamiltonians using quantum computers. Molecular Physics, 109 (5): 735–750, March 2011. 10.1080/​00268976.2011.552441.

Cited by

[1] Yi-Tong Zou, Yu-Jiao Bo, and Ji-Chong Yang, "Optimize quantum simulation using a force-gradient integrator", EPL (Europhysics Letters) 135 1, 10004 (2021).

[2] Emiel Koridon, Saad Yalouz, Bruno Senjean, Francesco Buda, Thomas E. O'Brien, and Lucas Visscher, "Orbital transformations to reduce the 1-norm of the electronic structure Hamiltonian for quantum computing applications", Physical Review Research 3 3, 033127 (2021).

[3] Dominic W. Berry, Andrew M. Childs, Yuan Su, Xin Wang, and Nathan Wiebe, "Time-dependent Hamiltonian simulation withL1-norm scaling", arXiv:1906.07115, Quantum 4, 254 (2020).

[4] Leonardo Novo, "Bridging gaps between random approaches to quantum simulation", Quantum Views 4, 33 (2020).

[5] Vincent E. Elfving, Marta Millaruelo, José A. Gámez, and Christian Gogolin, "Simulating quantum chemistry in the seniority-zero space on qubit-based quantum computers", Physical Review A 103 3, 032605 (2021).

[6] Yuan Su, Hsin-Yuan Huang, and Earl T. Campbell, "Nearly tight Trotterization of interacting electrons", arXiv:2012.09194, Quantum 5, 495 (2021).

[7] Sam McArdle, Suguru Endo, Alán Aspuru-Guzik, Simon C. Benjamin, and Xiao Yuan, "Quantum computational chemistry", arXiv:1808.10402, Reviews of Modern Physics 92 1, 015003 (2020).

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

[9] Yingkai Ouyang, "Quantum storage in quantum ferromagnets", Physical Review B 103 14, 144417 (2021).

[10] Andrew M. Childs, Yuan Su, Minh C. Tran, Nathan Wiebe, and Shuchen Zhu, "A Theory of Trotter Error", arXiv:1912.08854.

[11] Hrant Gharibyan, Masanori Hanada, Masazumi Honda, and Junyu Liu, "Toward simulating superstring/M-theory on a quantum computer", Journal of High Energy Physics 2021 7, 140 (2021).

[12] Sam McArdle, "Learning from Physics Experiments with Quantum Computers: Applications in Muon Spectroscopy", PRX Quantum 2 2, 020349 (2021).

The above citations are from Crossref's cited-by service (last updated successfully 2021-09-23 13:12:58) and SAO/NASA ADS (last updated successfully 2021-09-23 13:13:00). The list may be incomplete as not all publishers provide suitable and complete citation data.

1 thought on “Compilation by stochastic Hamiltonian sparsification

  1. Pingback: Perspective in Quantum Views by Leonardo Novo "Bridging gaps between random approaches to quantum simulation"