Computing Ground State Properties with Early Fault-Tolerant Quantum Computers

Ruizhe Zhang1, Guoming Wang2, and Peter Johnson2

1Department of Computer Science, The University of Texas at Austin, Austin, TX 78712, USA.
2Zapata Computing Inc., Boston, MA 02110, USA.

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


Significant effort in applied quantum computing has been devoted to the problem of ground state energy estimation for molecules and materials. Yet, for many applications of practical value, additional properties of the ground state must be estimated. These include Green's functions used to compute electron transport in materials and the one-particle reduced density matrices used to compute electric dipoles of molecules. In this paper, we propose a quantum-classical hybrid algorithm to efficiently estimate such ground state properties with high accuracy using low-depth quantum circuits. We provide an analysis of various costs (circuit repetitions, maximal evolution time, and expected total runtime) as a function of target accuracy, spectral gap, and initial ground state overlap. This algorithm suggests a concrete approach to using early fault tolerant quantum computers for carrying out industry-relevant molecular and materials calculations.

Previously, there was no known way to use a near-term quantum computer to reliably compute many useful properties of quantum materials or molecules. Existing methods were either not reliable or not possible with a near-term quantum computer. This paper proposes a reliable, near-term method for computing useful properties beyond just the ground state energy of a Hamiltonian. Major applications of this work include the design of materials and molecules and solving linear systems of equations.

► BibTeX data

► References

[1] Yudong Cao, Jhonathan Romero, and Alán Aspuru-Guzik. ``Potential of quantum computing for drug discovery''. IBM Journal of Research and Development 62, 6–1 (2018).

[2] Yudong Cao, Jonathan Romero, Jonathan P Olson, Matthias Degroote, Peter D Johnson, Mária Kieferová, Ian D Kivlichan, Tim Menke, Borja Peropadre, Nicolas PD Sawaya, et al. ``Quantum chemistry in the age of quantum computing''. Chemical reviews 119, 10856–10915 (2019).

[3] Alán Aspuru-Guzik, Anthony D Dutoi, Peter J Love, and Martin Head-Gordon. ``Simulated quantum computation of molecular energies''. Science 309, 1704–1707 (2005).

[4] Alberto Peruzzo, Jarrod McClean, Peter Shadbolt, Man-Hong Yung, Xiao-Qi Zhou, Peter J Love, Alán Aspuru-Guzik, and Jeremy L O’brien. ``A variational eigenvalue solver on a photonic quantum processor''. Nature communications 5, 1–7 (2014).

[5] Yigal Meir and Ned S Wingreen. ``Landauer formula for the current through an interacting electron region''. Physical review letters 68, 2512 (1992).

[6] Frank Jensen. ``Introduction to computational chemistry''. John Wiley & Sons. (2017).

[7] Thomas E O’Brien, Bruno Senjean, Ramiro Sagastizabal, Xavier Bonet-Monroig, Alicja Dutkiewicz, Francesco Buda, Leonardo DiCarlo, and Lucas Visscher. ``Calculating energy derivatives for quantum chemistry on a quantum computer''. npj Quantum Information 5, 1–12 (2019).

[8] Andris Ambainis. ``On physical problems that are slightly more difficult than qma''. In 2014 IEEE 29th Conference on Computational Complexity (CCC). Pages 32–43. (2014).

[9] Sevag Gharibian and Justin Yirka. ``The complexity of simulating local measurements on quantum systems''. Quantum 3, 189 (2019).

[10] Sevag Gharibian, Stephen Piddock, and Justin Yirka. ``Oracle Complexity Classes and Local Measurements on Physical Hamiltonians''. In Christophe Paul and Markus Bläser, editors, 37th International Symposium on Theoretical Aspects of Computer Science (STACS 2020). Volume 154 of Leibniz International Proceedings in Informatics (LIPIcs), pages 20:1–20:37. Dagstuhl, Germany (2020). Schloss Dagstuhl–Leibniz-Zentrum für Informatik.

[11] David Poulin and Pawel Wocjan. ``Preparing ground states of quantum many-body systems on a quantum computer''. Physical review letters 102, 130503 (2009).

[12] Yimin Ge, Jordi Tura, and J Ignacio Cirac. ``Faster ground state preparation and high-precision ground energy estimation with fewer qubits''. Journal of Mathematical Physics 60, 022202 (2019).

[13] Lin Lin and Yu Tong. ``Near-optimal ground state preparation''. Quantum 4, 372 (2020).

[14] Sam McArdle, Alexander Mayorov, Xiao Shan, Simon Benjamin, and Xiao Yuan. ``Digital quantum simulation of molecular vibrations''. Chemical science 10, 5725–5735 (2019).

