Heisenberg-Limited Ground-State Energy Estimation for Early Fault-Tolerant Quantum Computers

Under suitable assumptions, the quantum-phase-estimation (QPE) algorithm is able to achieve Heisenberg-limited precision scaling in estimating the ground-state energy. However, QPE requires a large number of ancilla qubits and a large circuit depth, as well as the ability to perform inverse quantum Fourier transform, making it expensive to implement on an early fault-tolerant quantum computer. We propose an alternative method to estimate the ground-state energy of a Hamiltonian with Heisenberglimited precision scaling, which employs a simple quantum circuit with one ancilla qubit, and a classical postprocessing procedure. Besides the ground-state energy, our algorithm also produces an approximate cumulative distribution function of the spectral measure, which can be used to compute other spectral properties of the Hamiltonian.