Limitations on the simulation of non-sparse Hamiltonians

Details Limitations on the simulation of non-sparse Hamiltonians Limitations on the simulation of non-sparse Hamiltonians

2009-08-31

arxiv.org/abs/0908.4398v2

Quantum Information and Computation 10, 669-684 (2010)

Physics

Quantum Physics

v1: 12 pages. v2: 15 pages; strengthened main result

Scientific paper

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.

Affiliated with

Also associated with

No associations

Rating

Limitations on the simulation of non-sparse Hamiltonians does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.

If you have personal experience with Limitations on the simulation of non-sparse Hamiltonians, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Limitations on the simulation of non-sparse Hamiltonians will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-219992