Nielsen and Chuang, Exercise 6.12: How to simulate the specific Hamiltonian in the search algorithm by the Oracle gates?

Question

In Chapter 6 of "Quantum Computation and Quantum Information" Textbook by Nielsen and Chuang, Exercise 6.12:

Exercise 6.12: (Alternative Hamiltonian for quantum search) Suppose: $$H=|x\rangle\langle ψ|+|ψ\rangle\langle x|$$ (1) Show that it takes time $\mathcal O(1)$ to rotate from the state $|ψ\rangle$ to the state $|x\rangle$, given an evolution according to the Hamiltonian $H$.
(2) Explain how a quantum simulation of the Hamiltonian $H$ may be performed, and determine the number of oracle calls your simulation technique requires to obtain the solution with high probability.

(1) It is ease to get the answer for the first (1) part of the question: $$e^{-itH}=e^{-it(|x\rangle\langleψ|+|ψ\rangle\langle x|)}=e^{-it(λ_1|m_1\rangle\langle m_1|+λ_2|m_2\rangle\langle m_2|)}$$

where $λ_1$ and $λ_2$ - eigenvalues of $H$: $λ_{1,2} = α±1,$

$α = \langle x|ψ\rangle=1/\sqrt{N}$ and eigenvalues

$$m_1=\frac{1}{\sqrt{2(1+α)}}(|x\rangle+|ψ\rangle)$$ $$m_2=\frac{1}{\sqrt{2(1-α)}}(|x\rangle-|ψ\rangle)$$

therefore $e^{-itH}=(e^{-it(α+1)}-1)|m_1\rangle\langle m_1|+(e^{-it(α-1)}-1)|m_2\rangle\langle m_2|+1$

$$e^{-itH}|ψ\rangle=e^{-itα}(-i\sin(t)|x\rangle+\cos(t)|ψ\rangle)$$

in order to have $e^{-itH}|ψ\rangle=|x\rangle$, $t$ should be equal to $$t=\pi/2$$

(2) Unfortunately i was unable to find an answer to the second part of the question. Could anybody help me?

It is well-known how the quantum simulation of the several Hamiltonian can be performed. For example:

For the Hamiltonian $H=|x\rangle\langle x|+|ψ\rangle\langle ψ|$ the quantum simulation exist in the Nielsen and Chuang Textbook - page 258 paragraph 6.2 and in the article of Farhi and Gutmann An analog analogue of a digital quantum computation. Phys. Rev. A, 57(4):2403–2406, 1998 arXiv e-print quant-ph/9612026

For the Hamiltonian $H=2iα(|x\rangle\langle ψ|-|ψ\rangle\langle x|)$ the quantum simulation described in the article of Stephen A. Fenner An intuitive Hamiltonian for quantum search May 2000 ArXiv

But for the Hamiltonian $H=|x\rangle\langle ψ|+|ψ\rangle\langle x|)$ I found only the general description of the possibility to use it in the quantum search Generalized Quantum Search Hamiltonian. Joonwoo Bae, Younghun Kwon. arXiv:quant-ph/0110020 and didn't find the answer how the quantum simulation can be performed.

Can anybody have an ideas how the last Hamiltonian can be simulated using Oracle quantum gate?

Answer 1

I assume this is not what was intended, but here's one method:

You already know that you can approximately make $H'=2i\alpha(|x\rangle\langle\psi|-|\psi\rangle\langle x|)$ by using products of terms such as $e^{i\delta|x\rangle\langle x|}$ and $e^{i\delta|\psi\rangle\langle \psi|}$. So, we could simply convert $H'$ into $H$: $$ e^{i\pi/2|\psi\rangle\langle \psi|}e^{iH't}e^{-i\pi/2|\psi\rangle\langle \psi|}=e^{e^{i\pi/2|\psi\rangle\langle \psi|}iH'te^{-i\pi/2|\psi\rangle\langle \psi|}}. $$ So, let's consider just the exponent: $$ e^{i\pi/2|\psi\rangle\langle \psi|}H'e^{-i\pi/2|\psi\rangle\langle \psi|}. $$ The term $e^{i\pi/2|\psi\rangle\langle \psi|}$ has the effect $$ e^{i\pi/2|\psi\rangle\langle \psi|}|\psi\rangle=i|\psi\rangle, $$ while it has no effect on any other (orthogonal) state. If we ignore terms of $O(\alpha)$, we can neglect the overlap between $|\psi\rangle$ and $|x\rangle$, so $$ e^{i\pi/2|\psi\rangle\langle \psi|}|x\rangle\approx|x\rangle. $$ Hence, the transformation on $H'$ is $$ H'\rightarrow2i\alpha(-i|x\rangle\langle\psi|-i|\psi\rangle\langle x|)=2\alpha(|x\rangle\langle\psi|+|\psi\rangle\langle x|), $$ exactly as we need (to $O(\alpha^2)$).

Answer 2

Probably i found an additional solution: $$e^{-itH}=e^{-it(|x\rangle\langle \psi|+|\psi\rangle\langle x|)}=e^{-it(\alpha I+\sqrt{1-\alpha^2}X+\alpha Z)}=e^{-it\alpha}e^{-it(\sqrt{1-\alpha^2}X+\alpha Z)}$$ where we put the calculation basis through $|x\rangle$ and $|\psi\rangle$

the last exponent express the rotation on the Bloch sphere around vector $(\sqrt{1-\alpha^2},0,\alpha)$. It means that Hamiltonian $H$ express the same rotation on the Bloch sphere.

On other hand $$e^{-itH_1}=e^{-it(|x\rangle\langle x|+|\psi\rangle\langle \psi|)}=e^{-it(I+\alpha\sqrt{1-\alpha^2} X+\alpha^2 Z)}=e^{-it}e^{-it\alpha(\sqrt{1-\alpha^2}X+\alpha Z)}$$ where we see rotation around the same vector $(\sqrt{1-\alpha^2},0,\alpha)$.

It means that Hamiltonian $H$ can be simulated by using $H_1$, but $H_1$ can be simulated by using products of terms such as $e^{i\delta|x\rangle\langle x|}$ and $e^{i\delta|\psi\rangle\langle \psi|}$ (see Nielsen and Chuang Textbook p258)