Quantum Convolutional Neural Networks

1. 1
   Step 1:

   $$T\lvert q_0q_1\cdots q_{m-1}\rangle=\lvert q_{m-2}q_{m-1}q_0\cdots q_{m-3}\rangle,\qquad T\,W_{(i,j)}\,T^\dagger=W_{(i+2,\,j+2)}$$

   $T$ is the cyclic shift by two sites on the ring of active qubits (indices mod $m$), a permutation unitary. Conjugating a two-qubit gate on $(i,j)$ by a permutation moves it to the permuted qubits.
2. 2
   Step 2:

   $$E=\prod_{k=0}^{m/2-1}U_{(2k,\,2k+1)},\qquad O=\prod_{k=0}^{m/2-1}U_{(2k+1,\,2k+2)}$$

   The even and odd sublayers of one convolution layer, all with the same $U$. Inside a sublayer the pairs are disjoint, so the factors commute and their order is irrelevant.
3. 3
   Step 3:

   $$TET^\dagger=\prod_kU_{(2k+2,\,2k+3)}=E,\qquad TOT^\dagger=\prod_kU_{(2k+3,\,2k+4)}=O$$

   Shifting by two maps the set of even pairs onto itself and the set of odd pairs onto itself (indices mod $m$). Because the weights are shared, every shifted factor is again a factor of the same product.
4. 4
   Step 4:

   $$T\,(OE)\,T^\dagger=(TOT^\dagger)(TET^\dagger)=OE$$

   Insert $T^\dagger T=I$ between the two sublayers. The whole convolution layer commutes with $T$, and so does a pooling layer on the pairs $(2k,2k+1)$, by the same argument.
5. 5
   Step 5:

   $$T_1\,E\,T_1^\dagger=\prod_kU_{(2k+1,\,2k+2)}=O\ne E\ \text{in general}$$

   A one-site shift exchanges the sublayers: the layer is translation invariant with a two-site unit cell, like a convolution with stride $2$.

1. 1
   Step 1:

   $$P_{c\to t}(b_0,b_1)=X_c\cdot CR_X(c,t,b_1)\cdot X_c\cdot CR_Z(c,t,b_0)$$

   The time-ordered gates $CR_Z(c,t,b_0)$, $X(c)$, $CR_X(c,t,b_1)$, $X(c)$ written as one matrix product, last gate leftmost.
2. 2
   Step 2:

   $$X_c\big(\lvert0\rangle\langle0\rvert\otimes I+\lvert1\rangle\langle1\rvert\otimes R_X(b_1)\big)X_c=\lvert1\rangle\langle1\rvert\otimes I+\lvert0\rangle\langle0\rvert\otimes R_X(b_1)$$

   $X\lvert0\rangle\langle0\rvert X=\lvert1\rangle\langle1\rvert$ and $X\lvert1\rangle\langle1\rvert X=\lvert0\rangle\langle0\rvert$: sandwiching between two $X$ gates makes the rotation fire on control value $0$.
3. 3
   Step 3:

   $$\big(\lvert0\rangle\langle0\rvert\otimes R_X(b_1)+\lvert1\rangle\langle1\rvert\otimes I\big)\big(\lvert0\rangle\langle0\rvert\otimes I+\lvert1\rangle\langle1\rvert\otimes R_Z(b_0)\big)=\lvert0\rangle\langle0\rvert\otimes R_X(b_1)+\lvert1\rangle\langle1\rvert\otimes R_Z(b_0)$$

   Multiply out; the cross terms contain $\lvert0\rangle\langle0\vert1\rangle\langle1\rvert=0$.
4. 4
   Step 4:

   $$P_{c\to t}(b_0,b_1)=\begin{pmatrix}\cos\frac{b_1}2&-i\sin\frac{b_1}2&0&0\\-i\sin\frac{b_1}2&\cos\frac{b_1}2&0&0\\0&0&e^{-ib_0/2}&0\\0&0&0&e^{ib_0/2}\end{pmatrix}$$

   The explicit $4\times4$ matrix in the basis $\lvert c\,t\rangle=\lvert00\rangle,\lvert01\rangle,\lvert10\rangle,\lvert11\rangle$, using $R_X(b)=\cos\frac b2I-i\sin\frac b2X$ and $R_Z(b)=\mathrm{diag}(e^{-ib/2},e^{ib/2})$.
