Quantum algorithm for ground state energy estimation using circuit depth with exponentially improved dependence on precision

Guoming Wang1, Daniel Stilck França2, Ruizhe Zhang1,3, Shuchen Zhu1,4, and Peter D. Johnson5

1Zapata Computing Canada Inc., Toronto, ON M5V 2Y1, Canada
2Univ Lyon, ENS Lyon, UCBL, CNRS, Inria, LIP, F-69342, Lyon Cedex 07, France
3Department of Computer Science, University of Texas at Austin, Austin, TX 78712, USA
4Department of Computer Science, Georgetown University, Washington, DC 20057, USA
5Zapata Computing Inc., Boston, MA 02110 USA

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


A milestone in the field of quantum computing will be solving problems in quantum chemistry and materials faster than state-of-the-art classical methods. The current understanding is that achieving quantum advantage in this area will require some degree of fault tolerance. While hardware is improving towards this milestone, optimizing quantum algorithms also brings it closer to the present. Existing methods for ground state energy estimation are costly in that they require a number of gates per circuit that grows exponentially with the desired number of bits in precision. We reduce this cost exponentially, by developing a ground state energy estimation algorithm for which this cost grows linearly in the number of bits of precision. Relative to recent resource estimates of ground state energy estimation for the industrially-relevant molecules of ethylene-carbonate and PF$_6^-$, the estimated gate count and circuit depth is reduced by a factor of 43 and 78, respectively. Furthermore, the algorithm can use additional circuit depth to reduce the total runtime. These features make our algorithm a promising candidate for realizing quantum advantage in the era of early fault-tolerant quantum computing.

► BibTeX data

► References

[1] Henrik R. Larsson, Huanchen Zhai, Cyrus J. Umrigar, and Garnet Kin-Lic Chan. The chromium dimer: closing a chapter of quantum chemistry. Journal of the American Chemical Society, 144(35):15932–15937, 2022.

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

[3] Jérôme F. Gonthier, Maxwell D. Radin, Corneliu Buda, Eric J Doskocil, Clena M. Abuan, and Jhonathan Romero. Measurements as a roadblock to near-term practical quantum advantage in chemistry: Resource analysis. Physical Review Research, 4(3):033154, 2022.

[4] Isaac H. Kim, Ye-Hua Liu, Sam Pallister, William Pol, Sam Roberts, and Eunseok Lee. Fault-tolerant resource estimate for quantum chemical simulations: Case study on li-ion battery electrolyte molecules. Physical Review Research, 4(2):023019, 2022.

[5] Alain Delgado, Pablo A. M. Casares, Roberto dos Reis, Modjtaba Shokrian Zini, Roberto Campos, Norge Cruz-Hernández, Arne-Christian Voigt, Angus Lowe, Soran Jahangiri, M. A. Martin-Delgado, et al. Simulating key properties of lithium-ion batteries with a fault-tolerant quantum computer. Physical Review A, 106(3):032428, 2022.

[6] Joshua J. Goings, Alec White, Joonho Lee, Christofer S. Tautermann, Matthias Degroote, Craig Gidney, Toru Shiozaki, Ryan Babbush, and Nicholas C. Rubin. Reliably assessing the electronic structure of cytochrome p450 on today's classical computers and tomorrow's quantum computers. Proceedings of the National Academy of Sciences, 119(38): e2203533119, 2022.

[7] 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):4213, 2014.

[8] 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 preprint arXiv:2203.07275, 2022.

[9] Jarrod R. McClean, Sergio Boixo, Vadim N. Smelyanskiy, Ryan Babbush, and Hartmut Neven. Barren plateaus in quantum neural network training landscapes. Nature Communications, 9(1):4812, 2018.

[10] Eric R. Anschuetz and Bobak T. Kiani. Quantum variational algorithms are swamped with traps. Nature Communications, 13(1):7760, 2022.

[11] 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):041015, 2018.

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

[13] 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. PRX Quantum, 3(4):040305, 2022.

[14] Rolando D. Somma. Quantum eigenvalue estimation via time series analysis. New Journal of Physics, 21(12):123025, 2019.

[15] Kianna Wan, Mario Berta, and Earl T. Campbell. Randomized quantum algorithm for statistical phase estimation. Physical Review Letters, 129(3):030503, 2022.

