# Tag Info

Remember that we're not told what function $f$ is being implemented by this circuit, it is simply claimed that $f(x)=f(y)$ if and only if $y=x$ or $x\oplus 11=\bar{x}$. So, we need to identify what the function is, and then we can verify if it has that property. The first thing we observe is that, actually, it's just a one-bit function repeated twice - the ...
Note: $I_k$ is unit matrix of order $k$ in the following text. First step of the algorithm is $H \otimes H \otimes I_2 \otimes I_2$ as you mentioned. A controlled gate $U$ with $n$ qubits between the control qubit and the target qubit can expressed as a matrix  CU_{n} = \begin{pmatrix} I_{\frac{N}{2}} & O_{\frac{N}{2}} \\ O_{\frac{N}{2}} & I_{\...