[15] Jérôme F. Gonthier, Maxwell D. Radin, Corneliu Buda, Eric J. Doskocil, Clena M. Abuan, and Jhonathan Romero. ``Identifying challenges towards practical quantum advantage through resource estimation: the measurement roadblock in the variational quantum eigensolver'' (2020). arXiv:2012.04001.

[16] Guoming Wang, Dax Enshan Koh, Peter D Johnson, and Yudong Cao. ``Minimizing estimation runtime on noisy quantum computers''. PRX Quantum 2, 010346 (2021).

[17] Ryan Babbush, Jarrod R McClean, Michael Newman, Craig Gidney, Sergio Boixo, and Hartmut Neven. ``Focus beyond quadratic speedups for error-corrected quantum advantage''. PRX Quantum 2, 010103 (2021).

[18] Kyle EC Booth, Bryan O'Gorman, Jeffrey Marshall, Stuart Hadfield, and Eleanor Rieffel. ``Quantum-accelerated constraint programming''. Quantum 5, 550 (2021).

[19] Earl T Campbell. ``Early fault-tolerant simulations of the hubbard model''. Quantum Science and Technology 7, 015007 (2021).

[20] Lin Lin and Yu Tong. ``Heisenberg-limited ground-state energy estimation for early fault-tolerant quantum computers''. PRX Quantum 3, 010318 (2022).

[21] David Layden. ``First-order trotter error from a second-order perspective''. Phys. Rev. Lett. 128, 210501 (2022).

[22] Rolando D Somma. ``Quantum eigenvalue estimation via time series analysis''. New Journal of Physics 21, 123025 (2019).

[23] Laura Clinton, Johannes Bausch, Joel Klassen, and Toby Cubitt. ``Phase estimation of local hamiltonians on nisq hardware'' (2021). arXiv:2110.13584.

[24] Patrick Rall. ``Faster coherent quantum algorithms for phase, energy, and amplitude estimation''. Quantum 5, 566 (2021).

[25] Dominic W Berry, Andrew M Childs, Richard Cleve, Robin Kothari, and Rolando D Somma. ``Simulating hamiltonian dynamics with a truncated taylor series''. Physical review letters 114, 090502 (2015). url:​10.1103/​PhysRevLett.114.090502.

[26] Guang Hao Low and Isaac L Chuang. ``Optimal hamiltonian simulation by quantum signal processing''. Physical review letters 118, 010501 (2017).

[27] 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, 9456–9461 (2018).

[28] Guang Hao Low and Isaac L Chuang. ``Hamiltonian simulation by qubitization''. Quantum 3, 163 (2019).

[29] Emanuel Knill, Gerardo Ortiz, and Rolando D Somma. ``Optimal quantum measurements of expectation values of observables''. Physical Review A 75, 012328 (2007).

[30] James D. Watson, Johannes Bausch, and Sevag Gharibian. ``The complexity of translationally invariant problems beyond ground state energies'' (2020). arXiv:2012.12717.

[31] Alberto Peruzzo, Jarrod McClean, Peter Shadbolt, Man-Hong Yung, Xiao-Qi Zhou, Peter J Love, Alán Aspuru-Guzik, and Jeremy L O’brien. ``A variational eigenvalue solver on a photonic quantum processor''. Nature communications 5, 1–7 (2014).

[32] Jarrod R McClean, Jonathan Romero, Ryan Babbush, and Alán Aspuru-Guzik. ``The theory of variational hybrid quantum-classical algorithms''. New Journal of Physics 18, 023023 (2016).

[33] Attila Szabo and Neil S Ostlund. ``Modern quantum chemistry: introduction to advanced electronic structure theory''. Courier Corporation. (2012).

[34] Sevag Gharibian and François Le Gall. ``Dequantizing the quantum singular value transformation: Hardness and applications to quantum chemistry and the quantum pcp conjecture''. In Proceedings of the 54th Annual ACM SIGACT Symposium on Theory of Computing. Pages 19–32. (2022).

[35] Shantanav Chakraborty, András Gilyén, and Stacey Jeffery. ``The Power of Block-Encoded Matrix Powers: Improved Regression Techniques via Faster Hamiltonian Simulation''. In Christel Baier, Ioannis Chatzigiannakis, Paola Flocchini, and Stefano Leonardi, editors, 46th International Colloquium on Automata, Languages, and Programming (ICALP 2019). Volume 132 of Leibniz International Proceedings in Informatics (LIPIcs), pages 33:1–33:14. Dagstuhl, Germany (2019). Schloss Dagstuhl–Leibniz-Zentrum fuer Informatik.

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

[37] Patrick Rall. ``Quantum algorithms for estimating physical quantities using block encodings''. Physical Review A 102, 022408 (2020).

