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

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

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?


1 Answer 1


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 ?

example of black box

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

using the black box

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.

  • $\begingroup$ In Deustch's algorithm, the black box can be just the identity matrix, or a cnot gate, it depends on the function f(x). $\endgroup$
    – Hadamard
    Commented Dec 16, 2023 at 0:19
  • $\begingroup$ 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$ ? $\endgroup$
    – NotaChoice
    Commented Dec 16, 2023 at 2:02
  • $\begingroup$ 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 $\endgroup$
    – Hadamard
    Commented Dec 16, 2023 at 3:25
  • $\begingroup$ 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? $\endgroup$
    – NotaChoice
    Commented Dec 16, 2023 at 16:13
  • $\begingroup$ I added a black box to my answer to try to help you. I suggest you analyze it carefully. $\endgroup$
    – Hadamard
    Commented Dec 16, 2023 at 20:58

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.