How to implement the exponential of an outer product?

In exercise 6.7 page 258 in Nielsen and Chuang book, they have a Hamiltonian $$H = \left| x \right\rangle \!\!\left\langle x \right| + \left| \psi \right\rangle \!\!\left\langle \psi \right|$$ and the purpose is implementing $$\exp(-iHt)\left| \psi \right\rangle$$, where $$\left| \psi \right\rangle = \frac{\sum_{x}\left| x \right\rangle}{\sqrt N}$$.

Regarding the first part of the Hamiltonian, I couldn't understand how I can figure out the circuit implementation (the gates) for the operator $$\exp(-i \left| x \right\rangle \!\!\left\langle x \right| \Delta t)$$.

In the book, they implement it as: Could you please explain to me that circuit, and how they come out with it?

And what the oracle contains? an example with 4-qubits ($$exp(-i \left| 0101 \right\rangle \left\langle 0101 \right| \Delta t)$$) or else, would be too helpful.

And thank you.

Firstly let's use Taylor series (I will write $$t$$ instead of $$\Delta t$$):

$$\begin{equation} e^{-i |x \rangle \langle x | t} = I + (-i |x \rangle \langle x | t) + \frac{(-i |x \rangle \langle x | t)^2}{2!} + \frac{(-i |x \rangle \langle x | t)^3}{3!} ... = \\ = \left( I + (-i t) + \frac{(-i t)^2}{2!} + \frac{(-i t)^3}{3!} ... \right) |x \rangle \langle x | + I(1 - |x \rangle \langle x|) = \\ = I + (e^{-it} - 1) |x \rangle \langle x | \end{equation}$$

So the circuit should implement the operator $$I + (e^{-it} - 1) |x \rangle \langle x |$$.

Now what does the Oracle (from the M. Nielsen and I. Chuang textbook):

$$|x\rangle |q\rangle \xrightarrow[]{\text{O}} |x\rangle |q \oplus f(x)\rangle$$

So, if $$|q\rangle = |0\rangle$$ as mentioned in the circuit, and note that $$f(x) = 1$$ only if $$x$$ is a solution, otherwise $$f(x) = 0$$. The operator that corresponds to the Oracle (here I am assuming (also assumed in the book) that we have only one solution):

$$O = \sum_{y \ne x} |y\rangle \langle y| I + |x\rangle \langle x| X = II + |x\rangle \langle x| (X - I)$$

Let's see what the combined action looks like (the phase gate is denoted as $$P$$ and $$II \equiv I$$):

$$\begin{equation} O \: I \cdot P \: O = \left[ I + |x\rangle \langle x| (X - I) \right] I \cdot P \left[ I + |x\rangle \langle x| (X - I) \right]= \\ = I \cdot P + |x\rangle \langle x| P(X - I) + |x\rangle \langle x| (X - I) P +|x\rangle \langle x| (X - I) P (X - I) = \\ = I \cdot P - |x\rangle \langle x| P + e^{it}|x\rangle \langle x| P^{\dagger} \end{equation}$$

because $$XPX = e^{it}P^{\dagger}$$. Let's take into account that the ancillary qubit starts in the $$|0 \rangle$$ state, then the combined operator will look like (by omitting the $$P$$ and $$P^{\dagger}$$ applyied on the ancillary qubit, because they do noting on the $$|0 \rangle$$ state and thus the ancillary qubit is "out of the game"):

$$\begin{equation} I - |x\rangle \langle x| + e^{it}|x\rangle \langle x| = I + (e^{it} - I)|x\rangle \langle x| \end{equation}$$

How one can see there is the inconsistency of $$-$$ sign in the phase like in this answer to the related question, because, maybe I did a mistake, or perhaps, there is a typo in the book. Now let's draw an example when $$|x\rangle = |0101\rangle$$ (I will show the simplest example: the implementations can be different depending on what we want to find with Grover, but one thing should be the same: in all cases $$|0101\rangle$$ should be a solution): where the leftmost qubit in $$|0101\rangle$$ corresponds to the first wire. The circuit is drawn with quirk. The way of implementing the Oracle shown above more explicitly can be understood from this answer about black and white dots in the circuit and this answer about multi-controlled gates.

• Thank you @Davit Khachatryan for this elegant answer! May 11 '20 at 19:08

When exponentiating a diagonal matrix, you get a new diagonal matrix where the diagonals are exponentiated.

If the matrix: $$-i|x\rangle\langle x|\Delta t$$ = $$\textrm{diag}(0,i\Delta t)$$, the matrix exponential is $$\textrm{diag}(e^0,e^{i\Delta t})$$ as shown in the 2x2 gate in the figure you showed. You do not need "oracles" to do matrix exponentiation, and the fact that the ones in your diagram take several qubits as input, not just one, indicates to me that they have nothing to do with the matrix exponentiation but probably are related to some other part of the problem.

For your 4-qubit example, write down the diagonal matrix and then exponentiate the diagonals. You will get 15 elements being $$e^0=1$$, and you will get $$e^{-i\Delta t}$$ for the other element, depending on how you define $$|0101\rangle$$ (the way I have defined it, there is no negative sign, so that's why I have a negative sign in my exponential, while your diagram did not).

• Thank you for answering! In the book, they describe the figure as "Circuit implementing the operation exp(−i|x⟩⟨x|Δt) using two oracle calls". May 8 '20 at 22:47
• I think that the oracle is needed in case of more than one qubit, and the 2by2 is always in the last qubit, I believe that both are part of the exp(−i|x⟩⟨x|Δt). If I'm misleading somewhere pls correct me :) May 8 '20 at 23:15
• @walid I don't think you need those multi-qubit oracles to do a matrix exponential. Any matrix H can be exponentiated using for example the MATLAB command expm(H). This just gives a new matrix which is exactly the same size as H. There is no need for any "oracles". May 8 '20 at 23:47
• I'm not 100% sure what the best gates to use would be, but I think CNOT and $\pi/8$ would not be enough, because one of the elements of the 16x16 matrix will be $e^{-i\Delta t}$ ... whereas CNOT has only {0,1} and pi/8 has pi/8 specifically (not the variable $\Delta t$ which can be anything). May 9 '20 at 0:04
• It depends on what you want to do. You are correct that it appears your matrix exponential can be written in terms of pi/8 and some 1-qubit identity operations for the special case where the change in time $\Delta t$ is exactly pi/4. It will not work for other values of $\Delta t$ though, but I suppose you can add some phase-rotation gate to change the factor. May 9 '20 at 0:16