# In Grover's oracle, how is the matrix $U_f$ derived for a generic $n$?

Grover's algorithm works by iteration of the operator $$\tag{1}G:=U_S^\perp U_f=H^{\otimes n}U_0^\perp H^{\otimes n}.$$ I know how to write down the matrix for $$U_S^\perp$$ (the inversion about the average value of the amplitudes), and also how it is implemented in a circuit (essentially, a CNOT gate between $$X$$ and $$H$$ gates).

But what about $$U_f$$? In the theory, the oracle is defined by its action of the tensor product of the input and output registers as $$\tag{2}U_f|x\rangle |y\rangle=|x\rangle |y\oplus f(x)\rangle,$$ where $$f$$ returns $$0$$ for all input states but for a specified $$x_0$$, in which case it returns $$1$$. But more concretely, I have the following questions:

1. how is the matrix form of $$U_f$$ for a generic $$n$$ derived (specifically for the first few qubits $$n=1,2,3$$), and
2. what does its implementation in a circuit actually look like in terms of fundamental gates?
• Most of the time $f(x)$ is a Boolean function that, thought of classically, could be implemented with a bunch of NAND gates and NOR gates, etc. but thought of quantumly would be implemented with a bunch of reversible CNOT gates/CCNOT gates etc. Building the matrix form of $U_f$ is somewhat akin to writing the truth-table for $f(x)$. Depending on your gate set that you write your circuit from, you may also need a number of ancilla bits in calculating $f(x)$ that will need to be reset prior to the Grover diffusion. Feb 26, 2021 at 18:00
• I think I can answer my first question now. $U_f$ acts as $$U_f(H|0\rangle\otimes |-\rangle)=\frac{1}{\sqrt N}\sum_x (-1)^{f(x)}|x\rangle\otimes |-\rangle=\frac{1}{\sqrt N}(|0...0\rangle+|0...1\rangle+...-|x_0\rangle+...+|1...1\rangle)\otimes |-\rangle,$$ so as it simply adds a negative phase on $|x_0\rangle$ and does nothing to all other qubits it is simply the following diagonal matrix: $$U_f:=\text{diag}(1,...,-1,...,1),$$ where the $-1$ is at position $x_0$. Feb 27, 2021 at 14:13
• As for the circuit implementation, I have seen it for $n=2,3$ in terms of a sequence controlled $Z$ gates. Is this also true in general? Feb 27, 2021 at 14:14
• related to quantumcomputing.stackexchange.com/q/175/55 (I think)
– glS
Mar 1, 2021 at 20:20