5. 5
   Step 5:

   $$V_0=R_X(b_1),\qquad V_1=R_Z(b_0)$$

   The form $U=\sum_m\lvert m\rangle\langle m\rvert\otimes V_m$ of the theorem: once $c$ is ignored, the gates implement "measure $c$; if $1$ apply $R_Z(b_0)$ to $t$, if $0$ apply $R_X(b_1)$".

1. 1
   Step 1:

   $$\Phi(\rho)=\mathrm{Tr}_c\big[U\rho U^\dagger\big]=\sum_mK_m\,\rho\,K_m^\dagger,\qquad K_m=\langle m\rvert_c\otimes V_m$$

   Rewrite the pooled state of the theorem with the operators $K_m:\mathbb C^2\otimes\mathbb C^2\to\mathbb C^2$, $K_m\lvert j\rangle\lvert\phi\rangle=\delta_{mj}V_m\lvert\phi\rangle$.
2. 2
   Step 2:

   $$\sum_mK_m^\dagger K_m=\sum_m\lvert m\rangle\langle m\rvert\otimes V_m^\dagger V_m=I_4$$

   Completeness of the Kraus operators: $\Phi$ is trace preserving, and a map of Kraus form is completely positive. Pooling is a quantum channel from two qubits to one.
3. 3
   Step 3:

   $$\mathrm{Tr}\big[O\,\Phi(\rho)\big]=\mathrm{Tr}\big[\Phi^*(O)\,\rho\big],\qquad\Phi^*(O)=\sum_mK_m^\dagger OK_m=\sum_m\lvert m\rangle\langle m\rvert_c\otimes V_m^\dagger OV_m$$

   Cyclicity of the trace defines the dual (Heisenberg-picture) map, which pulls an observable on $t$ back to an observable on $c\otimes t$.
4. 4
   Step 4:

   $$R_X(b)^\dagger ZR_X(b)=\cos b\,Z+\sin b\,Y,\qquad R_Z(b)^\dagger ZR_Z(b)=Z$$

   With $R_X(b)=\cos\frac b2I-i\sin\frac b2X$: $(\cos\frac b2+i\sin\frac b2X)Z(\cos\frac b2-i\sin\frac b2X)=(\cos^2\frac b2-\sin^2\frac b2)Z+2\sin\frac b2\cos\frac b2\,Y$, using $XZX=-Z$ and $ZX=iY$. $R_Z$ commutes with $Z$.
5. 5
   Step 5:

   $$\Phi^*(Z_t)=\lvert0\rangle\langle0\rvert_c\otimes\big(\cos b_1\,Z+\sin b_1\,Y\big)+\lvert1\rangle\langle1\rvert_c\otimes Z$$

   Insert $V_0=R_X(b_1)$ and $V_1=R_Z(b_0)$. The angle $b_0$ has dropped out.
6. 6
   Step 6:

   $$f=\mathrm{Tr}\big[Z_3\,\Phi_{1\to3}(\rho)\big]\ \Rightarrow\ \frac{\partial f}{\partial p_{10}}\equiv0$$

   In the lab, the last pooling $P_{1\to3}(p_{10},p_{11})$ is followed directly by the measurement of $Z_3$, so the output does not depend on $p_{10}$ at all. Only $11$ of the $12$ weights matter. A $Z$ rotation conditioned on the control is invisible to a $Z$ measurement.

Quick check

Quick check

1. 1
   Step 1:

   $$\lvert\Psi_{\ell-1}\rangle=D_\ell\,W_\ell\,\lvert\Psi_\ell\rangle,\qquad W_\ell=\bigotimes w,\quad w\lvert\phi\rangle=u_w\big(\lvert0\rangle\otimes\lvert\phi\rangle\big),\quad w^\dagger w=I$$

   One MERA layer maps a state on $m/2$ sites to a state on $m$ sites. Each isometry is a unitary $u_w$ acting on an ancilla in $\lvert0\rangle$ and an existing qubit, and $D_\ell$ is a brick-wall layer of disentanglers.
