Why Backpropagation Fails on Quantum Hardware

1. 1
   Step 1:

   $$\frac{\partial L}{\partial\theta_k}=\nabla\ell(x_P)\,\frac{\partial x_P}{\partial x_k}\,\frac{\partial x_k}{\partial\theta_k}$$

   $\theta_k$ enters $L$ only through $x_k=F_k(x_{k-1};\theta_k)$; chain rule for the composition $x_k\mapsto x_{k+1}\mapsto\dots\mapsto x_P$.
2. 2
   Step 2:

   $$\frac{\partial x_P}{\partial x_k}=J_P\,J_{P-1}\cdots J_{k+1},\qquad J_j=\frac{\partial F_j}{\partial x_{j-1}}\Big\rvert_{x_{j-1}}$$

   The chain rule once more; each Jacobian is evaluated at the intermediate value of its own stage.
3. 3
   Step 3:

   $$\bar x_k:=\nabla\ell(x_P)\,J_P\cdots J_{k+1}\ \Rightarrow\ \bar x_P=\nabla\ell(x_P),\quad\bar x_{k-1}=\bar x_k\,J_k$$

   Peel off one factor at a time: multiplying from the left keeps every intermediate a row vector, never a matrix.
4. 4
   Step 4:

   $$\frac{\partial L}{\partial\theta_k}=\bar x_k\,\frac{\partial F_k}{\partial\theta_k}\Big\rvert_{x_{k-1}}$$

   Substitute the definition of $\bar x_k$ into the first line.
5. 5
   Step 5:

   $$\text{cost}(\nabla_\theta L)=\sum_{k=1}^P\text{cost}(\bar x_k\mapsto\bar x_kJ_k)\ \le\ c\cdot\text{cost}(L)$$

   A vector–Jacobian product of stage $k$ costs a bounded multiple of evaluating $F_k$ (the cheap-gradient principle, Griewank and Walther). The Jacobians depend on $x_{k-1}$, which must therefore be stored on the tape or recomputed.

∎

1. 1
   Step 1:

   $$V(\lvert\psi\rangle\lvert s\rangle)=\lvert\psi\rangle\lvert\psi\rangle,\quad V(\lvert\varphi\rangle\lvert s\rangle)=\lvert\varphi\rangle\lvert\varphi\rangle$$

   Assume such a $V$ exists and apply it to two arbitrary states.
2. 2
   Step 2:

   $$\langle\psi\vert\varphi\rangle\langle s\vert s\rangle=\langle\psi\vert\varphi\rangle^2$$

   Take the inner product of the two equations; $V^\dagger V=I$ on the left, and inner products of product states factorise on the right.
3. 3
   Step 3:

   $$\langle\psi\vert\varphi\rangle=\langle\psi\vert\varphi\rangle^2\ \Rightarrow\ \langle\psi\vert\varphi\rangle\in\{0,1\}$$

   $\langle s\vert s\rangle=1$, and $z=z^2$ has the solutions $0$ and $1$.
4. 4
   Step 4:

   $$\lvert\psi\rangle=\lvert0\rangle,\ \lvert\varphi\rangle=\lvert+\rangle:\quad\langle0\vert+\rangle=\tfrac1{\sqrt2}\notin\{0,1\}$$

   Two states that are neither equal nor orthogonal give a contradiction, so no universal cloner exists.

∎

1. 1
   Step 1:

   $$\lVert\psi(x)\rVert^2=1-\lVert x\rVert^2+\sum_{i=1}^dx_i^2=1$$

   The basis $\{\lvert i\rangle\}$ is orthonormal.
2. 2
   Step 2:

   $$\lVert\psi-e^{i\alpha}\varphi\rVert^2=2-2\,\mathrm{Re}\big(e^{i\alpha}\langle\psi\vert\varphi\rangle\big)\ \Rightarrow\ D(\psi,\varphi)^2=2-2\lvert\langle\psi\vert\varphi\rangle\rvert$$

   Expand the squared norm of a difference of unit vectors; the real part is maximal, equal to the modulus, for the optimal phase.
3. 3
   Step 3:

   $$\langle\psi(x)\vert\psi(y)\rangle=\sqrt{1-\lVert x\rVert^2}\sqrt{1-\lVert y\rVert^2}+\sum_ix_iy_i\ \ge\ 0$$

   All amplitudes are real and nonnegative, so the overlap equals its modulus.
4. 4
   Step 4:

   $$D\big(\psi(x),\psi(y)\big)^2=2-2\langle\psi(x)\vert\psi(y)\rangle=\lVert\psi(x)-\psi(y)\rVert^2$$

   For such states the optimal phase is $\alpha=0$: the phase-invariant distance is the plain Euclidean one.
