Barren Plateaus

1. 1
   Step 1:

   $$WMW^\dagger=\int\mathrm dU\,(WU)A(WU)^\dagger=\int\mathrm dU\,UAU^\dagger=M\quad\forall W\in\mathrm U(d)$$

   Left invariance of the Haar measure: the substitution $U\mapsto WU$ does not change the integral. Hence $M$ commutes with every unitary.
2. 2
   Step 2:

   $$D_j=I-2\lvert j\rangle\langle j\rvert:\quad (D_jMD_j)_{jk}=-M_{jk}\ (k\neq j)\ \Rightarrow\ M_{jk}=0$$

   This is Schur's lemma for the defining representation, proved by hand. The diagonal unitary $D_j$ flips the sign of row $j$ and of column $j$, so an off-diagonal entry in row $j$ changes sign; $D_jMD_j=M$ forces it to vanish. Thus $M$ is diagonal.
3. 3
   Step 3:

   $$P_{jk}\ \text{(transposition of }\lvert j\rangle,\lvert k\rangle):\quad (P_{jk}MP_{jk})_{jj}=M_{kk}\ \Rightarrow\ M_{jj}=M_{kk}$$

   Permutation matrices are unitary; conjugating a diagonal matrix by a transposition swaps two diagonal entries. All diagonal entries are therefore equal and $M=cI$.
4. 4
   Step 4:

   $$cd=\mathrm{Tr}M=\int\mathrm dU\,\mathrm{Tr}(UAU^\dagger)=\mathrm{Tr}A\ \Rightarrow\ c=\frac{\mathrm{Tr}A}d$$

   The trace is linear, cyclic ($\mathrm{Tr}(UAU^\dagger)=\mathrm{Tr}A$), and the measure has total mass $1$.
5. 5
   Step 5:

   $$\mathbb E\,\langle\psi\vert A\vert\psi\rangle=\langle0\vert\Big(\int\mathrm dU\,U^\dagger AU\Big)\vert0\rangle=\frac{\mathrm{Tr}A}{d}$$

   Apply the result to $U^\dagger$, which is again Haar distributed (invariance under $U\mapsto U^{-1}$ follows from uniqueness of the measure). A 1-design reproduces this degree-$(1,1)$ average by definition.

∎

1. 1
   Step 1:

   $$\langle\psi\vert A\vert\psi\rangle=\langle0\vert U^\dagger AU\vert0\rangle=\mathrm{Tr}\big(AU\lvert0\rangle\langle0\rvert U^\dagger\big)$$

   Cyclicity of the trace; set $B=D=\lvert0\rangle\langle0\rvert$ in the Weingarten formula, so $\mathrm{Tr}B=\mathrm{Tr}D=\mathrm{Tr}(BD)=1$.
2. 2
   Step 2:

   $$\mathbb E\big[\langle\psi\vert A\vert\psi\rangle\langle\psi\vert C\vert\psi\rangle\big]=\frac{\mathrm{Tr}A\,\mathrm{Tr}C+\mathrm{Tr}(AC)}{d^2-1}-\frac{\mathrm{Tr}(AC)+\mathrm{Tr}A\,\mathrm{Tr}C}{d(d^2-1)}$$

   Substitute into the Weingarten formula.
3. 3
   Step 3:

   $$=\big(\mathrm{Tr}A\,\mathrm{Tr}C+\mathrm{Tr}(AC)\big)\,\frac{d-1}{d(d^2-1)}=\frac{\mathrm{Tr}A\,\mathrm{Tr}C+\mathrm{Tr}(AC)}{d(d+1)}$$

   Both fractions carry the same numerator; $\frac1{d^2-1}-\frac1{d(d^2-1)}=\frac{d-1}{d(d^2-1)}$ and $d^2-1=(d-1)(d+1)$.
4. 4
   Step 4:

   $$\mathrm{Tr}\big[(A\otimes C)F\big]=\sum_{i,j}\langle j\vert A\vert i\rangle\langle i\vert C\vert j\rangle=\mathrm{Tr}(AC),\qquad\mathrm{Tr}\big[(A\otimes C)I\big]=\mathrm{Tr}A\,\mathrm{Tr}C$$

   Insert the definition of $F$; the sum over $i$ is a resolution of the identity.
5. 5
   Step 5:

   $$\mathrm{Tr}\Big[(A\otimes C)\,\mathbb E\big[(\lvert\psi\rangle\langle\psi\rvert)^{\otimes2}\big]\Big]=\mathrm{Tr}\Big[(A\otimes C)\,\frac{I+F}{d(d+1)}\Big]\quad\forall A,C$$

   The left side is $\mathbb E\big[\langle\psi\vert A\vert\psi\rangle\langle\psi\vert C\vert\psi\rangle\big]$; the right side is the same number by the previous two lines.
