LIMITATIONS ON THE SIMULATION OF NON-SPARSE HAMILTONIANS
The problem of simulating sparse Hamiltonians on quantum computers is well studied. The evolution of a sparse N x N Hamiltonian H for time t can be simulated using O(parallel to Ht parallel to poly(log N)) operations, which is essentially optimal due to a no fast-forwarding theorem. Here, we consider non-sparse Hamiltonians and show significant limitations on their simulation. We generalize the no fast-forwarding theorem to dense Hamiltonians, ruling out generic simulations taking time o(parallel to Ht parallel to), even though parallel to H parallel to is not a unique measure of the size of a dense Hamiltonian H. We also present a stronger limitation ruling out the possibility of generic simulations taking time polyt(parallel to Ht parallel to, log N), showing that known simulations based on discrete-time quantum walk cannot be dramatically improved in general. On the positive side, we show that some non-sparse Hamiltonians can be simulated efficiently, such as those with graphs of small arboricity.
hamiltonian simulation lower bounds