5. 5
   Step 5:

   $$\lVert\psi(x)-\psi(y)\rVert^2=\big(\sqrt{1-\lVert x\rVert^2}-\sqrt{1-\lVert y\rVert^2}\big)^2+\lVert x-y\rVert^2\ \ge\ \lVert x-y\rVert^2$$

   The coordinates $1,\dots,d$ of $\psi(x)$ are those of $x$; the extra coordinate only adds a square.

∎

1. 1
   Step 1:

   $$\lVert x_i-x_j\rVert>\delta\ \Rightarrow\ B(x_i,\tfrac\delta2)\cap B(x_j,\tfrac\delta2)=\varnothing$$

   Choose points greedily, each farther than $\delta$ from all previous ones. The balls of radius $\frac\delta2$ around them are disjoint and lie in the bounded set $\{\lVert x\rVert\le1+\frac\delta2\}$, so the process stops after finitely many points: the set $\{x_1,\dots,x_M\}$ is maximal.
2. 2
   Step 2:

   $$K\subseteq\bigcup_{m=1}^M\bar B(x_m,\delta)$$

   Maximality: a point of $K$ at distance more than $\delta$ from every $x_m$ could still be added.
3. 3
   Step 3:

   $$\mathrm{vol}(K)\le M\,\delta^d\,\mathrm{vol}(B^d)$$

   Subadditivity of volume; a ball of radius $\delta$ in $\mathbb R^d$ has volume $\delta^d\,\mathrm{vol}(B^d)$, with $B^d$ the unit ball.
4. 4
   Step 4:

   $$\mathrm{vol}(K)=2^{-d}\,\mathrm{vol}(B^d)$$

   The unit ball is the union of the $2^d$ reflections of $K$ by sign changes of coordinates, which are congruent and overlap only on coordinate hyperplanes, a set of volume zero.
5. 5
   Step 5:

   $$M\ \ge\ \frac{2^{-d}}{\delta^d}=(2\delta)^{-d}$$

   Combine the last two lines.

∎

