Strongly Entangling Layers

1. 1
   Step 1:

   $$V=\begin{pmatrix}a&b\\c&d\end{pmatrix},\quad V^\dagger V=I\iff\lvert a\rvert^2+\lvert c\rvert^2=1,\ \ \lvert b\rvert^2+\lvert d\rvert^2=1,\ \ \bar ab+\bar cd=0$$

   The entries of $V^\dagger V$ are the inner products $\langle v_j,v_k\rangle=\sum_m\overline{(v_j)_m}(v_k)_m$ of the columns $v_0=(a,c)$, $v_1=(b,d)$; unitarity says the columns are orthonormal.
2. 2
   Step 2:

   $$\big\langle(a,c),(-\bar c,\bar a)\big\rangle=\bar a(-\bar c)+\bar c\,\bar a=0,\qquad\lVert(-\bar c,\bar a)\rVert^2=\lvert c\rvert^2+\lvert a\rvert^2=1$$

   An explicit unit vector orthogonal to the first column.
3. 3
   Step 3:

   $$\dim_{\mathbb C}\{v\in\mathbb C^2:\langle v_0,v\rangle=0\}=2-1=1\ \Rightarrow\ (b,d)=t\,(-\bar c,\bar a),\quad t\in\mathbb C$$

   The orthogonal complement of the non-zero vector $v_0$ is the kernel of the non-zero linear functional $v\mapsto\langle v_0,v\rangle$, hence one-dimensional and spanned by $(-\bar c,\bar a)$.
4. 4
   Step 4:

   $$\det V=ad-bc=a\,t\,\bar a-(-t\,\bar c)\,c=t\big(\lvert a\rvert^2+\lvert c\rvert^2\big)=t$$

   Substitute $b=-t\bar c$ and $d=t\bar a$ and use the normalisation of the first column.
5. 5
   Step 5:

   $$\det V=1\ \Rightarrow\ t=1\ \Rightarrow\ V=\begin{pmatrix}a&-\bar c\\c&\bar a\end{pmatrix}=:\begin{pmatrix}p&-\bar q\\q&\bar p\end{pmatrix}$$

   This proves the "only if" direction with $p=a$, $q=c$.
6. 6
   Step 6:

   $$\begin{pmatrix}\bar p&\bar q\\-q&p\end{pmatrix}\begin{pmatrix}p&-\bar q\\q&\bar p\end{pmatrix}=\begin{pmatrix}\lvert p\rvert^2+\lvert q\rvert^2&-\bar p\bar q+\bar q\bar p\\-qp+pq&\lvert q\rvert^2+\lvert p\rvert^2\end{pmatrix}=I,\qquad\det=\lvert p\rvert^2+\lvert q\rvert^2=1$$

   The "if" direction: direct multiplication and the determinant $p\bar p-(-\bar q)q$.

∎

1. 1
   Step 1:

   $$\lvert\det U\rvert^2=\det(U^\dagger)\det(U)=\det(U^\dagger U)=1\ \Rightarrow\ \det U=e^{2i\alpha}\ \text{for some }\alpha\in\mathbb R$$

   Multiplicativity of the determinant and $\det U^\dagger=\overline{\det U}$.
2. 2
   Step 2:

   $$V:=e^{-i\alpha}U:\qquad V^\dagger V=U^\dagger U=I,\qquad\det V=\big(e^{-i\alpha}\big)^2\det U=e^{-2i\alpha}e^{2i\alpha}=1$$

   A scalar factor $\lambda$ multiplies the determinant of a $2\times2$ matrix by $\lambda^2$ and leaves unitarity intact when $\lvert\lambda\rvert=1$. Hence $V\in SU(2)$.
3. 3
   Step 3:

   $$V=\begin{pmatrix}p&-\bar q\\q&\bar p\end{pmatrix},\qquad\lvert p\rvert^2+\lvert q\rvert^2=1$$

   The lemma on the matrices of $SU(2)$.
4. 4
   Step 4:

   $$\gamma:=2\arctan\!2\big(\lvert q\rvert,\lvert p\rvert\big)\in[0,\pi]\ \Rightarrow\ \lvert p\rvert=\cos\tfrac\gamma2,\ \lvert q\rvert=\sin\tfrac\gamma2;\qquad p=\cos\tfrac\gamma2\,e^{i\lambda},\ \ q=\sin\tfrac\gamma2\,e^{i\kappa}$$

   The point $(\lvert p\rvert,\lvert q\rvert)$ lies on the quarter of the unit circle with non-negative coordinates, so it is $(\cos\frac\gamma2,\sin\frac\gamma2)$ for a unique $\frac\gamma2\in[0,\frac\pi2]$. The phases $\lambda=\arg p$ and $\kappa=\arg q$ are arbitrary when the modulus vanishes.
