Implement a hamiltonian simulation on a diagonal matrix?

Question

I'm trying to implement a Hamiltonian simulation of a diagonal matrix explained on A.M. Childs. Quantum information processing in continuous time (Rule 1.6 in Ref. 10). Briefly, the operations are:

$$ |a,0\rangle \rightarrow |a, d(a)\rangle \rightarrow e^{-itd(a)}|a, d(a)\rangle \rightarrow e^{-itd(a)}|a, 0\rangle $$ In Kothari thesis, he says that, to implement the second operation, you just have to perform a set of controlled phase gates on the first register controlled by the second register, the latter is the $ancilla$, which is coded as $h_j$.

My question is how implement that second operation $|a,d(a)\rangle \rightarrow e^{-itd(a)}|a, d(a)\rangle$ exactly, I can't grasp easily the way to do it.

Answer 1

You can use controlled-powers-of-$Z$ gates on the binary decomposition of $d(a)$. If $d(a)\in\{0,1\}^k$ then for each qubit in $d(a)$ you apply the appropriate controlled-root-of-$Z$ to perform the second operation.

In particular, following @DaftWullie's answer here:

Now, recognise that if you've got some state $|z\rangle$ for $z\in\{0,1\}^k$, it's easy to turn it into $e^{i\pi z 2^k}$ - you apply $Z$ on the most significant bit, $\sqrt{Z}$ on the second-most, $Z^{1/4}$ on the third, $Z^{1/8}$ on the fourth, and so on (think about how you convert from a binary to a decimal representation). Thus, if you apply these gates but controlled off the ancilla, this achieves exactly what you need.