  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, {\em also} when one is unable to prepare eigenstates of the system.
Given a quantum subroutine which provides samples of a `phase function'
$g(k)=\sum_j A_j e^{i \phi_j k}$ with unknown eigenphases $\phi_j$ and overlaps
$A_j$ at quantum cost $O(k)$, we show how to estimate the phases $\{\phi_j\}$
with (root-mean-square) error $\delta$ for total quantum cost
$T=O(\delta^{-1})$. Our scheme combines the idea of Heisenberg-limited
multi-order quantum phase estimation for a single eigenvalue phase [Higgins et
al (2009) and Kimmel et al (2015)] with subroutines with so-called dense
quantum phase estimation which uses classical processing via time-series
analysis for the QEEP problem [Somma (2019)] 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.
