Scalable Quantum Computation of Highly Excited Eigenstates with Spectral Transforms*

We propose a natural application of Quantum Linear Systems Problem (QLSP) solvers such as the HHL algorithm to efficiently prepare highly excited interior eigenstates of physical Hamiltonians in a variational and targeted manner. This is enabled by the efficient computation of the expectation values of inverse Hamiltonians on quantum computers, in situations where Hamiltonian simulation and the representation of eigenstates on quantum computers are efficient. Importantly, the usage of the QLSP solver as a subroutine within our algorithm -- with its inputs and outputs corresponding to physically meaningful objects such as Hamiltonians and eigenstates arising from physical systems -- does not conceal exponentially costly pre/post-processing steps that usually accompanies it in generic linear algebraic applications. We detail implementations of this scheme for both fault-tolerant and near-term quantum computers, analyze their efficiency and implementability, and detail conditions under which the QLSP solvers' exponentially better scaling in problem size render it advantageous over existing classical and quantum approaches. Simulation results for applications in many-body physics and quantum chemistry further demonstrate its effectiveness and scalability over existing approaches.