  A milestone in the field of quantum computing will be solving problems in
quantum chemistry and materials faster than state-of-the-art classical methods.
The current understanding is that achieving quantum advantage in this area will
require some degree of fault tolerance. While hardware is improving towards
this milestone, optimizing quantum algorithms also brings it closer to the
present. Existing methods for ground state energy estimation are costly in that
they require a number of gates per circuit that grows exponentially with the
desired number of bits in precision. We reduce this cost exponentially, by
developing a ground state energy estimation algorithm for which this cost grows
linearly in the number of bits of precision. Relative to recent resource
estimates of ground state energy estimation for the industrially-relevant
molecules of ethylene-carbonate and PF$_6^-$, the estimated gate count and
circuit depth is reduced by a factor of 43 and 78, respectively. Furthermore,
the algorithm can use additional circuit depth to reduce the total runtime.
These features make our algorithm a promising candidate for realizing quantum
advantage in the era of early fault-tolerant quantum computing.
