<p>Diagonal Hamiltonians are easy to simulate with 2 queries. It's very well explained (with a circuit diagram!) in <a href="http://dx.doi.org/1721.1/16663" rel="noreferrer">Andrew Childs' PhD thesis</a> on page 18, Rule 1.6. </p>

<p>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). </p>

<p>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.</p>

CC BY-SA 3.0
2011-05-06T02:19:26.073Z
It seems I'm a complete idiot! Thanks Robin, that's exactly what I needed, and fairly obvious in retrospect.
Joe Fitzsimons
CC BY-SA 4.0
2023-02-15T22:54:40.240Z
Is there a similar way to construct a block encoding of a diagonal matrix $H$ given an oracle $|a,0\rangle\mapsto|a,d(a)\rangle$ returning its elements $H_{aa}$ with fixed-bit precision?
mavzolej
CC BY-SA 3.0
2011-05-06T00:47:44.227Z
2011-05-06T00:47:44.227Z
Robin Kothari
<p>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 <span class="math-container">$H$</span>, which will be given by <span class="math-container">$e^{-iHt}$</span>. If <span class="math-container">$H$</span> is sparse, and the entries of <span class="math-container">$H$</span> are available via some blackbox function then there are efficient algorithms to simulate this evolution operator to within some constant distance <span class="math-container">$\epsilon$</span> in the trace norm.</p>
<p>According to <a href="https://doi.org/10.1007/s00220-006-0150-x" rel="nofollow noreferrer">Berry, Ahokas, Cleve and Sanders, Commun. Math. Phys. 270, 359–371 (2007)</a> 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 <a href="https://dl.acm.org/doi/10.1145/780542.780552" rel="nofollow noreferrer">STOC 03 paper</a> on quantum random walks by Childs, Cleve, Deotto, Fahri, Gutmann and Spielman which seems to only deal with a specific subset of such Hamiltonians.</p>
<p>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).</p>
<p>For what it's worth, I am specifically interested in the case of simulating diagonal Hamiltonians.</p>

CC BY-SA 3.0
2011-05-06T00:21:56.987Z
Robin Kothari's thesis has some improvements on sparse Hamiltonian simulation of BACS07 ( http://uwspace.uwaterloo.ca/bitstream/10012/5356/1/RobinKothariThesis.pdf ), it might explain what you are looking for. But a better source is probably Robin himself!
Artem Kaznatcheev
<cc.complexity-theory><quantum-computing><physics>
How efficiently can a 1-sparse Hamiltonian be simulated (quantum mechanically)?
Joe Fitzsimons
# How efficiently can a 1-sparse Hamiltonian be simulated (quantum mechanically)?

(Asked by: username_0 on 2011-05-05)

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)](https://doi.org/10.1007/s00220-006-0150-x) 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](https://dl.acm.org/doi/10.1145/780542.780552) 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.

**Tags:** cc.complexity-theory, quantum-computing, physics

> **Comments:**
> **username_1**: username_2's thesis has some improvements on sparse Hamiltonian simulation of BACS07 ( http://uwspace.uwaterloo.ca/bitstream/10012/5356/1/RobinKothariThesis.pdf ), it might explain what you are looking for. But a better source is probably Robin himself!  

---

## 1 answers

### Answer by username_2 on 2011-05-06. Score: 9 | Accepted answer

Diagonal Hamiltonians are easy to simulate with 2 queries. It's very well explained (with a circuit diagram!) in [Andrew Childs' PhD thesis](http://dx.doi.org/1721.1/16663) 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.

> **Comments:**
> **username_0**: It seems I'm a complete idiot! Thanks Robin, that's exactly what I needed, and fairly obvious in retrospect.  
> **username_3**: Is there a similar way to construct a block encoding of a diagonal matrix $H$ given an oracle $|a,0\rangle\mapsto|a,d(a)\rangle$ returning its elements $H_{aa}$ with fixed-bit precision?  

---

