Hamiltonian Simulation Circuit for Grover's Search

Question

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 ?

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