6. 6
   Step 6:

   $$\mathbb E\big[(\lvert\psi\rangle\langle\psi\rvert)^{\otimes2}\big]=\frac{I+F}{d(d+1)}$$

   Product operators $A\otimes C$ span all operators on $\mathbb C^d\otimes\mathbb C^d$, and an operator is fixed by its Hilbert–Schmidt inner products with a spanning set. Note that $\frac{I+F}2$ is the projector onto the symmetric subspace, of dimension $\frac{d(d+1)}2$: the average is the normalised symmetric projector.

∎

1. 1
   Step 1:

   $$C=\langle0\vert U_-^\dagger R_k^\dagger U_+^\dagger HU_+R_kU_-\vert0\rangle$$

   Definition of the cost with the circuit split at gate $k$; only $R_k$ depends on $\theta_k$.
2. 2
   Step 2:

   $$\partial_kR_k=-\tfrac i2V_kR_k=-\tfrac i2R_kV_k,\qquad\partial_kR_k^\dagger=\tfrac i2R_k^\dagger V_k$$

   Differentiate the exponential $e^{-i\theta V/2}$; $V_k$ commutes with every function of itself.
3. 3
   Step 3:

   $$\partial_kC=\tfrac i2\langle0\vert U_-^\dagger V_k\,\tilde K\,U_-\vert0\rangle-\tfrac i2\langle0\vert U_-^\dagger\,\tilde K\,V_kU_-\vert0\rangle,\qquad\tilde K=R_k^\dagger U_+^\dagger HU_+R_k$$

   Product rule: the derivative hits $R_k^\dagger$ on the left or $R_k$ on the right; move $V_k$ next to $U_-$ using the second form of each derivative.
4. 4
   Step 4:

   $$\partial_kC=\tfrac i2\langle0\vert U_-^\dagger[V_k,K]U_-\vert0\rangle,\qquad K=(U_+R_k)^\dagger H(U_+R_k)$$

   Combine the two terms; $\tilde K$ is $K$ for the renamed $U_+$. Right invariance of the Haar measure means that $U_+R_k$ is a 2-design whenever $U_+$ is, so the renaming does not affect any assumption below.
5. 5
   Step 5:

   $$[V,K]^\dagger=[K,V]=-[V,K]\ \Rightarrow\ A^\dagger=-\tfrac i2\,(-[V,K])=A,\qquad\mathrm{Tr}A=\tfrac i2\big(\mathrm{Tr}(VK)-\mathrm{Tr}(KV)\big)=0$$

   $V$ and $K$ are Hermitian, so their commutator is anti-Hermitian and $\frac i2$ times it is Hermitian; a commutator is traceless by cyclicity.

∎

1. 1
   Step 1:

   $$\mathbb E_{U_-}\big[\langle\psi\vert A\vert\psi\rangle\big]=\frac{\mathrm{Tr}A}d=0;\qquad\mathbb E_{U_+}[K]=\frac{\mathrm{Tr}H}{d}I\ \Rightarrow\ \mathbb E\big[[V_k,K]\big]=0$$

   (a) First Haar moment for $U_-$ (with $\mathrm{Tr}A=0$), or for $U_+$: the average of $K$ is a multiple of the identity, which commutes with $V_k$, and the commutator is linear in $K$.
2. 2
   Step 2:

   $$\mathrm{Var}[\partial_kC]=\mathbb E\big[\langle\psi\vert A\vert\psi\rangle^2\big]=\frac{\mathrm{Tr}(A)^2+\mathrm{Tr}(A^2)}{d(d+1)}=\frac{\mathrm{Tr}(A^2)}{d(d+1)}$$

   (b) The mean is zero by (a), and the second-moment theorem applies to $\lvert\psi\rangle=U_-\lvert0\rangle$ with $A$ fixed by $U_+$.
3. 3
   Step 3:

   $$\mathrm{Tr}(A^2)=-\tfrac14\mathrm{Tr}\big([V,K]^2\big)=\tfrac14\mathrm{Tr}\big([V,K]^\dagger[V,K]\big)$$

   $A^2=-\frac14[V,K]^2$ and $[V,K]^\dagger=-[V,K]$.
4. 4
   Step 4:

   $$[V,K]^\dagger[V,K]=(KV-VK)(VK-KV)=K^2-KVKV-VKVK+VK^2V$$

   Expand and use $V^2=I$.
5. 5
   Step 5:

   $$\mathrm{Tr}\big([V,K]^\dagger[V,K]\big)=2\,\mathrm{Tr}(K^2)-2\,\mathrm{Tr}(VKVK)\le4\,\mathrm{Tr}(K^2)=4\,\mathrm{Tr}(H^2)$$

   Cyclicity gives $\mathrm{Tr}(VK^2V)=\mathrm{Tr}(K^2)$. By Cauchy–Schwarz for the Hilbert–Schmidt product, $\lvert\mathrm{Tr}(VKV\cdot K)\rvert\le\lVert VKV\rVert_F\lVert K\rVert_F=\mathrm{Tr}(K^2)$, and $K$ is unitarily similar to $H$.
