# Hamiltonian Simulation Circuit for Grover's Search

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 ?

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}$$.

• 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 ? Jul 22, 2022 at 14:42
• Nice! Thanks for for doing this. Jul 22, 2022 at 18:19
• $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? Jul 27, 2022 at 13:29
• The first term in the Taylor expansion is $I$ so you can't factor out $|x\rangle\langle x|$ from the expansion. Jul 27, 2022 at 19:50
• I believe the unitary matrix is $I + (e^{- it}-1)H$ where $H$ is the $|x \rangle \langle x |$. Jul 27, 2022 at 20:40