Quantum phase estimation is a cornerstone in quantum algorithm design, allowing for the inference of eigenvalues of exponentially-large sparse matrices. The maximum rate at which these eigenvalues may be learned, –known as the Heisenberg limit–, is constrained by bounds on the circuit complexity required to simulate an arbitrary Hamiltonian. Single-control qubit variants of quantum phase estimation that do not require coherence between experiments have garnered interest in recent years due to lower circuit depth and minimal qubit overhead. In this work we show that these methods can achieve the Heisenberg limit, also when one is unable to prepare eigenstates of the system. Given a quantum subroutine which provides samples of a ‘phase function’ g(k) = ^P_j A_je^iφjk with unknown eigenphases φ_j and overlaps A_j at quantum cost O(k), we show how to estimate the phases {φ_j} with (root-mean-square) error δ for total quantum cost T = O(δ⁻¹). Our scheme combines the idea of Heisenberg-limited multi-order quantum phase estimation for a single eigenvalue phase [1, 2] with subroutines with so-called dense quantum phase estimation which uses classical processing via time-series analysis for the QEEP problem [3] or the matrix pencil method. For our algorithm which adaptively fixes the choice for k in g(k) we prove Heisenberg-limited scaling when we use the time-series/QEEP subroutine. We present numerical evidence that using the matrix pencil technique the algorithm can achieve Heisenberg-limited scaling as well.

Modeling chemical reactions and complicated molecular systems has been proposed as the“killer application”of a future quantumcomputer. Accurate calculations of derivatives of molecular eigenenergies are essential toward this end, allowing for geometryoptimization, transition state searches, predictions of the response to an applied electric or magneticfield, and molecular dynamicssimulations. In this work, we survey methods to calculate energy derivatives, and present two new methods: one based onquantum phase estimation, the other on a low-order response approximation. We calculate asymptotic error bounds andapproximate computational scalings for the methods presented. Implementing these methods, we perform geometry optimizationon an experimental quantum processor, estimating the equilibrium bond length of the dihydrogen molecule to within 0:014 Å ofthe full configuration interaction value. Within the same experiment, we estimate the polarizability of the H2molecule,findingagreement at the equilibrium bond length to within 0:06 a.u. (2%relative error)