The Hamiltonian in the simulation of Grover Search is given as, $H=|x\rangle\langle x|+|\psi\rangle\langle\psi|$. It is said that in order to simulate $H$ we can simulate the Hamiltonians $H_1=|x\rangle\langle x|$ and $H_2=|\psi\rangle\langle\psi|$ for short time increments $\Delta t$. In Page 258, Quantum Computation and Quantum Information by Nielsen and Chuang, the following circuits which implement the operations $\exp(-i|x\rangle\langle x|\Delta t)$ and $\exp(-i|\psi\rangle\langle \psi|\Delta t)$ are given :


Thanks @MonteNero for the fix, so my understanding is that,

$$ (|x\rangle\langle x|)^{2m}=|x\rangle\langle x|=(|x\rangle\langle x|)^{2m+1}\\ e^{-i|x\rangle\langle x|\Delta t}=\sum_{k=0}^\infty\frac{1}{k!}(-i\Delta t)^k(|x\rangle\langle x|)^k\\ =\sum_{m=0}^\infty\frac{1}{(2m)!}(-i\Delta t)^{2m}(|x\rangle\langle x|)^{2m}+\sum_{m=0}^\infty\frac{1}{(2m+1)!}(-i\Delta t)^{2m+1}(|x\rangle\langle x|)^{2m+1}\\ $$ $$ =I+\sum_{m=1}^\infty\frac{(-i)^{2m}}{(2m)!}(\Delta t)^{2m}.|x\rangle\langle x|-\sum_{m=0}^\infty\frac{i(-i)^{2m}}{(2m+1)!}(\Delta t)^{2m+1}.|x\rangle\langle x|\\ =I+|x\rangle\langle x|(\sum_{m=1}^\infty\frac{(-i)^{2m}}{(2m)!}(\Delta t)^{2m}+1-1)-|x\rangle\langle x|\sum_{m=0}^\infty\frac{i(-i)^{2m}}{(2m+1)!}(\Delta t)^{2m+1}\\ =I-|x\rangle\langle x|+|x\rangle\langle x|\bigg(\sum_{m=0}^\infty\frac{(-1)^m}{(2m)!}(\Delta t)^{2m}-i\sum_{m=0}^\infty\frac{(-1)^m}{(2m+1)!}(\Delta t)^{2m+1}\bigg)\\ =I+|x\rangle\langle x|\Big(\cos(\Delta t)-i\sin(\Delta t)-1\Big)=I+(e^{-i\Delta t}-1)|x\rangle\langle x| $$ $$ \implies e^{-i|x\rangle\langle x|\Delta t}|x\rangle=(I+(e^{-i\Delta t}-1)|x\rangle\langle x|)|x\rangle=e^{-i\Delta t}|x\rangle $$

What oracle does is it flips $|0\rangle\to|1\rangle$ if the input is $|x\rangle$, then

$\begin{bmatrix}1&0\\0&e^{i\Delta t}\end{bmatrix}|1\rangle=\begin{bmatrix}1&0\\0&e^{i\Delta t}\end{bmatrix}\begin{bmatrix}0\\1\end{bmatrix}=e^{i\Delta t}\begin{bmatrix}0\\1\end{bmatrix}=e^{i\Delta t}|1\rangle$

This look like the phase gate should be $\begin{bmatrix}1&0\\0&\color{red}{e^{-i\Delta t}}\end{bmatrix}$ ? Or am I missing something ?


1 Answer 1


Nice catch!

Your understanding is correct except for a minor detail. The equality $e^{-i A \phi} = \cos(\phi)I - i \sin(\phi)A$ holds iff $A^{2m} = I$ for $m \in \mathbb{Z}$. We also require $A$ to be Hermitian if we want the $e^{-i A \phi}$ to be unitary.

As for the rest, you didn't miss anything (except maybe your computation of $e^{-i |x\rangle \langle x|\Delta t}$ is not correct as well). But, yes, it seems that the book has a typo. We could also verify that this is a typo using a slightly different approach without explicitly trying to compute $e^{-i |x\rangle \langle x|\Delta t}$.