[38] Yu Tong, Dong An, Nathan Wiebe, and Lin Lin. ``Fast inversion, preconditioned quantum linear system solvers, fast green's-function computation, and fast evaluation of matrix functions''. Physical Review A 104, 032422 (2021).

[39] Julia E Rice, Tanvi P Gujarati, Mario Motta, Tyler Y Takeshita, Eunseok Lee, Joseph A Latone, and Jeannette M Garcia. ``Quantum computation of dominant products in lithium–sulfur batteries''. The Journal of Chemical Physics 154, 134115 (2021).

[40] Trygve Helgaker, Poul Jorgensen, and Jeppe Olsen. ``Molecular electronic-structure theory''. John Wiley & Sons. (2014).

[41] Jacob T Seeley, Martin J Richard, and Peter J Love. ``The bravyi-kitaev transformation for quantum computation of electronic structure''. The Journal of chemical physics 137, 224109 (2012).

[42] Aram W Harrow, Avinatan Hassidim, and Seth Lloyd. ``Quantum algorithm for linear systems of equations''. Physical review letters 103, 150502 (2009).

[43] Andrew M Childs, Robin Kothari, and Rolando D Somma. ``Quantum algorithm for systems of linear equations with exponentially improved dependence on precision''. SIAM Journal on Computing 46, 1920–1950 (2017).

[44] Carlos Bravo-Prieto, Ryan LaRose, M. Cerezo, Yigit Subasi, Lukasz Cincio, and Patrick J. Coles. ``Variational quantum linear solver'' (2019). arXiv:1909.05820.

[45] Hsin-Yuan Huang, Kishor Bharti, and Patrick Rebentrost. ``Near-term quantum algorithms for linear systems of equations with regression loss functions''. New Journal of Physics 23, 113021 (2021).

[46] Yiğit Subaşı, Rolando D Somma, and Davide Orsucci. ``Quantum algorithms for systems of linear equations inspired by adiabatic quantum computing''. Physical review letters 122, 060504 (2019).

[47] Dong An and Lin Lin. ``Quantum linear system solver based on time-optimal adiabatic quantum computing and quantum approximate optimization algorithm''. ACM Transactions on Quantum Computing 3 (2022).

[48] Lin Lin and Yu Tong. ``Optimal polynomial based quantum eigenstate filtering with application to solving quantum linear systems''. Quantum 4, 361 (2020).

[49] Rolando D Somma and Sergio Boixo. ``Spectral gap amplification''. SIAM Journal on Computing 42, 593–610 (2013).

[50] Yosi Atia and Dorit Aharonov. ``Fast-forwarding of hamiltonians and exponentially precise measurements''. Nature communications 8, 1–9 (2017).

[51] Brielin Brown, Steven T Flammia, and Norbert Schuch. ``Computational difficulty of computing the density of states''. Physical review letters 107, 040501 (2011).

[52] Stephen P Jordan, David Gosset, and Peter J Love. ``Quantum-merlin-arthur–complete problems for stoquastic hamiltonians and markov matrices''. Physical Review A 81, 032331 (2010).

[53] Sevag Gharibian and Jamie Sikora. ``Ground state connectivity of local hamiltonians''. ACM Trans. Comput. Theory 10 (2018).

[54] James D. Watson and Johannes Bausch. ``The complexity of approximating critical points of quantum phase transitions'' (2021). arXiv:2105.13350.

Cited by

[1] 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", Quantum 6, 768 (2022).

[2] Yu Tong, "Designing algorithms for estimating ground state properties on early fault-tolerant quantum computers", Quantum Views 6, 65 (2022).

[3] Yulong Dong, Lin Lin, and Yu Tong, "Ground state preparation and energy estimation on early fault-tolerant quantum computers via quantum eigenvalue transformation of unitary matrices", arXiv:2204.05955.

[4] Peter D. Johnson, Alexander A. Kunitsa, Jérôme F. Gonthier, Maxwell D. Radin, Corneliu Buda, Eric J. Doskocil, Clena M. Abuan, and Jhonathan Romero, "Reducing the cost of energy estimation in the variational quantum eigensolver algorithm with robust amplitude estimation", arXiv:2203.07275.

[5] Guoming Wang, Sukin Sim, and Peter D. Johnson, "State Preparation Boosters for Early Fault-Tolerant Quantum Computation", arXiv:2202.06978.

The above citations are from Crossref's cited-by service (last updated successfully 2022-08-18 17:25:35) and SAO/NASA ADS (last updated successfully 2022-08-18 17:25:36). The list may be incomplete as not all publishers provide suitable and complete citation data.

1 thought on “Computing Ground State Properties with Early Fault-Tolerant Quantum Computers

  1. Pingback: Perspective in Quantum Views by Yu Tong "Designing algorithms for estimating ground state properties on early fault-tolerant quantum computers"