[16] Earl Campbell. Random compiler for fast Hamiltonian simulation. Physical Review Letters, 123(7):070503, 2019.

[17] Zhiyan Ding and Lin Lin. Even shorter quantum circuit for phase estimation on early fault-tolerant quantum computers with applications to ground-state energy estimation. PRX Quantum, 4(2):020331, 2023.

[18] Hongkang Ni, Haoya Li, and Lexing Ying. On low-depth algorithms for quantum phase estimation. arXiv preprint arXiv:2302.02454, 2023.

[19] Zhiyan Ding and Lin Lin. Simultaneous estimation of multiple eigenvalues with short-depth quantum circuit on early fault-tolerant quantum computers. Quantum, 7:1136, 2023.

[20] Haoya Li, Hongkang Ni, and Lexing Ying. On adaptive low-depth quantum algorithms for robust multiple-phase estimation. arXiv preprint arXiv:2303.08099, 2023.

[21] Thomas E. O'Brien, Brian Tarasinski, and Barbara M. Terhal. Quantum phase estimation of multiple eigenvalues for small-scale (noisy) experiments. New Journal of Physics, 21(2):023022, 2019.

[22] Alicja Dutkiewicz, Barbara M. Terhal, and Thomas E. O'Brien. Heisenberg-limited quantum phase estimation of multiple eigenvalues with few control qubits. Quantum, 6:830, 2022.

[23] Frank Neese. The ORCA program system. Wiley Interdisciplinary Reviews: Computational Molecular Science, 2(1):73–78, 2012.

[24] Frank Neese. Software update: the ORCA program system, version 4.0. Wiley Interdisciplinary Reviews: Computational Molecular Science, 8(1):e1327, 2018.

[25] Norm M. Tubman, Carlos Mejuto-Zaera, Jeffrey M. Epstein, Diptarka Hait, Daniel S. Levine, William Huggins, Zhang Jiang, Jarrod R. McClean, Ryan Babbush, Martin Head-Gordon, K. Birgitta Whaley. Postponing the orthogonality catastrophe: efficient state preparation for electronic structure simulations on quantum devices. arXiv preprint arXiv:1809.05523, 2018.

[26] Ruizhe Zhang, Guoming Wang, and Peter Johnson. Computing ground state properties with early fault-tolerant quantum computers. Quantum, 6:761, 2022.

[27] Guoming Wang, Sukin Sim, and Peter D. Johnson. State preparation boosters for early fault-tolerant quantum computation. Quantum, 6:829, 2022.

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

[29] Amara Katabarwa, Alex Kunitsa, Borja Peropadre, and Peter Johnson. Reducing runtime and error in VQE using deeper and noisier quantum circuits. arXiv preprint arXiv:2110.10664, 2021.

[30] Rutuja Kshirsagar, Amara Katabarwa, and Peter D. Johnson. On proving the robustness of algorithms for early fault-tolerant quantum computers. arXiv preprint arXiv:2209.11322, 2022.

[31] Andris Ambainis. On physical problems that are slightly more difficult than QMA. In 2014 IEEE 29th Conference on Computational Complexity (CCC), pages 32–43. IEEE, 2014.

[32] Wassily Hoeffding. Probability inequalities for sums of bounded random variables. Journal of the American Statistical Association, 58(301):13–30, 1963.

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

[34] Guoming Wang, Daniel Stilck França, Gumaro Rendon, and Peter D. Johnson. Faster ground state energy estimation on early fault-tolerant quantum computers via rejection sampling. arXiv preprint arXiv:2304.09827, 2023.

Cited by

[1] Ignacio Loaiza and Artur F. Izmaylov, "Block-Invariant Symmetry Shift: Preprocessing Technique for Second-Quantized Hamiltonians to Improve Their Decompositions to Linear Combination of Unitaries", Journal of Chemical Theory and Computation 19 22, 8201 (2023).

[2] Woo-Ram Lee, Ryan Scott, and V. W. Scarola, "A Compact Noise-Tolerant Algorithm for Unbiased Quantum Simulation Using Feynman's $i\eta$ Prescription", arXiv:2212.14039, (2022).

