4

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).$$


Only top voted, non community-wiki answers of a minimum length are eligible