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?
  • $\begingroup$ 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. $\endgroup$ Feb 26, 2021 at 18:00
  • $\begingroup$ 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$. $\endgroup$ Feb 27, 2021 at 14:13
  • $\begingroup$ 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? $\endgroup$ Feb 27, 2021 at 14:14
  • $\begingroup$ related to quantumcomputing.stackexchange.com/q/175/55 (I think) $\endgroup$
    – glS
    Mar 1, 2021 at 20:20


Your Answer

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

Browse other questions tagged or ask your own question.