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.
 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.
 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.
 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.
 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.
 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.
 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.
 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.
 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.
 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.
 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.
 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.
 Kianna Wan, Mario Berta, and Earl T. Campbell. Randomized quantum algorithm for statistical phase estimation. Physical Review Letters, 129(3):030503, 2022.
 Earl Campbell. Random compiler for fast Hamiltonian simulation. Physical Review Letters, 123(7):070503, 2019.
 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.
 Hongkang Ni, Haoya Li, and Lexing Ying. On low-depth algorithms for quantum phase estimation. arXiv preprint arXiv:2302.02454, 2023.
 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.
 Haoya Li, Hongkang Ni, and Lexing Ying. On adaptive low-depth quantum algorithms for robust multiple-phase estimation. arXiv preprint arXiv:2303.08099, 2023.
 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.
 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.
 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.
 Guoming Wang, Dax Enshan Koh, Peter D. Johnson, and Yudong Cao. Minimizing estimation runtime on noisy quantum computers. PRX Quantum, 2(1):010346, 2021.
 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.
 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.
 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.
 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.
 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).
 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).
 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).
 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).
 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).
 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).
 Hongkang Ni, Haoya Li, and Lexing Ying, "On low-depth algorithms for quantum phase estimation", Quantum 7, 1165 (2023).
 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).
 Nhat A. Nghiem and Tzu-Chieh Wei, "Quantum algorithm for estimating largest eigenvalues", Physics Letters A 488, 129138 (2023).
 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).
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.
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.