Estimating ground-state properties in quantum chemistry, e.g., the ground-state energy and observable expectation values, has been considered a promising candidate for demonstrating a useful quantum advantage [1,2,3]. For the current quantum hardware, impressive success has been achieved by variational quantum algorithms (VQA) [4,5], and the performance of these algorithms is expected to further improve for near-term devices. However, VQAs are not guaranteed to be scalable for large quantum-chemistry systems, especially when high precision, reaching chemical accuracy, is desired. Algorithms such as [6,7,8,9,10,11,12] based on quantum phase estimation (QPE) [13,14] or matrix functions [15,16,17] are generally considered more promising ways to attain chemical accuracy because of better precision dependence and more rigorous performance guarantees. Yet these algorithms are designed for fully fault-tolerant quantum computers, with considerable requirements in terms of ancilla qubits and circuit depth.
In a work by Zhang, Wang, and Johnson recently published in Quantum , the authors proposed an algorithm to estimate the ground-state observable expectation values with quantum computers that may not be fully fault-tolerant, but still preserves the scalability and performance guarantees of the algorithms such as QPE that are designed for fault-tolerant quantum computers. In particular, the authors considered metrics other than the total runtime, which include the circuit depth and the number of ancilla qubits. The underlying philosophy is that, for quantum devices with some error-correcting capability that we can build at a certain point in the future, it is preferable to have lower circuit depth and fewer ancilla qubits even at some expense in terms of increased total runtime. This type of quantum devices are sometimes called early fault-tolerant quantum computers, which is an increasingly popular term used in, e.g., Refs. [19,20,18,21,22].
One of the first papers that used this term is Ref. , in which the author carried out a non-asymptotic resource analysis for performing QPE for the Hubbard model. In Ref.  this term was first used to describe the type of quantum devices considered here. In the same paper, the authors proposed an algorithm to estimate the ground-state energy in this setting, and it achieves the optimal Heisenberg-limited precision scaling despite constraints on the number of ancilla qubits and circuit depth. In the algorithm it is assumed that one can efficiently prepare an initial guess for the ground state with a large overlap, which is a reasonable assumption for many quantum systems . The algorithm runs by estimating the cumulative distribution function (CDF) of the spectral measure using a circuit that resembles the one used for the Hadamard test. The Heisenberg-limited precision scaling is reached by using randomized evolution times in the circuit.
In , Zhang et al. extended this method to estimate the expectation value of observables in the ground state. Their main tool is a two-variable generalization of the CDF, which they call the 2D $O$-weighted CDF. It can be evaluated using a Hadamard-test-like circuit with randomized evolution times. Through evaluating this CDF and the original CDF in Ref. , the ground-state observable expectation value can be estimated to arbitrary precision. Their algorithm greatly extended the applicability of the framework proposed in Ref. , and the 2D $O$-weighted CDF may have further applications on its own. Previously proposed algorithms using a similar circuit, such as , do not prepare the ground state and as a result cannot directly yield the observable expectation values.
A similar result was obtained in another paper that appeared around the same time , in which the authors considered essentially the same circuit, but a different way of choosing the randomized evolution times. Ref.  considered using randomized compiling within this framework to reduce the circuit depth overhead that comes from implementing the time-evolution operator. More recently, in Ref. , it is shown that inserting Pauli-X rotations between the controlled time-evolution operators quadratically improves the overlap dependence without increasing the circuit depth. The same paper also shows that the improvement with respect to the overlap dependence becomes quartic if one is willing to put up with a larger circuit depth. Besides the ancilla qubits and circuit depth, Ref.  also considered minimizing the use of multi-qubit control structures, which may require a large number of non-Clifford gates to implement. These works provide a versatile toolbox for designing the most suitable algorithm for estimating ground-state properties in the early fault-tolerant setting.
Without more detailed knowledge of what the early versions of fault-tolerant quantum computers are like, it is difficult to say with certainty whether the trade-off between circuit depth and ancilla qubits on the one hand, and the total runtime on the other hand, is the optimal choice. The optimal choice will depend on what cost model best matches the hardware we are going to have. However, with the tools developed in the above mentioned works, it is not hard to imagine that we can combine them with the algorithms that prioritize the runtime to design an algorithm that can be flexibly adjusted to the cost model, thus best utilizing the potential of early fault-tolerant quantum computers.
 Y. Cao, J. Romero, J. P. Olson, M. Degroote, P. D. Johnson, M. Kieferová, I. D. Kivlichan, T. Menke, B. Peropadre, N. P. Sawaya, S. Sim, L. Veis, and A. Aspuru-Guzik. Quantum Chemistry in the Age of Quantum Computing. Chemical Reviews, 119 (19): 10856–10915, 2019. ISSN 15206890. 10.1021/acs.chemrev.8b00803.
 B. Bauer, S. Bravyi, M. Motta, and G. Kin-Lic Chan. Quantum Algorithms for Quantum Chemistry and Quantum Materials Science. Chemical Reviews, 120 (22): 12685–12717, 2020. ISSN 15206890. 10.1021/acs.chemrev.9b00829.
 S. McArdle, S. Endo, A. Aspuru-Guzik, S. C. Benjamin, and X. Yuan. Quantum computational chemistry. Reviews of Modern Physics, 92 (1): 015003, 2020. ISSN 15390756. 10.1103/RevModPhys.92.015003.
 A. Peruzzo, J. McClean, P. Shadbolt, M. H. Yung, X. Q. Zhou, P. J. Love, A. Aspuru-Guzik, and J. L. O'Brien. A variational eigenvalue solver on a photonic quantum processor. Nature Communications, 5: 4213, 2014. ISSN 20411723. 10.1038/ncomms5213.
 J. R. McClean, J. Romero, R. Babbush, and A. Aspuru-Guzik. The theory of variational hybrid quantum-classical algorithms. New Journal of Physics, 18 (2): 023023, 2016. ISSN 13672630. 10.1088/1367-2630/18/2/023023.
 D. Poulin and P. Wocjan. Preparing ground states of quantum many-body systems on a quantum computer. Physical Review Letters, 102 (13): 130503, 2009. ISSN 00319007. 10.1103/PhysRevLett.102.130503.
 D. W. Berry, M. Kieferová, A. Scherer, Y. R. Sanders, G. H. Low, N. Wiebe, C. Gidney, and R. Babbush. Improved techniques for preparing eigenstates of fermionic Hamiltonians. npj Quantum Information, 4 (1): 1–7, 2018. ISSN 20566387. 10.1038/s41534-018-0071-5.
 D. Poulin, A. Kitaev, D. S. Steiger, M. B. Hastings, and M. Troyer. Quantum Algorithm for Spectral Measurement with a Lower Gate Count. Physical Review Letters, 121 (1): 010501, 2018. ISSN 10797114. 10.1103/PhysRevLett.121.010501.
 R. Babbush, C. Gidney, D. W. Berry, N. Wiebe, J. McClean, A. Paler, A. Fowler, and H. Neven. Encoding Electronic Spectra in Quantum Circuits with Linear T Complexity. Physical Review X, 8 (4): 041015, 2018. ISSN 21603308. 10.1103/PhysRevX.8.041015.
 Y. Ge, J. Tura, and J. I. Cirac. Faster ground state preparation and high-precision ground energy estimation with fewer qubits. Journal of Mathematical Physics, 60 (2): 022202, 2019. ISSN 00222488. 10.1063/1.5027484.
 Y. Su, D. W. Berry, N. Wiebe, N. Rubin, and R. Babbush. Fault-Tolerant Quantum Simulations of Chemistry in First Quantization. PRX Quantum, 2 (4): 040332, 2021. ISSN 26913399. 10.1103/PRXQuantum.2.040332.
 D. S. Abrams and S. Lloyd. Quantum algorithm providing exponential speed increase for finding eigenvalues and eigenvectors. Physical Review Letters, 83 (24): 5162–5165, 1999. ISSN 10797114. 10.1103/PhysRevLett.83.5162.
 A. M. Childs and N. Wiebe. Hamiltonian simulation using linear combinations of unitary operations. Quantum Information and Computation, 12 (11-12): 901–924, 2012. ISSN 15337146. 10.26421/qic12.11-12-1.
 G. H. Low and I. L. Chuang. Optimal Hamiltonian Simulation by Quantum Signal Processing. Physical Review Letters, 118 (1): 010501, 2017. ISSN 10797114. 10.1103/PhysRevLett.118.010501.
 A. Gilyén, Y. Su, G. H. Low, and N. Wiebe. Quantum singular value transformation and beyond: Exponential improvements for quantum matrix arithmetics. In Proceedings of the Annual ACM Symposium on Theory of Computing, pages 193–204, 2019. ISBN 9781450367059. 10.1145/3313276.3316366.
 R. Zhang, G. Wang, and P. Johnson. Computing Ground State Properties with Early Fault-Tolerant Quantum Computers. Quantum, 6: 761, 2022. ISSN 2521-327X. 10.22331/q-2022-07-11-761.
 E. T. Campbell. Early fault-tolerant simulations of the Hubbard model. Quantum Science and Technology, 7 (1): 015007, 2022. ISSN 20589565. 10.1088/2058-9565/ac3110.
 L. Lin and Y. Tong. Heisenberg-Limited Ground-State Energy Estimation for Early Fault-Tolerant Quantum Computers. PRX Quantum, 3 (1): 010318, 2022. ISSN 26913399. 10.1103/PRXQuantum.3.010318.
 G. Wang, S. Sim, and P. D. Johnson. State Preparation Boosters for Early Fault-Tolerant Quantum Computation. arXiv preprint arXiv:2202.06978, 2022. URL http://arxiv.org/abs/2202.06978.
 K. Wan, M. Berta, and E. T. Campbell. Randomized Quantum Algorithm for Statistical Phase Estimation. Physical Review Letters, 129 (3): 030503, 2022. ISSN 10797114. 10.1103/PhysRevLett.129.030503.
 N. M. Tubman, C. Mejuto-Zaera, J. M. Epstein, D. Hait, D. S. Levine, W. Huggins, Z. Jiang, J. R. McClean, R. Babbush, M. Head-Gordon, and K. B. Whaley. Postponing the orthogonality catastrophe: efficient state preparation for electronic structure simulations on quantum devices. arXiv preprint arXiv:1809.05523, 2018. URL http://arxiv.org/abs/1809.05523.
 Y. Dong, L. Lin, and Y. Tong. Ground state preparation and energy estimation on early fault-tolerant quantum computers via quantum eigenvalue transformation of unitary matrices. arXiv preprint arXiv:2204.05955, 2022. URL http://arxiv.org/abs/2204.05955.
This View is published in Quantum Views 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.