# Tag Info

To see that Simon's program is an instance of an (abelian) hidden subgroup problem, we have to identify the group $G$, the subgroup $H$, the set $X$ and the function $f : G \rightarrow X$. Note first that the set $\{ 0,1 \}^n$ of all bit vectors of length $n$ naturally comes with a group structure given by the (component-wise) XOR between bit vectors: $(x_1, ... 3 You could do something like: assume the most significant bit of$s$is 1. write a function that says "if the most significant bit of$x$is 0, return$x$. if the most significant bit of$x$is 1, return$x\oplus s$. This is easily implemented because you start by doing a transversal set of cNOT gates to copy$x$from the input register to the output ... 3 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 ... 2 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_{\... 1 Yes. The tensor product of two linear maps S: V \to X and T: W \to Y is the linear map$$S \otimes T: V \otimes W \to X \otimes Y \ni (v \otimes w) \mapsto S(v) \otimes T(w).$\$