2. 2
   Step 2:

   $$W_\ell^\dagger D_\ell^\dagger\lvert\Psi_{\ell-1}\rangle=\lvert\Psi_\ell\rangle$$

   $D_\ell$ is unitary and $W_\ell^\dagger W_\ell=I$. Read in reverse, a layer first applies the unitaries $D_\ell^\dagger$ on neighbouring pairs, which is a convolution layer, and then $u_w^\dagger$ on each pair. For states in the MERA's image the ancilla returns exactly to $\lvert0\rangle$.
3. 3
   Step 3:

   $$\Phi_\ell(\rho)=\mathrm{Tr}_{\text{anc}}\Big[\big(\textstyle\bigotimes u_w^\dagger\big)D_\ell^\dagger\,\rho\,D_\ell\big(\textstyle\bigotimes u_w\big)\Big]$$

   For a general input the ancillas are not exactly $\lvert0\rangle$. Discarding them is a partial trace, so each reversed layer is a channel from $m$ to $m/2$ qubits: a convolution followed by pooling. QCNN pooling is more general than plain discarding, because the conditioned rotation lets the discarded qubit correct its neighbour, the error-correction step of Cong et al.
4. 4
   Step 4:

   $$\rho_\ell=\Phi_\ell(\rho_{\ell-1}),\qquad f=\mathrm{Tr}\big[Z\rho_L\big]=\mathrm{Tr}\big[(\Phi_1^*\circ\cdots\circ\Phi_L^*)(Z)\,\rho_0\big]$$

   Coarse-grained states on $n,n/2,\dots,1$ qubits; in the Heisenberg picture the readout $Z$ is pulled back through the dual maps to an $n$-qubit observable measured on the input.
5. 5
   Step 5:

   $$\Phi_\ell=\Phi\ \ \forall\ell:\qquad\rho_\ell=\Phi^{\ell}(\rho_0),\qquad\rho^\star=\Phi(\rho^\star)$$

   If, in addition, the same weights are used at every level, the network iterates one coarse-graining map: a discrete renormalisation-group (RG) flow. States in the same phase flow to the same fixed point, so a readout that distinguishes fixed points classifies phases. The lab's model uses different weights at its two levels, so it is a general multiscale network rather than a scale-invariant one.

1. 1
   Step 1:

   $$\mathrm{Var}[\partial_\mu C]\ \gtrsim\ \mathrm{Var}_0\cdot\kappa^{\,d_\mu},\qquad0<\kappa<1$$

   Assumption (intuition, not a proof): for a local cost, each of the $d_\mu$ layers of $2$-design blocks between $\theta_\mu$ and the readout reduces the variance by at most a constant factor $\kappa$; Cerezo et al. (2021) prove bounds of this type for local costs in layered circuits.
2. 2
   Step 2:

   $$d_\mu\le1+12\log_2n$$

   Part (c) of the light-cone lemma. In a QCNN every parameter is close to the output, because pooling halves the register at every level.
3. 3
   Step 3:

   $$\kappa^{1+12\log_2n}=\kappa\cdot\big(2^{\log_2\kappa}\big)^{12\log_2n}=\kappa\,n^{-12\log_2(1/\kappa)}$$

   Exponential decay in a depth that is logarithmic in $n$ is polynomial decay in $n$; this is the identity $a^{\log_2n}=n^{\log_2a}$.
4. 4
   Step 4:

   $$\mathrm{Var}[\partial_\mu C]\ \gtrsim\ \mathrm{Var}_0\,\kappa\,n^{-12\log_2(1/\kappa)}\in\Omega\big(1/\mathrm{poly}(n)\big)$$

   The heuristic reproduces the scaling of the theorem. A deep hardware-efficient ansatz with depth $d\propto n$ would instead give $\kappa^{cn}$, an exponential plateau.
