  We report an efficient quantum algorithm for estimating the local density of
states (LDOS) on a quantum computer. The LDOS describes the redistribution of
energy levels of a quantum system under the influence of a perturbation.
Sometimes known as the ``strength function'' from nuclear spectroscopy
experiments, the shape of the LDOS is directly related to the survivial
probability of unperturbed eigenstates, and has recently been related to the
fidelity decay (or ``Loschmidt echo'') under imperfect motion-reversal. For
quantum systems that can be simulated efficiently on a quantum computer, the
LDOS estimation algorithm enables an exponential speed-up over direct classical
computation.
