Hamiltonian sparsification and gap-simulations

Understand

Analog quantum simulations---simulations of one Hamiltonian by another---is one of the major goals in the noisy intermediate-scale quantum computation (NISQ) era, and has many applications in quantum complexity.

• We initiate the rigorous study of the physical resources required for such simulations, where we focus on the task of Hamiltonian sparsification.
• The goal is to find a simulating Hamiltonian $\tilde{H}$ whose underlying interaction graph has bounded degree (this is called degree-reduction) or much fewer edges than that of the original Hamiltonian $H$ (this is called dilution).
• We set this study in a relaxed framework for analog simulations that we call gap-simulation, where $\tilde{H}$ is only required to simulate the groundstate(s) and spectral gap of $H$ instead of its full spectrum, and we believe it is of independent interest.