Compilation by stochastic Hamiltonian sparsification
1Department of Physics and Astronomy, University of Sheffield, Sheffield, UK
2Riverlane, Cambridge, UK
| Published: | 2020-02-27, volume 4, page 235 |
| Eprint: | arXiv:1910.06255v2 |
| Doi: | https://doi.org/10.22331/q-2020-02-27-235 |
| Citation: | Quantum 4, 235 (2020). |
Find this paper interesting or want to discuss? Scite or leave a comment on SciRate.
Abstract
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.
https://doi.org/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.
https://doi.org/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.
https://doi.org/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.
https://doi.org/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.
https://doi.org/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.
https://doi.org/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.
https://doi.org/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.
arXiv:1906.07115
[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.
https://doi.org/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.
https://doi.org/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.
https://doi.org/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.
https://doi.org/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.
https://doi.org/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.
https://doi.org/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.
https://doi.org/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.
https://doi.org/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.
https://doi.org/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.
arXiv:1907.13117
[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.
https://doi.org/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.
https://doi.org/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.
arXiv:1902.10673
[22] Ian D. Kivlichan, Christopher E. Granade, and Nathan Wiebe. Phase estimation with randomized Hamiltonians. arXiv:1907.10070, 2019b.
arXiv:1907.10070
[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.
https://doi.org/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.
https://doi.org/10.1007/BF01608499
[25] S. Lloyd. Universal quantum simulators. Science, 273 (5278): 1073–1078, August 1996. 10.1126/science.273.5278.1073.
https://doi.org/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.
https://doi.org/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.
https://doi.org/10.22331/q-2019-07-12-163
[28] Guang Hao Low and Nathan Wiebe. Hamiltonian simulation in the interaction picture. arXiv:1805.00675, 2018.
arXiv:1805.00675
[29] Sam McArdle, Suguru Endo, Alan Aspuru-Guzik, Simon Benjamin, and Xiao Yuan. Quantum computational chemistry. arXiv preprint arXiv:1808.10402, 2018.
arXiv:1808.10402
[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.
arXiv:1710.07629
[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.
arXiv:1909.00028
[32] Jorge Nocedal and Stephen Wright. Numerical optimization. Springer Science & Business Media, 2006. 10.1007/b98874.
https://doi.org/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.
https://doi.org/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.
https://doi.org/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.
https://doi.org/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.
https://doi.org/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.
https://doi.org/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.
https://doi.org/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.
https://doi.org/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.
https://doi.org/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.
arXiv:1910.01155
[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.
https://doi.org/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.
https://doi.org/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.
https://doi.org/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] Zhicheng Zhang, Qisheng Wang, and Mingsheng Ying, "Parallel Quantum Algorithm for Hamiltonian Simulation", Quantum 8, 1228 (2024).
[3] Matthew Hagan and Nathan Wiebe, "Composite Quantum Simulations", Quantum 7, 1181 (2023).
[4] Refik Mansuroglu, Timo Eckstein, Ludwig Nützel, Samuel A Wilkinson, and Michael J Hartmann, "Variational Hamiltonian simulation for translational invariant systems via classical pre-processing", Quantum Science and Technology 8 2, 025006 (2023).
[5] Kaoru Mizuta, Yuya O. Nakagawa, Kosuke Mitarai, and Keisuke Fujii, "Local Variational Quantum Compilation of Large-Scale Hamiltonian Dynamics", PRX Quantum 3 4, 040302 (2022).
[6] Sam McArdle, Suguru Endo, Alán Aspuru-Guzik, Simon C. Benjamin, and Xiao Yuan, "Quantum computational chemistry", Reviews of Modern Physics 92 1, 015003 (2020).
[7] Dominic W. Berry, Andrew M. Childs, Yuan Su, Xin Wang, and Nathan Wiebe, "Time-dependent Hamiltonian simulation withL1-norm scaling", Quantum 4, 254 (2020).
[8] 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).
[9] Ryan Shaffer, Hang Ren, Emiliia Dyrenkova, Christopher G. Yale, Daniel S. Lobser, Ashlyn D. Burch, Matthew N. H. Chow, Melissa C. Revelle, Susan M. Clark, and Hartmut Häffner, "Sample-efficient verification of continuously-parameterized quantum gates for small quantum processors", Quantum 7, 997 (2023).
[10] Yingkai Ouyang, "Quantum storage in quantum ferromagnets", Physical Review B 103 14, 144417 (2021).
[11] Daniel Burgarth, Paolo Facchi, Giovanni Gramegna, and Kazuya Yuasa, "One bound to rule them all: from Adiabatic to Zeno", Quantum 6, 737 (2022).
[12] David Layden, "First-Order Trotter Error from a Second-Order Perspective", Physical Review Letters 128 21, 210501 (2022).
[13] Zhenyu Cai, Ryan Babbush, Simon C. Benjamin, Suguru Endo, William J. Huggins, Ying Li, Jarrod R. McClean, and Thomas E. O’Brien, "Quantum error mitigation", Reviews of Modern Physics 95 4, 045005 (2023).
[14] Richard Meister, Simon C. Benjamin, and Earl T. Campbell, "Tailoring Term Truncations for Electronic Structure Calculations Using a Linear Combination of Unitaries", Quantum 6, 637 (2022).
[15] Yuan Su, Hsin-Yuan Huang, and Earl T. Campbell, "Nearly tight Trotterization of interacting electrons", Quantum 5, 495 (2021).
[16] Jonathan Foldager and Bálint Koczor, "Can shallow quantum circuits scramble local noise into global white noise?", Journal of Physics A: Mathematical and Theoretical 57 1, 015306 (2024).
[17] Lingling Lao and Dan E. Browne, Proceedings of the 49th Annual International Symposium on Computer Architecture 351 (2022) ISBN:9781450386104.
[18] William J. Huggins, Sam McArdle, Thomas E. O’Brien, Joonho Lee, Nicholas C. Rubin, Sergio Boixo, K. Birgitta Whaley, Ryan Babbush, and Jarrod R. McClean, "Virtual Distillation for Quantum Error Mitigation", Physical Review X 11 4, 041036 (2021).
[19] Kianna Wan, Mario Berta, and Earl T. Campbell, "Randomized Quantum Algorithm for Statistical Phase Estimation", Physical Review Letters 129 3, 030503 (2022).
[20] Xiantao Li, "Some error analysis for the quantum phase estimation algorithms", Journal of Physics A: Mathematical and Theoretical 55 32, 325303 (2022).
[21] Matthew Pocrnic, Matthew Hagan, Juan Carrasquilla, Dvira Segal, and Nathan Wiebe, "Composite Qdrift-product formulas for quantum and classical simulations in real and imaginary time", Physical Review Research 6 1, 013224 (2024).
[22] Nicholas H. Stair, Cristian L. Cortes, Robert M. Parrish, Jeffrey Cohn, and Mario Motta, "Stochastic quantum Krylov protocol with double-factorized Hamiltonians", Physical Review A 107 3, 032414 (2023).
[23] Finn Lasse Buessen, Dvira Segal, and Ilia Khait, "Simulating time evolution on distributed quantum computers", Physical Review Research 5 2, L022003 (2023).
[24] 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).
[25] Paul K. Faehrmann, Mark Steudtner, Richard Kueng, Maria Kieferova, and Jens Eisert, "Randomizing multi-product formulas for Hamiltonian simulation", Quantum 6, 806 (2022).
[26] Leonardo Novo, "Bridging gaps between random approaches to quantum simulation", Quantum Views 4, 33 (2020).
[27] Oriel Kiss, Michele Grossi, and Alessandro Roggero, "Importance sampling for stochastic quantum simulations", Quantum 7, 977 (2023).
[28] Almudena Carrera Vazquez, Daniel J. Egger, David Ochsner, and Stefan Woerner, "Well-conditioned multi-product formulas for hardware-friendly Hamiltonian simulation", Quantum 7, 1067 (2023).
[29] Chi-Fang Chen, Hsin-Yuan Huang, Richard Kueng, and Joel A. Tropp, "Concentration for Random Product Formulas", PRX Quantum 2 4, 040305 (2021).
[30] Shi Jin and Xiantao Li, "A Partially Random Trotter Algorithm for Quantum Hamiltonian Simulations", Communications on Applied Mathematics and Computation (2023).
[31] Manuel G. Algaba, Mario Ponce-Martinez, Carlos Munuera-Javaloy, Vicente Pina-Canelles, Manish J. Thapa, Bruno G. Taketani, Martin Leib, Inés de Vega, Jorge Casanova, and Hermanni Heimonen, "Co-Design quantum simulation of nanoscale NMR", Physical Review Research 4 4, 043089 (2022).
[32] Earl T Campbell, "Early fault-tolerant simulations of the Hubbard model", Quantum Science and Technology 7 1, 015007 (2022).
[33] 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).
[34] 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).
[35] Sam McArdle, Suguru Endo, Alan Aspuru-Guzik, Simon Benjamin, and Xiao Yuan, "Quantum computational chemistry", arXiv:1808.10402, (2018).
[36] Andrew M. Childs, Yuan Su, Minh C. Tran, Nathan Wiebe, and Shuchen Zhu, "A Theory of Trotter Error", arXiv:1912.08854, (2019).
[37] 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).
[38] Kunal Sharma and Minh C. Tran, "Hamiltonian Simulation in the Interaction Picture Using the Magnus Expansion", arXiv:2404.02966, (2024).
[39] 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 2024-05-17 14:36:50) and SAO/NASA ADS (last updated successfully 2024-05-17 14:36:51). 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.
Pingback: Perspective in Quantum Views by Leonardo Novo "Bridging gaps between random approaches to quantum simulation"