Sparse random Hamiltonians are quantumly easy

Understand

A candidate application for quantum computers is to simulate the low-temperature properties of quantum systems.

• For this task, there is a well-studied quantum algorithm that performs quantum phase estimation on an initial trial state that has a nonnegligible overlap with a low-energy state.
• However, it is notoriously hard to give theoretical guarantees that such a trial state can be prepared efficiently.
• Moreover, the heuristic proposals that are currently available, such as with adiabatic state preparation, appear insufficient in practical cases.