1. 1
   Step 1:

   $$\{x_1,\dots,x_M\}\subset K,\quad\lVert x_m-x_{m'}\rVert>3\varepsilon,\quad M\ge(6\varepsilon)^{-d},\qquad\psi_m=\psi(x_m)$$

   The packing lemma with $\delta=3\varepsilon\le\frac12$. By the orthant lemma the states satisfy $D(\psi_m,\psi_{m'})>3\varepsilon$ for $m\ne m'$.
2. 2
   Step 2:

   $$X\sim\mathrm{Unif}\{1,\dots,M\},\qquad\rho_X=\big(\lvert\psi_X\rangle\langle\psi_X\rvert\big)^{\otimes N}\ \xrightarrow{\text{measure}}\ Y\ \longrightarrow\ \hat X=\operatorname*{arg\,min}_mD\big(\hat\psi(Y),\psi_m\big)$$

   Feed the procedure a uniformly random packing state; $Y$ is its complete classical record (an adaptive scheme is one measurement on the $N$ copies), and $\hat X$ rounds its output to the nearest packing state.
3. 3
   Step 3:

   $$D(\hat\psi,\psi_X)\le\varepsilon\ \Rightarrow\ D(\hat\psi,\psi_m)\ge D(\psi_X,\psi_m)-D(\hat\psi,\psi_X)>2\varepsilon\ \ (m\ne X)\ \Rightarrow\ \hat X=X$$

   Triangle inequality for $D$. Hence $\Pr(\hat X\ne X)\le p_e$.
4. 4
   Step 4:

   $$I(X;\hat X)=H(X)-H(X\vert\hat X)\ \ge\ \log_2M-\big(1+p_e\log_2M\big)=(1-p_e)\log_2M-1$$

   Fano's inequality $H(X\vert\hat X)\le h(p_e)+p_e\log_2M$ with the binary entropy $h\le1$, and $H(X)=\log_2M$ for the uniform distribution.
5. 5
   Step 5:

   $$I(X;\hat X)\ \le\ I(X;Y)$$

   Data-processing inequality: $\hat X$ is a function of $Y$.
6. 6
   Step 6:

   $$I(X;Y)\ \le\ S\Big(\frac1M\sum_m\rho_m\Big)-\frac1M\sum_mS(\rho_m)\ \le\ \log_2\dim\big(\mathcal H^{\otimes N}\big)=nN$$

   Holevo's bound for the ensemble $\{\frac1M,\rho_m\}$ (Nielsen and Chuang, Theorem 12.1). Each $\rho_m$ is pure, so $S(\rho_m)=0$, and the entropy of any state of $nN$ qubits is at most $nN$ bits.
7. 7
   Step 7:

   $$nN\ \ge\ (1-p_e)\log_2M-1\ \ge\ (1-p_e)\,(2^n-1)\log_2\tfrac1{6\varepsilon}-1$$

   Chain the inequalities and insert $\log_2M\ge d\log_2\frac1{6\varepsilon}$ with $d=2^n-1$.
8. 8
   Step 8:

   $$\varepsilon\le\tfrac1{36}\ \Rightarrow\ \tfrac1{6\varepsilon}\ge\varepsilon^{-1/2}\ \Rightarrow\ \log_2\tfrac1{6\varepsilon}\ge\tfrac12\log_2\tfrac1\varepsilon$$

   $6\varepsilon\le\varepsilon^{1/2}$ is equivalent to $\varepsilon^{1/2}\le\frac16$. With a fixed $p_e<1$ the bound becomes $\Omega\big(2^n\log(1/\varepsilon)/n\big)$.

∎

1. 1
   Step 1:

   $$\frac{\partial}{\partial\theta_k}e^{-i\theta_kG_k}=\sum_{m\ge1}\frac{m(-iG_k)^m\theta_k^{m-1}}{m!}=-iG_k\,e^{-i\theta_kG_k}$$

   Differentiate the absolutely convergent exponential series term by term; $G_k$ commutes with its own exponential.
2. 2
   Step 2:

   $$\frac{\partial\lvert\phi_P\rangle}{\partial\theta_k}=U_P\cdots U_{k+1}\,(-iG_k)\,U_k\cdots U_1\lvert0\rangle=V_k\,(-iG_k)\lvert\phi_k\rangle,\qquad V_k=U_P\cdots U_{k+1}$$

   Product rule: only the factor $U_k$ depends on $\theta_k$.
3. 3
   Step 3:

   $$\frac{\partial f}{\partial\theta_k}=\langle\partial_k\phi_P\vert H\vert\phi_P\rangle+\langle\phi_P\vert H\vert\partial_k\phi_P\rangle=2\,\mathrm{Re}\,\langle\phi_P\vert H\vert\partial_k\phi_P\rangle$$

   $f=\langle\phi_P\vert H\vert\phi_P\rangle$, and since $H=H^\dagger$ the first term is the complex conjugate of the second.
4. 4
   Step 4:

   $$\langle\phi_P\vert HV_k=\big(V_k^\dagger H\lvert\phi_P\rangle\big)^\dagger=\langle\lambda_k\vert\ \Rightarrow\ \frac{\partial f}{\partial\theta_k}=2\,\mathrm{Re}\,\langle\lambda_k\vert(-iG_k)\vert\phi_k\rangle$$

   $(AB)^\dagger=B^\dagger A^\dagger$ and $H^\dagger=H$; $V_k^\dagger=U_{k+1}^\dagger\cdots U_P^\dagger$ is the definition of $\lvert\lambda_k\rangle$.
5. 5
   Step 5:

   $$V_{k-1}=V_kU_k\ \Rightarrow\ \lvert\lambda_{k-1}\rangle=U_k^\dagger\lvert\lambda_k\rangle,\qquad\lvert\phi_{k-1}\rangle=U_k^\dagger U_k\lvert\phi_{k-1}\rangle=U_k^\dagger\lvert\phi_k\rangle$$

   Unitarity $U_k^\dagger U_k=I$: the forward states are recovered by undoing one gate at a time, so they need not be stored.
6. 6
   Step 6:

   $$\mathrm{Re}(-iz)=\mathrm{Im}\,z\ \Rightarrow\ \frac{\partial f}{\partial\theta_k}=2\,\mathrm{Im}\,\langle\lambda_k\vert G_k\vert\phi_k\rangle\overset{G_k=P/2}{=}\mathrm{Im}\,\langle\lambda_k\vert P\vert\phi_k\rangle$$

   For $z=a+ib$, $-iz=b-ia$. For a Pauli rotation $R_P(\theta)$ the generator is $P/2$; this is the formula used in the code cell.

∎

1. 1
   Step 1:

   $$\text{one gate on }\lvert\phi\rangle\in\mathbb C^{2^n}:\ O(2^n)$$

   A $k$-qubit gate updates the $2^{n-k}$ groups of $2^k$ amplitudes once each.
2. 2
   Step 2:

   $$\lvert\phi_P\rangle:\ P\cdot O(2^n),\qquad\lvert\lambda_P\rangle=\sum_{j=1}^Kc_jP_j\lvert\phi_P\rangle:\ K\cdot O(2^n)$$

   Forward pass gate by gate; a Pauli string permutes the amplitudes and multiplies them by phases.
3. 3
   Step 3:

   $$k=P,\dots,1:\ \ \lvert\mu\rangle=G_k\lvert\phi_k\rangle,\ \ \mathrm{Im}\langle\lambda_k\vert\mu\rangle,\ \ \lvert\phi_{k-1}\rangle=U_k^\dagger\lvert\phi_k\rangle,\ \ \lvert\lambda_{k-1}\rangle=U_k^\dagger\lvert\lambda_k\rangle$$

   Each iteration costs a constant number of $O(2^n)$ operations, $O(P\,2^n)$ in total, and holds only $\phi$, $\lambda$ and the scratch vector $\mu$.
4. 4
   Step 4:

   $$\text{tape}:\ (P+1)\,2^n\ \text{amplitudes};\qquad n=20,\ P=1000:\ 1001\times16\,\text{MiB}\approx15.6\,\text{GiB}\ \text{vs.}\ 3\times16\,\text{MiB}$$

   A complex double occupies $16$ bytes, so one $20$-qubit statevector takes $2^{20}\cdot16$ bytes $=16$ MiB.
5. 5
   Step 5:

   $$(2P+1)\cdot O\big((P+K)\,2^n\big)=O\big(P^2\,2^n\big)\ \text{for}\ K=O(P)$$

   Each of the $2P+1$ shifted circuits is a complete simulation; the adjoint method replaces them by a single backward sweep.

∎

1. 1
   Step 1:

   $$\mathbb E[\hat g_{\mathrm{FD}}]=\frac{f_+-f_-}{2h}$$

   Linearity of expectation and unbiasedness of each evaluation.
2. 2
   Step 2:

   $$\mathrm{Var}[\hat g_{\mathrm{FD}}]=\frac{\mathrm{Var}[\hat f(\theta+h)]+\mathrm{Var}[\hat f(\theta-h)]}{4h^2}=\frac{(1-f_+^2)+(1-f_-^2)}{4h^2N}$$

   For independent $X,Y$: $\mathrm{Var}[aX+bY]=a^2\mathrm{Var}X+b^2\mathrm{Var}Y$, here with $a=-b=\frac1{2h}$.
3. 3
   Step 3:

   $$f(\theta\pm h)=\sum_{j=0}^4\frac{(\pm h)^j}{j!}f^{(j)}(\theta)+\frac{(\pm h)^5}{120}f^{(5)}(\xi_\pm),\qquad\lvert\xi_\pm-\theta\rvert<h$$

   Taylor's theorem with the Lagrange form of the remainder.
4. 4
   Step 4:

   $$f_+-f_-=2hf'(\theta)+\frac{h^3}3f'''(\theta)+\frac{h^5}{120}\big(f^{(5)}(\xi_+)+f^{(5)}(\xi_-)\big)$$

   The even-order terms cancel; the odd ones double, and $\frac{2}{3!}=\frac13$.
5. 5
   Step 5:

   $$\frac{f_+-f_-}{2h}-f'(\theta)=\frac{f'''(\theta)}6h^2+\underbrace{\frac{h^4}{240}\big(f^{(5)}(\xi_+)+f^{(5)}(\xi_-)\big)}_{R},\qquad\lvert R\rvert\le\frac{2M_5}{240}h^4=\frac{M_5}{120}h^4$$

   Divide by $2h$ and bound each fifth derivative by $M_5$.
6. 6
   Step 6:

   $$\mathbb E\big[(\hat g-f')^2\big]=\big(\mathbb E\hat g-f'\big)^2+\mathbb E\big[(\hat g-\mathbb E\hat g)^2\big]$$

   Expand $\hat g-f'=(\hat g-\mathbb E\hat g)+(\mathbb E\hat g-f')$; the cross term has expectation zero.

∎

1. 1
   Step 1:

   $$\sin^2u=\tfrac12\big(1-\cos2u\big)$$

   Double-angle formula $\cos2u=1-2\sin^2u$.
2. 2
   Step 2:

   $$\sin^2(\theta+h)+\sin^2(\theta-h)=1-\tfrac12\big[\cos(2\theta+2h)+\cos(2\theta-2h)\big]$$

   Apply it with $u=\theta\pm h$ and add.
3. 3
   Step 3:

   $$\cos(a+b)+\cos(a-b)=2\cos a\cos b\ \Rightarrow\ \sin^2(\theta+h)+\sin^2(\theta-h)=1-\cos2\theta\cos2h$$

   Addition theorem $\cos(a\pm b)=\cos a\cos b\mp\sin a\sin b$; the sine terms cancel.

∎