5. 5
   Step 5:

   $$R_Z(\beta)R_Y(\gamma)R_Z(\delta)=\begin{pmatrix}e^{-i(\beta+\delta)/2}\cos\frac\gamma2&-e^{-i(\beta-\delta)/2}\sin\frac\gamma2\\e^{i(\beta-\delta)/2}\sin\frac\gamma2&e^{i(\beta+\delta)/2}\cos\frac\gamma2\end{pmatrix}$$

   The explicit matrix of $\mathrm{Rot}$ with $\phi=\delta$, $\theta=\gamma$, $\omega=\beta$.
6. 6
   Step 6:

   $$\beta:=\kappa-\lambda,\quad\delta:=-\kappa-\lambda\ \Rightarrow\ -\tfrac{\beta+\delta}2=\lambda,\qquad\tfrac{\beta-\delta}2=\kappa$$

   Two linear equations for the two unknown angles: $\beta+\delta=-2\lambda$ and $\beta-\delta=2\kappa$.
7. 7
   Step 7:

   $$R_Z(\beta)R_Y(\gamma)R_Z(\delta)=\begin{pmatrix}\cos\frac\gamma2e^{i\lambda}&-\sin\frac\gamma2e^{-i\kappa}\\\sin\frac\gamma2e^{i\kappa}&\cos\frac\gamma2e^{-i\lambda}\end{pmatrix}=\begin{pmatrix}p&-\bar q\\q&\bar p\end{pmatrix}=V$$

   Substitute the two phase relations entry by entry; $\overline{e^{i\kappa}}=e^{-i\kappa}$ and $\overline{e^{i\lambda}}=e^{-i\lambda}$.
8. 8
   Step 8:

   $$U=e^{i\alpha}V=e^{i\alpha}R_Z(\beta)R_Y(\gamma)R_Z(\delta)=e^{i\alpha}\,\mathrm{Rot}(\delta,\gamma,\beta)$$

   Undo the phase. For $U\in SU(2)$ we have $e^{2i\alpha}=1$, so $e^{i\alpha}=\pm1$; the sign $-1$ is absorbed by $R_Y(\gamma+2\pi)=-R_Y(\gamma)$, giving $U=\mathrm{Rot}(\delta,\gamma+2\pi,\beta)$. Together with $\mathrm{Rot}\in SU(2)$ this proves $\{\mathrm{Rot}\}=SU(2)$.
9. 9
   Step 9:

   $$\big(e^{i\alpha}V\big)_i\otimes I_{\text{rest}}=e^{i\alpha}\,\big(V_i\otimes I_{\text{rest}}\big)$$

   On a register, a phase on one tensor factor is a global phase of the whole state, which no measurement detects. A column of $\mathrm{Rot}$ gates therefore realises every product of single-qubit unitaries $U_0\otimes\cdots\otimes U_{n-1}$ up to an unobservable phase.

∎

1. 1
   Step 1:

   $$(i+r)\bmod n=i\iff r\equiv0\pmod n$$

   A CNOT needs two distinct wires. If $r$ is a multiple of $n$, every "gate" $\mathrm{CNOT}(i,i)$ has control equal to target and is undefined; otherwise no wire is paired with itself.
2. 2
   Step 2:

   $$(i+r+n)\bmod n=(i+r)\bmod n$$

   Only $r\bmod n$ enters the block, and the non-zero residues are exactly $1,\dots,n-1$. In particular $r=n$ is the excluded residue $0$.
3. 3
   Step 3:

   $$\ell=0,1,\dots,n-2:\ r_\ell=\ell+1;\qquad\ell=n-1:\ r_\ell=0+1=1;\qquad r_{\ell+(n-1)}=r_\ell$$

   $\ell\bmod(n-1)$ runs through $0,\dots,n-2$ periodically with period $n-1$, so the range runs through $1,\dots,n-1$ and starts again. For $n=2$ every layer has $r_\ell=1$.
4. 4
   Step 4:

   $$i\mapsto(i+r)\bmod n\ \text{is a bijection of }\mathbb Z_n\ \Rightarrow\ \text{every wire has degree }2\text{ in the multigraph of }B_r$$

   Wire $i$ is the control of edge $\{i,i+r\}$ and the target of edge $\{i-r,i\}$. A finite multigraph in which every vertex has degree $2$ is a disjoint union of cycles.
5. 5
   Step 5:

   $$\text{orbit of }c:\ \{c+kr\bmod n:k\in\mathbb Z\}=c+g\mathbb Z_n,\qquad\lvert c+g\mathbb Z_n\rvert=\frac ng$$

   The subgroup of $\mathbb Z_n$ generated by $r$ is generated by $g=\gcd(n,r)$ (Bézout: $g=ar+bn$), so the orbits are the $g$ cosets of $g\mathbb Z_n$, each with $n/g$ elements. For $\gcd(n,r)=1$ there is a single cycle through all $n$ wires.
6. 6
   Step 6:

   $$n=3:\ r=1:\ \{0,1\},\{1,2\},\{2,0\};\qquad r=2:\ \{0,2\},\{1,0\},\{2,1\}$$

   For $n=3$ both blocks consist of the three edges of the triangle; they differ in the direction of the CNOTs and in the order in which the edges are applied, which the $\mathbb F_2$ analysis below makes precise. If $n/g=2$ (i.e. $r=n/2$), each cycle is a pair $\{i,i+n/2\}$ carrying the two CNOTs $\mathrm{CNOT}(i,i+\frac n2)$ and $\mathrm{CNOT}(i+\frac n2,i)$.