6. 6
   Step 6:

   $$\mathrm{Var}[\partial_kC]\le\frac{\mathrm{Tr}(H^2)}{d(d+1)}\ \overset{H^2=I}{=}\ \frac{d}{d(d+1)}=\frac{1}{2^n+1}$$

   Combine the last three lines; a Pauli string squares to the identity, so $\mathrm{Tr}(H^2)=d$. Equality holds when $V_k$ anticommutes with $K$.
7. 7
   Step 7:

   $$\partial_kC=\mathrm{Tr}\big(HU_+BU_+^\dagger\big),\quad B=\tfrac i2[\rho,V_k],\ \rho=\lvert\psi\rangle\langle\psi\rvert;\qquad\mathrm{Tr}B=0,\ \ \mathrm{Tr}(B^2)=\tfrac{1-\langle\psi\vert V_k\vert\psi\rangle^2}2$$

   (c) $\langle\psi\vert[V,K]\vert\psi\rangle=\mathrm{Tr}\big([\rho,V]K\big)$ by cyclicity. As before, $\mathrm{Tr}(B^2)=\frac14\mathrm{Tr}([\rho,V]^\dagger[\rho,V])=\frac14\big(2\,\mathrm{Tr}\rho-2\,\mathrm{Tr}(\rho V\rho V)\big)$ with $\rho^2=\rho$, $V^2=I$, and $\mathrm{Tr}(\rho V\rho V)=\langle\psi\vert V\vert\psi\rangle^2$.
8. 8
   Step 8:

   $$\mathbb E_{U_+}\big[\mathrm{Tr}(HU_+BU_+^\dagger)^2\big]=\frac{\mathrm{Tr}(H^2)\,\mathrm{Tr}(B^2)}{d^2-1}-\frac{\mathrm{Tr}(H)^2\,\mathrm{Tr}(B^2)}{d(d^2-1)}=\frac{d\,\mathrm{Tr}(B^2)}{d^2-1}$$

   Weingarten with $A=C=H$, $B=D=B$, and $\mathrm{Tr}B=0$; for a traceless Pauli string $\mathrm{Tr}H=0$ and $\mathrm{Tr}(H^2)=d$.

∎

1. 1
   Step 1:

   $$\Pr\big[\lvert X-\mathbb EX\rvert\ge\delta\big]\le\frac{\mathrm{Var}X}{\delta^2}$$

   Chebyshev's inequality, applied to $X=\partial_kC$ with $\mathbb EX=0$ and the variance bound of the theorem.
2. 2
   Step 2:

   $$\hat g=\tfrac12\big[\hat f_+-\hat f_-\big],\qquad\mathrm{Var}[\hat g]=\frac{(1-f_+^2)+(1-f_-^2)}{4N}\le\frac1{2N}$$

   Shot noise of the parameter-shift estimator for a Pauli-string $H$ (lesson on finite differences): each evaluation averages $N$ outcomes $\pm1$.
3. 3
   Step 3:

   $$\sqrt{\tfrac1{2N}}\le\varepsilon\sigma\ \Longleftrightarrow\ N\ge\frac1{2\varepsilon^2\sigma^2}=\frac{2^n+1}{2\varepsilon^2}\quad\text{for }\sigma^2=\tfrac1{2^n+1}$$

   The worst-case standard deviation $\frac1{\sqrt{2N}}$ must be below the precision $\varepsilon\sigma$ we ask for; when $f_\pm$ are close to $0$, as on a plateau, the shot-noise variance is close to its maximum $\frac1{2N}$, so the bound is essentially tight.

∎

1. 1
   Step 1:

   $$\Pi_0=\prod_jP_j,\qquad I-\Pi_0=\sum_{x\neq0}\lvert x\rangle\langle x\rvert,\qquad\frac1n\sum_j(I-P_j)=\sum_x\frac{\lvert x\rvert}{n}\lvert x\rangle\langle x\rvert$$

   All three operators are diagonal in the computational basis; $\lvert x\rvert$ is the number of ones in the bit string $x$, i.e. the number of qubits not in $\lvert0\rangle$.
2. 2
   Step 2:

   $$x\neq0:\quad\frac{\lvert x\rvert}n\le1\le\lvert x\rvert;\qquad x=0:\quad0\le0\le0$$

   Compare the diagonal entries: $1\le\lvert x\rvert\le n$ for every nonzero string.
3. 3
   Step 3:

   $$\frac1n\sum_j(I-P_j)\ \le\ I-\Pi_0\ \le\ \sum_j(I-P_j)$$

   Diagonal operators are ordered entrywise.
4. 4
   Step 4:

   $$C_L\le C_G\le n\,C_L$$

   $X\le Y$ implies $\mathrm{Tr}(\rho X)\le\mathrm{Tr}(\rho Y)$ for every state $\rho\ge0$.

∎