[3] Modjtaba Shokrian Zini, Alain Delgado, Roberto dos Reis, Pablo Antonio Moreno Casares, Jonathan E. Mueller, Arne-Christian Voigt, and Juan Miguel Arrazola, "Quantum simulation of battery materials using ionic pseudopotentials", Quantum 7, 1049 (2023).

[4] Pablo Antonio Moreno Casares, "Fault-tolerant quantum algorithms", arXiv:2301.08057, (2023).

[5] Yukun Zhang, Yifei Huang, Jinzhao Sun, Dingshun Lv, and Xiao Yuan, "Quantum Computing Quantum Monte Carlo", arXiv:2206.10431, (2022).

[6] Zhiyan Ding and Lin Lin, "Even Shorter Quantum Circuit for Phase Estimation on Early Fault-Tolerant Quantum Computers with Applications to Ground-State Energy Estimation", PRX Quantum 4 2, 020331 (2023).

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

[8] S. Pathak, A. E. Russo, S. K. Seritan, and A. D. Baczewski, "Quantifying T -gate-count improvements for ground-state-energy estimation with near-optimal state preparation", Physical Review A 107 4, L040601 (2023).

[9] Guoming Wang, Daniel Stilck França, Gumaro Rendon, and Peter D. Johnson, "Faster ground state energy estimation on early fault-tolerant quantum computers via rejection sampling", arXiv:2304.09827, (2023).

[10] Francesco Pio Barone, Oriel Kiss, Michele Grossi, Sofia Vallecorsa, and Antonio Mandarino, "Counterdiabatic optimized driving in quantum phase sensitive models", arXiv:2311.04282, (2023).

[11] Hongkang Ni, Haoya Li, and Lexing Ying, "On low-depth algorithms for quantum phase estimation", Quantum 7, 1165 (2023).

[12] Jinzhao Sun, Lucia Vilchez-Estevez, Vlatko Vedral, Andrew T. Boothroyd, and M. S. Kim, "Probing spectral features of quantum many-body systems with quantum simulators", arXiv:2305.07649, (2023).

[13] Samson Wang, Sam McArdle, and Mario Berta, "Qubit-Efficient Randomized Quantum Algorithms for Linear Algebra", arXiv:2302.01873, (2023).

[14] Nick S. Blunt, Laura Caune, Róbert Izsák, Earl T. Campbell, and Nicole Holzmann, "Statistical phase estimation and error mitigation on a superconducting quantum processor", arXiv:2304.05126, (2023).

[15] Nhat A. Nghiem and Tzu-Chieh Wei, "Quantum algorithm for estimating largest eigenvalues", Physics Letters A 488, 129138 (2023).

[16] Rutuja Kshirsagar, Amara Katabarwa, and Peter D. Johnson, "On proving the robustness of algorithms for early fault-tolerant quantum computers", arXiv:2209.11322, (2022).

[17] Zhiyan Ding and Lin Lin, "Simultaneous estimation of multiple eigenvalues with short-depth quantum circuit on early fault-tolerant quantum computers", Quantum 7, 1136 (2023).

[18] Qiyao Liang, Yiqing Zhou, Archismita Dalal, and Peter D. Johnson, "Modeling the Performance of Early Fault-Tolerant Quantum Algorithms", arXiv:2306.17235, (2023).

[19] Youle Wang, Chenghong Zhu, Mingrui Jing, and Xin Wang, "Ground state preparation with shallow variational warm-start", arXiv:2303.11204, (2023).

[20] Allan Tosta, Thais de Lima Silva, Giancarlo Camilo, and Leandro Aolita, "Randomized semi-quantum matrix processing", arXiv:2307.11824, (2023).

[21] Gumaro Rendon and Peter D. Johnson, "Low-depth Gaussian State Energy Estimation", arXiv:2309.16790, (2023).

[22] Changhao Yi, Cunlu Zhou, and Jun Takahashi, "Quantum Phase Estimation by Compressed Sensing", arXiv:2306.07008, (2023).

The above citations are from Crossref's cited-by service (last updated successfully 2023-12-07 08:35:05) and SAO/NASA ADS (last updated successfully 2023-12-07 08:35:06). The list may be incomplete as not all publishers provide suitable and complete citation data.