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.
 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.
 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.
 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.
 H. Beinert. Iron-sulfur clusters: Nature's modular, multipurpose structures. Science, 277 (5326): 653–659, August 1997. 10.1126/science.277.5326.653.
 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.
 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.
 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.
 Earl Campbell. Random compiler for fast Hamiltonian simulation. Phys. Rev. Lett., 123: 070503, Aug 2019. 10.1103/PhysRevLett.123.070503.
 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.
 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.
 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.
 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.
 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.
 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.
 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.
 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.
 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.
 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.
 G Lindblad. On the generators of quantum dynamical semigroups. Communications in Mathematical Physics, 48 (2): 119–130, 1976. ISSN 0010-3616. 10.1007/BF01608499.
 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.
 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.
 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.
 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.
 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.
 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.
 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.
 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.
 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.
 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.
 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.
 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.
 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.
 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.
 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.
 Daniel Burgarth, Paolo Facchi, Giovanni Gramegna, and Kazuya Yuasa, "One bound to rule them all: from Adiabatic to Zeno", Quantum 6, 737 (2022).
 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).
 David Layden, "First-Order Trotter Error from a Second-Order Perspective", Physical Review Letters 128 21, 210501 (2022).
 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).
 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).
 Lingling Lao and Dan E. Browne, Proceedings of the 49th Annual International Symposium on Computer Architecture 351 (2022) ISBN:9781450386104.
 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).
 Kianna Wan, Mario Berta, and Earl T. Campbell, "Randomized Quantum Algorithm for Statistical Phase Estimation", Physical Review Letters 129 3, 030503 (2022).
 Xiantao Li, "Some error analysis for the quantum phase estimation algorithms", Journal of Physics A: Mathematical and Theoretical 55 32, 325303 (2022).
 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).
 Paul K. Faehrmann, Mark Steudtner, Richard Kueng, Maria Kieferova, and Jens Eisert, "Randomizing multi-product formulas for Hamiltonian simulation", Quantum 6, 806 (2022).
 Leonardo Novo, "Bridging gaps between random approaches to quantum simulation", Quantum Views 4, 33 (2020).
 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).
 Chi-Fang Chen, Hsin-Yuan Huang, Richard Kueng, and Joel A. Tropp, "Concentration for Random Product Formulas", PRX Quantum 2 4, 040305 (2021).
 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).
 Earl T Campbell, "Early fault-tolerant simulations of the Hubbard model", Quantum Science and Technology 7 1, 015007 (2022).
 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).
 Yingkai Ouyang, "Quantum storage in quantum ferromagnets", Physical Review B 103 14, 144417 (2021).
 Andrew M. Childs, Yuan Su, Minh C. Tran, Nathan Wiebe, and Shuchen Zhu, "A Theory of Trotter Error", arXiv:1912.08854.
 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).
 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 2022-12-08 12:07:35) and SAO/NASA ADS (last updated successfully 2022-12-08 12:07:36). 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.