The Search Oracle

Grover's algorithm needs two ingredients: an oracle and a diffuser. The oracle is the piece that "knows" the answer — it marks the target item by giving it a phase of $-1$ while leaving every other state unchanged.

What a phase-flip oracle does

Given a search space of $N = 2^n$ items encoded as $n$ -qubit basis states, the oracle $\mathcal{O}$ acts on a superposition as

\mathcal{O}\,|\psi\rangle = \mathcal{O}\sum_x \alpha_x |x\rangle = \sum_{x \neq x^*} \alpha_x |x\rangle - \alpha_{x^*} |x^*\rangle,

where $x^*$ is the marked item. In matrix language $\mathcal{O}$ is the identity everywhere except for a $-1$ on the diagonal entry corresponding to $|x^*\rangle$ . Because it is diagonal with entries $\pm 1$ , the oracle is its own inverse: $\mathcal{O}^2 = I$ .

Building an oracle by conjugation

Suppose we want to mark $|11\rangle$ in a 2-qubit space. A controlled- $Z$ gate does exactly that:

CZ\,|11\rangle = -|11\rangle, \qquad CZ\,|xy\rangle = |xy\rangle \text{ for } (x,y) \neq (1,1).

Now suppose we want to mark a different state, say $|01\rangle$ . The trick is conjugation by bit-flips: wrap the CZ with $X$ gates on any qubit that should read $0$ in the target. Flipping qubit 0 before and after temporarily turns the condition " $q_0 = 0$ " into " $q_0 = 1$ ", so the CZ fires on $|01\rangle$ instead of $|11\rangle$ :

(X_0 \otimes I_1)\; CZ\; (X_0 \otimes I_1)\;|01\rangle = (X_0 \otimes I_1)\; CZ\;|11\rangle = -(X_0 \otimes I_1)\;|11\rangle = -|01\rangle.

Any state other than $|01\rangle$ picks up no net phase because the CZ never fires on those states. The full oracle for marking $|01\rangle$ is therefore

\mathcal{O}_{01} = (X_0 \otimes I)\; CZ_{01}\; (X_0 \otimes I).

This conjugation pattern generalises to any $n$ -bit target: apply $X$ gates on every qubit that is $0$ in the target, apply a multi-controlled- $Z$ , then undo the $X$ gates.

Try it

Implement the 2-qubit phase-flip oracle that marks $|01\rangle$ . The grader checks the complete unitary matrix of your circuit — doing nothing, or flipping the wrong state, will not pass.

Run your code to see the quantum state.