Note that the evolution of $|\psi\rangle$ over small time interval $\Delta t$ can be approximated by the following relation: $$|\psi(\Delta t)\rangle = \left(I - i \Delta t H + O(\Delta t^2)\right) |\psi(0)\rangle.$$ The above relation can be derived directly using the Schrodinger equation.

Now, in our case, the initial state is $|\psi(0)\rangle = |\psi\rangle$ so we can write $$|\psi_1\rangle = \left(I - i \Delta t H + O(\Delta t^2)\right) |\psi\rangle$$ where $|\psi_1\rangle$ is the state $|\psi\rangle$ after the time $\Delta t$.

Given that $H = |x\rangle \langle x|$ we get: \begin{align} |\psi_1\rangle &\approx (I - i \Delta t |x\rangle \langle x| ) |\psi\rangle \\ &= |\psi\rangle - i \Delta t|x\rangle \langle x|\psi\rangle \\ &= \frac{1}{\sqrt{N}}\sum_{y}|y\rangle- i \Delta t|x\rangle \langle x |\frac{1}{\sqrt{N}}\sum_{y}|y\rangle \\ &= \frac{1}{\sqrt{N}}\sum_{y}|y\rangle- i \Delta t |x\rangle \frac{1}{\sqrt{N}}\\ &= \frac{1}{\sqrt{N}}\left [\sum_{y \neq x}|y\rangle + |x\rangle - i \Delta t |x\rangle \right]\\ &=\frac{1}{\sqrt{N}}\left [\sum_{y \neq x}|y\rangle + \color{red}{(1 - i \Delta t)} |x\rangle \right].\\ \end{align} Note that for $\Delta t$ small, we have $\color{red}{1 - i \Delta t} \approx \cos(\Delta t) - i \sin(\Delta t) = e^{-i\Delta t}$.

So even if we consider the evolution of $|\psi\rangle$ over an infinitesimal time period $\Delta t$ without making use of a unitary operator $e^{-i |x\rangle \langle x| \Delta t}$ we see that the term $|x\rangle$ picks up a relative phase which is $e^{-i\Delta t}$.

  • $\begingroup$ Thanks for mentioning the error in the calculation for $e^{-i|x\rangle\langle x|\Delta t}$. I have edited it, hope it is fine now ? $\endgroup$
    – Sooraj S
    Jul 22, 2022 at 14:42
  • $\begingroup$ Nice! Thanks for for doing this. $\endgroup$
    – MonteNero
    Jul 22, 2022 at 18:19
  • $\begingroup$ $e^{-i|x\rangle\langle x|\Delta t}=e^{-i\Delta t}|x\rangle\langle x|$ where $e^{-i|x\rangle\langle x|\Delta t}$ is unitary since $e^{-i|x\rangle\langle x|\Delta t}.(e^{-i|x\rangle\langle x|\Delta t})^\dagger=I$, but $e^{-i\Delta t}|x\rangle\langle x|.(e^{-i\Delta t}|x\rangle\langle x|)^\dagger=e^{-i\Delta t}|x\rangle\langle x|.e^{i\Delta t}|x\rangle\langle x|=|x\rangle\langle x|\neq I$, looks like $e^{-i\Delta t}|x\rangle\langle x|$ is not unitary. Is it not a contradiction? $\endgroup$
    – Sooraj S
    Jul 27, 2022 at 13:29
  • $\begingroup$ The first term in the Taylor expansion is $I$ so you can't factor out $|x\rangle\langle x|$ from the expansion. $\endgroup$
    – MonteNero
    Jul 27, 2022 at 19:50
  • 1
    $\begingroup$ I believe the unitary matrix is $I + (e^{- it}-1)H$ where $H$ is the $|x \rangle \langle x |$. $\endgroup$
    – MonteNero
    Jul 27, 2022 at 20:40

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.