In the book, Nielsen and Chuang, there is a section on quantum simulation of the quantum search algorithm. Hamiltonion operator is defined as follows-

$$ H = |x\rangle\langle x| + |\psi\rangle\langle\psi| $$ where x is the only solution to the search problem and $$ \psi = \frac{\sum_{x}{|x\rangle}}{N} $$ with N being the total number of elements.

enter image description here

I haven't been able to understand how the following circuits were implemented using the Hamiltonions specified in the picture and the book doesn't explain how they came up with the circuits.


1 Answer 1


Both circuits work essentially the same. It's perhaps slightly easier to understand the second because it's being explicit about what it's doing rather than hiding some of it in an oracle. So, take the second diagram. Consider the effect of the middle gates. They basically say

  • if the top register is in the all 0 state, flip the bit of the second register

  • if the second register is in 1, apply a phase. Otherwise, do nothing.

  • if the top register is in the all 0 state, flip the bit of the second register.

Clearly, the first and the third cancel each other out, meaning that the second register will return as $|0\rangle$. However, it's that middle operation that's important. Expressed as it is, hopefully you see that the overall effect of the three gates is to say "add a phase if the top register is in the all 0 state". Thus, the effect of these 3 gates on the first register can be written as $$ I+(e^{i\Delta t}-1)|0\rangle\langle 0|^{\otimes n}. $$ You can now take into account the effect of the other two gates. $$ H^{\otimes n}\left(I+(e^{i\Delta t}-1)|0\rangle\langle 0|^{\otimes n}\right)H^{\otimes n}=I+(e^{i\Delta t}-1)|\psi\rangle\langle \psi|=e^{i\Delta t|\psi\rangle\langle\psi|} $$

There seems to be a minus sign inconsistency with what you've posted. I don't know if that's a mistake I've made somewhere...

To check the identity $$ I+(e^{i\Delta t}-1)|\psi\rangle\langle \psi|=e^{i\Delta t|\psi\rangle\langle\psi|}, $$ it is perhaps easiest to go from right to left. Clearly, the operator $|\psi\rangle\langle\psi|$ is a rank 1 projector, which I'll denote $P_{\psi}$. We can introduce a second projector $P_{\perp}=I-P_{\psi}$. The states that this projects onto all have 0 eigenvalue with $P_{\psi}$.

The definition of the exponential of matrix $M=\sum_j\lambda_jP_j$ is $$ e^{i\theta M}=\sum_je^{i\lambda_j\theta}P_j. $$ So, $$ e^{i\Delta t|\psi\rangle\langle\psi|}=e^{i\Delta t}P_{\psi}+P_{\perp}, $$ which is exactly what we were after.

  • $\begingroup$ The minus sign inconsistency has puzzled me too but the book has that only. Also, can you help me understand conversion from 2nd last step to last step. I am getting a different result using operator functions. $\endgroup$ Commented May 5, 2020 at 16:14
  • $\begingroup$ Thanks a lot. I understood your approach but can you point out what's wrong with mine. I decomposed |ψ⟩⟨ψ| into |ψ⟩⟨ψ| I |ψ⟩⟨ψ| where I is diagonalizable. Now, using operator functions on this, I'll get $\exp(it)|ψ⟩⟨ψ|$, which is a different answer than yours. $\endgroup$ Commented May 6, 2020 at 9:30
  • $\begingroup$ without more complete working, I'm not going to be able to pick it out; but you can see that it cannot be correct because that answer is not unitary (what happens to a state orthogonal to $|\psi\rangle$?) $\endgroup$
    – DaftWullie
    Commented May 6, 2020 at 10:04
  • $\begingroup$ Oh, I understood my mistake. For using operator functions here, matrix must be decomposed into UDU^+, U being a unitary matrix. In my decomposition, U was not unitary. Thanks for helping. $\endgroup$ Commented May 6, 2020 at 10:24

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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