∎

1. 1
   Step 1:

   $$\#w=\sum_{\ell=0}^{L-1}\sum_{i=0}^{n-1}3=3nL,\qquad\#\text{rotations}=3\cdot\#\mathrm{Rot}=3nL$$

   One $\mathrm{Rot}$ gate with three independent angles per wire and layer; it is emitted as three rotations.
2. 2
   Step 2:

   $$\#\mathrm{CNOT}=\sum_{\ell=0}^{L-1}\#\{i:0\le i\le n-1\}=nL\quad(n\ge2)$$

   Every block has one CNOT per wire $i$, including the wrap-around gate $\mathrm{CNOT}(n-1,(n-1+r)\bmod n)$; the HEA ladder has only $n-1$ CNOTs because it does not close the cycle.
3. 3
   Step 3:

   $$n=3:\ \text{any two edges of the triangle share a wire}\ \Rightarrow\ \mathrm{depth}(B_r)=3$$

   Gates sharing a wire cannot be in the same moment, so the three CNOTs of a block occupy three consecutive moments.
4. 4
   Step 4:

   $$\mathrm{depth}(W_\ell)=3+3=6,\qquad\mathrm{depth}(W)=6L$$

   Three moments for $R_Z,R_Y,R_Z$ on all wires, three for the block. Layers do not overlap: if a block ends at moment $T$, the two wires of its last CNOT are busy until $T$, and any pair of the three wires contains one of them. The first CNOT of the next block therefore waits for three rotations after $T$ and runs at $T+4$, and its two successors follow at $T+5$ and $T+6$, because the edges of the triangle pairwise share a wire.
5. 5
   Step 5:

   $$(x_0,x_1)\xrightarrow{\mathrm{CNOT}(0,1)}(x_0,\,x_0\oplus x_1)\xrightarrow{\mathrm{CNOT}(1,0)}\big(x_0\oplus(x_0\oplus x_1),\,x_0\oplus x_1\big)=(x_1,\,x_0\oplus x_1)$$

   For $n=2$ the range is $r=1$ and the block is $\mathrm{CNOT}(0,1)$ followed by $\mathrm{CNOT}(1,0)$; $x_0\oplus x_0=0$. This is the visible test of the lab: two of the three CNOTs of a SWAP.

∎

1. 1
   Step 1:

   $$\mathrm{CNOT}(c,t)\lvert x\rangle=\lvert x'\rangle,\qquad x'_t=x_t\oplus x_c,\quad x'_k=x_k\ (k\ne t)$$

   $\mathrm{CNOT}(c,t)=\lvert0\rangle\langle0\rvert_c\otimes I_t+\lvert1\rangle\langle1\rvert_c\otimes X_t$ flips the target bit exactly when the control bit is $1$, i.e. adds $x_c$ to $x_t$ modulo $2$.
2. 2
   Step 2:

   $$(E_{tc}x)_t=x_t+x_c,\qquad(E_{tc}x)_k=x_k\ (k\ne t)\ \Rightarrow\ x'=E_{tc}x$$

   Row $t$ of $E_{tc}$ has ones in columns $t$ and $c$, every other row is a row of the identity. Multiplying by $E_{tc}$ adds row $c$ of a matrix to row $t$: the elementary row operation $\mathrm{row}_t\leftarrow\mathrm{row}_t+\mathrm{row}_c$.
3. 3
   Step 3:

   $$E_{tc}^2=I+2\,e_te_c^\top+e_t\big(e_c^\top e_t\big)e_c^\top=I+0+0=I$$

   In $\mathbb F_2$, $2=0$, and $e_c^\top e_t=0$ because $c\ne t$. Hence every CNOT is its own inverse, as a matrix over $\mathbb F_2$ and as a unitary.
4. 4
   Step 4:

   $$B\lvert x\rangle=g_{m-1}\cdots g_1\lvert E_{t_0c_0}x\rangle=\cdots=\lvert E_{t_{m-1}c_{m-1}}\cdots E_{t_0c_0}x\rangle=\lvert Ax\rangle$$

   Induction over the gates: each gate maps a basis state to a basis state and multiplies the current label from the left by its elementary matrix; later gates stand further to the left.
5. 5
   Step 5:

   $$A\cdot E_{t_0c_0}\cdots E_{t_{m-1}c_{m-1}}=E_{t_{m-1}c_{m-1}}\cdots E_{t_0c_0}E_{t_0c_0}\cdots E_{t_{m-1}c_{m-1}}=I$$

   The innermost pair $E_{t_0c_0}E_{t_0c_0}=I$ cancels, then the next pair, and so on. Thus $A$ is invertible, $x\mapsto Ax$ is a bijection of $\mathbb F_2^n$, and $B$ is a permutation matrix.

∎