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

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

Time Stamp: November 6, 2023 8:28 AM
Source Node: 2369686

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.

Abstract

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.
https:/​/​doi.org/​10.1021/​jacs.2c06357

[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.
https:/​/​doi.org/​10.1126/​science.1113479

[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.
https:/​/​doi.org/​10.1103/​PhysRevResearch.4.033154

[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.
https:/​/​doi.org/​10.1103/​PhysRevResearch.4.023019

[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.
https:/​/​doi.org/​10.1103/​PhysRevA.106.032428

[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.
https:/​/​doi.org/​10.1073/​pnas.2203533119

[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.
https:/​/​doi.org/​10.1038/​ncomms5213

[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.
https:/​/​doi.org/​10.48550/​arXiv.2203.07275
arXiv:2203.07275

[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.
https:/​/​doi.org/​10.1038/​s41467-018-07090-4

[10] Eric R. Anschuetz and Bobak T. Kiani. Quantum variational algorithms are swamped with traps. Nature Communications, 13(1):7760, 2022.
https:/​/​doi.org/​10.1038/​s41467-022-35364-5

[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.
https:/​/​doi.org/​10.1103/​PhysRevX.8.041015

[12] Lin Lin and Yu Tong. Heisenberg-limited ground-state energy estimation for early fault-tolerant quantum computers. PRX Quantum, 3(1):010318, 2022.
https:/​/​doi.org/​10.1103/​PRXQuantum.3.010318

[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.
https:/​/​doi.org/​10.1103/​PRXQuantum.3.040305

[14] Rolando D. Somma. Quantum eigenvalue estimation via time series analysis. New Journal of Physics, 21(12):123025, 2019.
https:/​/​doi.org/​10.1088/​1367-2630/​ab5c60

[15] Kianna Wan, Mario Berta, and Earl T. Campbell. Randomized quantum algorithm for statistical phase estimation. Physical Review Letters, 129(3):030503, 2022.
https:/​/​doi.org/​10.1103/​PhysRevLett.129.030503

[16] Earl Campbell. Random compiler for fast Hamiltonian simulation. Physical Review Letters, 123(7):070503, 2019.
https:/​/​doi.org/​10.1103/​PhysRevLett.123.070503

[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.
https:/​/​doi.org/​10.1103/​PRXQuantum.4.020331

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

[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.
https:/​/​doi.org/​10.22331/​q-2023-10-11-1136

[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.
https:/​/​doi.org/​10.48550/​arXiv.2303.08099
arXiv:2303.08099

[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.
https:/​/​doi.org/​10.1088/​1367-2630/​aafb8e

[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.
https:/​/​doi.org/​10.22331/​q-2022-10-06-830

[23] Frank Neese. The ORCA program system. Wiley Interdisciplinary Reviews: Computational Molecular Science, 2(1):73–78, 2012.
https:/​/​doi.org/​10.1002/​wcms.81

[24] Frank Neese. Software update: the ORCA program system, version 4.0. Wiley Interdisciplinary Reviews: Computational Molecular Science, 8(1):e1327, 2018.
https:/​/​doi.org/​10.1002/​wcms.1327

[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.
https:/​/​doi.org/​10.48550/​arXiv.1809.05523
arXiv:1809.05523

[26] Ruizhe Zhang, Guoming Wang, and Peter Johnson. Computing ground state properties with early fault-tolerant quantum computers. Quantum, 6:761, 2022.
https:/​/​doi.org/​10.22331/​q-2022-07-11-761

[27] Guoming Wang, Sukin Sim, and Peter D. Johnson. State preparation boosters for early fault-tolerant quantum computation. Quantum, 6:829, 2022.
https:/​/​doi.org/​10.22331/​q-2022-10-06-829

[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.
https:/​/​doi.org/​10.1103/​PRXQuantum.2.010346

[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.
https:/​/​doi.org/​10.48550/​arXiv.2110.10664
arXiv:2110.10664

[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.
https:/​/​doi.org/​10.48550/​arXiv.2209.11322
arXiv:2209.11322

[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.
https:/​/​doi.org/​10.1109/​CCC.2014.12

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

[33] Yu Tong. Designing algorithms for estimating ground state properties on early fault-tolerant quantum computers. Quantum Views, 6:65, 2022.
https:/​/​doi.org/​10.22331/​qv-2022-07-22-65

[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.
https:/​/​doi.org/​10.48550/​arXiv.2304.09827
arXiv:2304.09827

Cited by

[1] Woo-Ram Lee, Ryan Scott, and V. W. Scarola, “A Compact Noise-Tolerant Algorithm for Unbiased Quantum Simulation Using Feynman’s $ieta$ Prescription”, arXiv:2212.14039, (2022).

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

[3] Pablo Antonio Moreno Casares, “Fault-tolerant quantum algorithms”, arXiv:2301.08057, (2023).

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

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

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

[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] Samson Wang, Sam McArdle, and Mario Berta, “Qubit-Efficient Randomized Quantum Algorithms for Linear Algebra”, arXiv:2302.01873, (2023).

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

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

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

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

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

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

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

[16] Nhat A. Nghiem and Tzu-Chieh Wei, “Quantum Algorithm For Estimating Eigenvalue”, arXiv:2211.06179, (2022).

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

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

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

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

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

The above citations are from SAO/NASA ADS (last updated successfully 2023-11-06 13:31:07). The list may be incomplete as not all publishers provide suitable and complete citation data.

Could not fetch Crossref cited-by data during last attempt 2023-11-06 13:31:06: Could not fetch cited-by data for 10.22331/q-2023-11-06-1167 from Crossref. This is normal if the DOI was registered recently.

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.

Time Stamp:

More from Quantum Journal