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.


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.

  • $\begingroup$ It seems I'm a complete idiot! Thanks Robin, that's exactly what I needed, and fairly obvious in retrospect. $\endgroup$ – Joe Fitzsimons May 6 '11 at 2:19

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.