  Many promising quantum applications depend on the efficient quantum
simulation of an exponentially large sparse Hamiltonian, a task known as sparse
Hamiltonian simulation, which is fundamentally important in quantum
computation. Although several theoretically appealing quantum algorithms have
been proposed for this task, they typically require a black-box query model of
the sparse Hamiltonian, rendering them impractical for near-term implementation
on quantum devices.
  In this paper, we propose a technique named Hamiltonian embedding. This
technique simulates a desired sparse Hamiltonian by embedding it into the
evolution of a larger and more structured quantum system, allowing for more
efficient simulation through hardware-efficient operations. We conduct a
systematic study of this new technique and demonstrate significant savings in
computational resources for implementing prominent quantum applications. As a
result, we can now experimentally realize quantum walks on complicated graphs
(e.g., binary trees, glued-tree graphs), quantum spatial search, and the
simulation of real-space Schr\"odinger equations on current trapped-ion and
neutral-atom platforms. Given the fundamental role of Hamiltonian evolution in
the design of quantum algorithms, our technique markedly expands the horizon of
implementable quantum advantages in the NISQ era.
