  This paper is an algorithmic study of quantum phase estimation with multiple
eigenvalues. We present robust multiple-phase estimation (RMPE) algorithms with
Heisenberg-limited scaling. The proposed algorithms improve significantly from
the idea of single-phase estimation methods by combining carefully designed
signal processing routines and an adaptive determination of runtime amplifying
factors. They address both the {\em integer-power} model, where the unitary $U$
is given as a black box with only integer runtime accessible, and the {\em
real-power} model, where $U$ is defined through a Hamiltonian $H$ by $U =
\exp(-2\pi\mathrm{i} H)$ with any real runtime allowed. These algorithms are
particularly suitable for early fault-tolerant quantum computers in the
following senses: (1) a minimal number of ancilla qubits are used, (2) an
imperfect initial state with a significant residual is allowed, (3) the
prefactor in the maximum runtime can be arbitrarily small given that the
residual is sufficiently small and a gap among the dominant eigenvalues is
known in advance. Even if the eigenvalue gap does not exist, the proposed RMPE
algorithms can achieve the Heisenberg limit while maintaining (1) and (2).
