



01322nas a2200121   4500008004100000245006100041210006000102260001500162520094400177100002301121700001901144856003701163       2009                        eng d00aLimitations on the simulation of non-sparse Hamiltonians0 aLimitations on the simulation of nonsparse Hamiltonians  c2009/08/313 a  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(||Ht||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(||Ht||), even though ||H|| 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 poly(||Ht||,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.
1 aChilds, Andrew, M.1 aKothari, Robin  uhttp://arxiv.org/abs/0908.4398v2