5. 5
   Step 5:

   $$\text{global cost: }O=Z^{\otimes n}\ \Rightarrow\ \mathrm{Var}\sim2^{-n}\ \text{even at depth }O(1)$$

   Locality matters too: a global observable has a plateau at any depth, while the QCNN measures one qubit through a narrow light cone (part (a)).

Quick check

1. 1
   Step 1:

   $$E(x)=\bigotimes_{q=0}^{3}R_Y(\pi x_q),\qquad R_Y(\pi x)\lvert0\rangle=\cos\tfrac{\pi x}2\lvert0\rangle+\sin\tfrac{\pi x}2\lvert1\rangle,\quad\langle Z_q\rangle=\cos\pi x_q$$

   Angle encoding of the four pixels $x_q\in[0,1]$ (data parameters x0 to x3). An off pixel ($x\approx0$) gives $\langle Z\rangle\approx1$ and an on pixel ($x\approx1$) gives $\langle Z\rangle\approx-1$.
2. 2
   Step 2:

   $$C_{ij}(a)=\mathrm{CNOT}(j,i)\,\big(R_Y^{(i)}(a_2)\otimes R_Y^{(j)}(a_3)\big)\,\mathrm{CNOT}(i,j)\,\big(R_Y^{(i)}(a_0)\otimes R_Y^{(j)}(a_1)\big)$$

   The convolution block as a matrix product. In time order it is $R_Y(i,a_0)$, $R_Y(j,a_1)$, $\mathrm{CNOT}(i,j)$, $R_Y(i,a_2)$, $R_Y(j,a_3)$, $\mathrm{CNOT}(j,i)$: six gates with four weights.
3. 3
   Step 3:

   $$\mathcal L_1=C_{30}(p_{0..3})\,C_{12}(p_{0..3})\,C_{23}(p_{0..3})\,C_{01}(p_{0..3})$$

   Layer 1 on the ring pairs in the time order $(0,1),(2,3),(1,2),(3,0)$, all with the shared weights $p_0,\dots,p_3$: the even sublayer, then the odd one.
4. 4
   Step 4:

   $$\mathcal Q_1=P_{2\to3}(p_4,p_5)\,P_{0\to1}(p_4,p_5),\qquad P_{c\to t}(b_0,b_1)=\lvert0\rangle\langle0\rvert_c\otimes R_X^{(t)}(b_1)+\lvert1\rangle\langle1\rvert_c\otimes R_Z^{(t)}(b_0)$$

   Pooling layer 1 with the shared weights $p_4,p_5$, each block made of the four gates $CR_Z$, $X$, $CR_X$, $X$. Qubits $0$ and $2$ are not used again, so by the deferred-measurement theorem they are measured and discarded.
5. 5
   Step 5:

   $$\mathcal L_2=C_{13}(p_{6..9}),\qquad\mathcal Q_2=P_{1\to3}(p_{10},p_{11})$$

   Level 2 on the active qubits $(1,3)$. The single convolution acts on all remaining qubits, which makes it the fully connected layer.
6. 6
   Step 6:

   $$f_p(x)=\langle0000\rvert E^\dagger\mathcal L_1^\dagger\mathcal Q_1^\dagger\mathcal L_2^\dagger\mathcal Q_2^\dagger\,Z_3\,\mathcal Q_2\mathcal L_2\mathcal Q_1\mathcal L_1E\lvert0000\rangle,\qquad\hat y=\mathrm{sign}\,f_p(x)$$

   The output $\langle Z_3\rangle$ (Pauli word IIIZ), exactly what the lab's grader evaluates.
7. 7
   Step 7:

   $$4+4\cdot6+2\cdot4+6+4=46\ \text{gates};\qquad p_0..p_3:\ 4\times,\quad p_4,p_5:\ 2\times,\quad p_6..p_{11}:\ 1\times$$

   Gate count and the number of gates in which each weight occurs; these numbers determine the cost of the gradient below.

1. 1
   Step 1:

   $$p=0:\quad R_Y(0)=CR_Z(0)=CR_X(0)=I\ \Rightarrow\ P_{c\to t}=X_cX_c=I,\qquad C_{ij}=\mathrm{CNOT}(j,i)\,\mathrm{CNOT}(i,j)$$

   All rotations become identities; only the CNOT pairs of the convolution blocks remain.
