How efficiently can a 1-sparse Hamiltonian be simulated (quantum mechanically)?

Question

In quantum computation there is a fair amount of interest in the task of simulating quantum physics. One instance of this is the problem of simulating the evolution of a system under the action of some general Hamiltonian $H$, which will be given by $e^{-iHt}$. If $H$ is sparse, and the entries of $H$ are available via some blackbox function then there are efficient algorithms to simulate this evolution operator to within some constant distance $\epsilon$ in the trace norm.

According to Berry, Ahokas, Cleve and Sanders, Commun. Math. Phys. 270, 359–371 (2007) 1-sparse Hamiltonians can be simulated efficiently using only 2 black box queries. However, the citations that go with this are to a masters thesis which does not appear to be online and to a STOC 03 paper on quantum random walks by Childs, Cleve, Deotto, Fahri, Gutmann and Spielman which seems to only deal with a specific subset of such Hamiltonians.

I guess that this is in fact true for all 1-sparse Hamiltonians, as the paper seems to indicate, but there is obviously something I'm missing (which is probably in the unobtainable thesis). I would be very grateful if someone could tell me whether or not this is true in general, and if so explain how it can be done (or point to a paper which contains it).

For what it's worth, I am specifically interested in the case of simulating diagonal Hamiltonians.

Answer 1

Diagonal Hamiltonians are easy to simulate with 2 queries. It's very well explained (with a circuit diagram!) in Andrew Childs' PhD thesis on page 18, Rule 1.6.

The main idea is to observe that if H is the Hamiltonian with diagonal entries d(j), then simulating H for time t maps the basis state $|j\rangle$ to $e^{-id(j)t}|j\rangle$. This is performed as follows: $|j, 0\rangle \rightarrow |j, d(j)\rangle$ (this uses 1 query), then $|j, d(j)\rangle \rightarrow e^{-id(j)t}|j, d(j)\rangle$ (this is a controlled phase flip on the first register controlled by the second), and then $e^{-id(j)t}|j, d(j)\rangle \rightarrow e^{-id(j)t}|j, 0\rangle$ (this uncomputes the answer using another query).

Indeed, all 1-sparse Hamiltonians can be simulated with 2 queries. This is also explained in Andrew's thesis, towards the end of page 20. It might be a bit hard to understand since it's explained in the context of simulating a d-sparse Hamiltonian using edge coloring. But the essential idea is to reduce a d-sparse Hamiltonian to a sum of 1-sparse Hamiltonians and then simulate the 1-sparse Hamiltonian.