# Preparation of Grover’s algorithm: How to implement the oracle $U_f$?

In order to understand Grover’s algorithm, we need to be able to implement $$U_f$$ from a black box implementing $$f$$, which we know how to do. Suppose you have this black box

as we can find in some notes, then we want to prove that the following implements $$U_f$$ :

I don’t recognize what does the symbol $$\oplus$$ on the bottom wire mean, it seems like a CNOT gate or a serie of CNOT gates being controlled by the upper wires.

Is there a reference where I can check that this circuit works?

Another question is: why do we call $$U_f$$ an oracle?

The black boxes you have provided are part of Deutsch's Algorithm. The idea of using black box concepts is that you do not need to worry about what is inside. Doing so avoids details that could cause some difficulty at first.

There is no way to calculate $$f(x)$$ directly using a single-qubit quantum gate, so it is necessary to do that indirectly, using a two-qubit quantum gate. The black box you provided accomplishes this. The answer is placed in $$| b \oplus f(a) \rangle$$. Using $$b=0$$ allows $$f(a)$$ to be calculated. This black box is an oracle, we can ask it about solution and it give it to us.

The symbol $$\oplus$$ in the bottom wire is just a NOT gate.

Sometimes an oracle does not know the solution but it recognizes the solution, i.e, it is not capable of providing the solution, but if you ask it about a probable solution, it will recognize it or not.

Suppose $$|01 \rangle$$ is a solution to a problem. You will query the oracle about all probable solutions $$|00 \rangle$$, $$|01 \rangle$$ , $$|10 \rangle$$ and $$|11 \rangle$$, but you will do it only once. The oracle will receive a superposition of the probable solutions: $$\frac{1}{2}\left (|00 \rangle + |01 \rangle + |10 \rangle + |11 \rangle \right)$$ and will make a change to the sought solution. In the case of Grover, the oracle will perform a phase shift: $$\frac{1}{2}\left (|00 \rangle - |01 \rangle + |10 \rangle + |11 \rangle \right)$$ . Some operations will be required later to extract that result.

What is inside the black box ?

How to use this black box in Deustch-Jozsa Algorithm?

If some 1 is measured in the end, the function in the black box is balanced. If only 0's are measured,the function is constant.

• In Deustch's algorithm, the black box can be just the identity matrix, or a cnot gate, it depends on the function f(x). Dec 16, 2023 at 0:19
• Thank you, if this is a NOT gate then why not just write ket 1 instead of ket 0. Then why does the upper qubits become $(-1)^{f(x)}|x\rangle$ ? Dec 16, 2023 at 2:02
• It was a choice of the author. In the page 35 of the Nielsen and Chuang book they do like you said: they wrote ket 1. link Dec 16, 2023 at 3:25
• I think I understand now after also reading from page 249 of N&C, only thing remaining is how do we ‘force’ the output qubit to be ket 0 while it must be $(-1)^{f(x)}$ ket 0. This coefficient is initially attached with the bottom wire, no? Dec 16, 2023 at 16:13
• I added a black box to my answer to try to help you. I suggest you analyze it carefully. Dec 16, 2023 at 20:58