2. 2
   Step 2:

   $$\mathrm{CNOT}(c,t)\,Z_c\,\mathrm{CNOT}(c,t)=Z_c,\qquad\mathrm{CNOT}(c,t)\,Z_t\,\mathrm{CNOT}(c,t)=Z_cZ_t$$

   Heisenberg rule for a CNOT, which is its own inverse: on $\lvert a,b\rangle$ the gate maps the target to $b\oplus a$, so $Z_t$ picks up the sign $(-1)^a$ of the control.
3. 3
   Step 3:

   $$Z_3\ \xrightarrow{\mathrm{CNOT}(3,1)}\ Z_3\ \xrightarrow{\mathrm{CNOT}(1,3)}\ Z_1Z_3$$

   Pull $Z_3$ back through $C_{13}$, last gate first.
4. 4
   Step 4:

   $$Z_1Z_3\ \xrightarrow{\mathrm{CNOT}(0,3)}\ Z_0Z_1Z_3\ \xrightarrow{\mathrm{CNOT}(3,0)}\ Z_0Z_1$$

   Through $C_{30}$: $\mathrm{CNOT}(0,3)$ maps $Z_3\mapsto Z_0Z_3$; then $\mathrm{CNOT}(3,0)$ maps $Z_0\mapsto Z_3Z_0$ and fixes $Z_3$, and $Z_3^2=I$.
5. 5
   Step 5:

   $$Z_0Z_1\ \xrightarrow{\mathrm{CNOT}(2,1)}\ Z_0Z_1Z_2\ \xrightarrow{\mathrm{CNOT}(1,2)}\ Z_0Z_2$$

   Through $C_{12}$: $Z_1\mapsto Z_2Z_1$, then $Z_2\mapsto Z_1Z_2$ and $Z_1^2=I$.
6. 6
   Step 6:

   $$Z_0Z_2\ \xrightarrow{\mathrm{CNOT}(3,2)}\ Z_0Z_2Z_3\ \xrightarrow{\mathrm{CNOT}(2,3)}\ Z_0Z_3$$

   Through $C_{23}$: $Z_2\mapsto Z_3Z_2$, then $Z_3\mapsto Z_2Z_3$ and $Z_2^2=I$.
7. 7
   Step 7:

   $$Z_0Z_3\ \xrightarrow{\mathrm{CNOT}(1,0)}\ Z_0Z_1Z_3\ \xrightarrow{\mathrm{CNOT}(0,1)}\ Z_1Z_3$$

   Through $C_{01}$, the first block in time: $Z_0\mapsto Z_1Z_0$, then $Z_1\mapsto Z_0Z_1$ and $Z_0^2=I$.
8. 8
   Step 8:

   $$f_0(x)=\langle Z_1Z_3\rangle_{E(x)\lvert0000\rangle}=\cos(\pi x_1)\cos(\pi x_3)$$

   The encoded state is a product state, so the expectation value factorises into $\langle Z_1\rangle\langle Z_3\rangle$.
9. 9
   Step 9:

   $$x_{\text{on}}\in[0.75,1)\Rightarrow\cos\pi x\in(-1,-\tfrac{\sqrt2}2],\qquad x_{\text{off}}\in[0,0.25)\Rightarrow\cos\pi x\in(\tfrac{\sqrt2}2,1]$$

   The pixel ranges of the bars dataset.
10. 10
    Step 10:

    $$y=+1\ (\texttt{1100},\texttt{0011}):\ f_0\le-\tfrac12;\qquad y=-1\ (\texttt{1010},\texttt{0101}):\ f_0\ge\tfrac12$$

    In a horizontal bar exactly one of the pixels $q_1,q_3$ is on, so the product is negative. In a vertical bar both or neither are on, so it is positive. Its magnitude is at least $\frac{\sqrt2}2\cdot\frac{\sqrt2}2=\frac12$. Zero weights therefore classify every image with the wrong sign (accuracy $0$), and training must essentially flip this sign.