The Inversion (Compute–Uncompute) Test

1. 1
   Step 1:

   $$P(b)=\big\lvert\langle b\vert V\vert0^n\rangle\big\rvert^2,\qquad V=U(x')^\dagger U(x)$$

   Born rule: measuring every qubit of the pure state $V\lvert0^n\rangle$ in the computational basis returns the string $b$ with the squared modulus of the amplitude $\langle b\vert V\vert0^n\rangle$.
2. 2
   Step 2:

   $$\langle b\vert U(x')^\dagger=\big(U(x')\lvert b\rangle\big)^\dagger=\langle\phi_b(x')\rvert,\qquad\langle0^n\vert U(x')^\dagger=\langle\phi(x')\rvert$$

   The adjoint of a product is the reversed product of adjoints, $(AB)^\dagger=B^\dagger A^\dagger$ (proved in the next section), applied to the matrix $A=U(x')$ and the column vector $B=\lvert b\rangle$; for $b=0^n$ this is the bra of the feature state of $x'$.
3. 3
   Step 3:

   $$\langle b\vert U(x')^\dagger U(x)\vert0^n\rangle=\langle\phi_b(x')\vert\big(U(x)\lvert0^n\rangle\big)=\langle\phi_b(x')\vert\phi(x)\rangle$$

   Associativity of the matrix product: the row vector $\langle\phi_b(x')\rvert$ multiplies the column vector $U(x)\lvert0^n\rangle=\lvert\phi(x)\rangle$.
4. 4
   Step 4:

   $$P(0^n)=\lvert\langle\phi(x')\vert\phi(x)\rangle\rvert^2=\Big\lvert\overline{\langle\phi(x)\vert\phi(x')\rangle}\Big\rvert^2=K(x,x')$$

   Set $b=0^n$. Conjugate symmetry $\langle\psi\vert\chi\rangle=\overline{\langle\chi\vert\psi\rangle}$ and $\lvert\bar z\rvert=\lvert z\rvert$ show that the order of the two states inside the modulus is irrelevant.
5. 5
   Step 5:

   $$\langle\phi_b(x')\vert\phi_{b'}(x')\rangle=\langle b\vert U(x')^\dagger U(x')\vert b'\rangle=\langle b\vert b'\rangle=\delta_{bb'}$$

   A unitary maps the orthonormal computational basis to an orthonormal basis $\{\lvert\phi_b(x')\rangle\}_b$ of $\mathbb C^{2^n}$.
6. 6
   Step 6:

   $$\sum_{b}P(b)=\sum_b\lvert\langle\phi_b(x')\vert\phi(x)\rangle\rvert^2=\lVert\phi(x)\rVert^2=1\ \Rightarrow\ \sum_{b\ne0^n}P(b)=1-K(x,x')$$

   Parseval's identity in the basis $\{\lvert\phi_b(x')\rangle\}$: the other outcomes record the components of $\lvert\phi(x)\rangle$ orthogonal to $\lvert\phi(x')\rangle$.
7. 7
   Step 7:

   $$\big\lvert\langle0^n\vert U(x)^\dagger U(x')\vert0^n\rangle\big\rvert^2=\lvert\langle\phi(x)\vert\phi(x')\rangle\rvert^2=K(x',x)=K(x,x')$$

   The same computation with $x$ and $x'$ exchanged; the kernel is symmetric. Either circuit order estimates the same number.

∎

1. 1
   Step 1:

   $$\big((AB)^\dagger\big)_{ik}=\overline{(AB)_{ki}}=\overline{\sum_{j=1}^qA_{kj}B_{ji}}$$

   Definition of the conjugate transpose and of the matrix product, for $1\le i\le r$ and $1\le k\le p$.
2. 2
   Step 2:

   $$=\sum_{j=1}^q\overline{B_{ji}}\;\overline{A_{kj}}=\sum_{j=1}^q(B^\dagger)_{ij}(A^\dagger)_{jk}$$

   Complex conjugation is additive and multiplicative, $\overline{z+w}=\bar z+\bar w$ and $\overline{zw}=\bar z\bar w$, and complex numbers commute, so each product can be written with the $B$ factor first.
3. 3
   Step 3:

   $$=(B^\dagger A^\dagger)_{ik}\quad\text{for all }i,k\ \Rightarrow\ (AB)^\dagger=B^\dagger A^\dagger$$

   The last sum is entry $(i,k)$ of the product $B^\dagger A^\dagger$ of an $r\times q$ and a $q\times p$ matrix.
4. 4
   Step 4:

   $$(AB)^\dagger(AB)=B^\dagger(A^\dagger A)B=B^\dagger B=I\ \Rightarrow\ (AB)^{-1}=(AB)^\dagger=B^\dagger A^\dagger=B^{-1}A^{-1}$$

   For unitary square $A,B$ use the identity just proved, associativity, and $A^\dagger A=B^\dagger B=I$; a square matrix with a left inverse is invertible, with the same two-sided inverse.

∎

1. 1
   Step 1:

   $$L=1:\quad U=G_1,\qquad U^\dagger=G_1^\dagger$$

   Base case: a one-gate circuit is inverted by the inverse of its gate.
2. 2
   Step 2:

   $$U_{L+1}=G_{L+1}U_L\ \Rightarrow\ U_{L+1}^\dagger=U_L^\dagger\,G_{L+1}^\dagger$$

   Induction step: adding a gate at the end of the circuit multiplies the unitary from the left; apply the lemma with $A=G_{L+1}$, $B=U_L$.
3. 3
   Step 3:

   $$U_{L+1}^\dagger=\big(G_1^\dagger\cdots G_L^\dagger\big)G_{L+1}^\dagger=G_1^\dagger G_2^\dagger\cdots G_{L+1}^\dagger$$

   Insert the induction hypothesis $U_L^\dagger=G_1^\dagger\cdots G_L^\dagger$. As a time-ordered circuit the product is read from the right: $G_{L+1}^\dagger$ is applied first and $G_1^\dagger$ last.
4. 4
   Step 4:

   $$U^\dagger U=G_1^\dagger\cdots G_{L-1}^\dagger\big(G_L^\dagger G_L\big)G_{L-1}\cdots G_1=G_1^\dagger\cdots G_{L-1}^\dagger G_{L-1}\cdots G_1=\cdots=I$$

   Direct check that the reversed circuit undoes the original one: the product telescopes from the middle outwards, each $G_k^\dagger G_k=I$.
5. 5
   Step 5:

   $$(G\otimes I_{\bar S})^\dagger=G^\dagger\otimes I_{\bar S}$$

   A gate on the qubits $S$ is the tensor product of its small matrix with the identity on the remaining qubits $\bar S$, and $(A\otimes B)^\dagger=A^\dagger\otimes B^\dagger$ entrywise; so each inverted gate acts on the same qubits as the original one.
6. 6
   Step 6:

   $$\text{moments }M_1,\dots,M_d\text{ of }U\ \Rightarrow\ \text{moments }M_d^\dagger,\dots,M_1^\dagger\text{ of }U^\dagger$$

   Gates in one moment act on disjoint qubits, so their inverses do too; reversing the list of moments gives a valid layering of $U^\dagger$ with the same depth $d$, and the gate count $L$ is unchanged.

∎

1. 1
   Step 1:

   $$G=G^\dagger,\ G^\dagger G=I\ \Rightarrow\ G^2=I\ \Rightarrow\ G^{-1}=G$$

   A matrix that is both Hermitian and unitary squares to the identity. $X,Y,Z$ are Hermitian by inspection and $H=\frac1{\sqrt2}(X+Z)$ is a real combination of Hermitian matrices.
2. 2
   Step 2:

   $$\mathrm{CNOT}=\lvert0\rangle\langle0\rvert\otimes I+\lvert1\rangle\langle1\rvert\otimes X,\qquad\mathrm{CZ}=\mathrm{diag}(1,1,1,-1)$$

   Both are Hermitian (sums of tensor products of Hermitian factors, resp. real diagonal) and unitary, hence self-inverse. $\mathrm{SWAP}$, $\mathrm{CCX}$ and $\mathrm{CSWAP}$ are permutation matrices of involutions of the basis states (swapping two bits, flipping a bit under a condition that the flip does not change, exchanging two bits under a control), so applying them twice restores every basis state.
3. 3
   Step 3:

   $$\big(e^{A}\big)^\dagger=\Big(\sum_{k\ge0}\frac{A^k}{k!}\Big)^\dagger=\sum_{k\ge0}\frac{(A^\dagger)^k}{k!}=e^{A^\dagger}$$

   The exponential series converges absolutely, the adjoint is linear and continuous, and $(A^k)^\dagger=(A^\dagger)^k$ by the lemma applied $k-1$ times.
4. 4
   Step 4:

   $$R_P(\theta)^\dagger=\big(e^{-i\theta P/2}\big)^\dagger=e^{\,i\theta P^\dagger/2}=e^{-i(-\theta)P/2}=R_P(-\theta)$$

   Use the previous line with $A=-i\theta P/2$, $\overline{-i}=i$, and $P^\dagger=P$ for the Pauli matrices.
5. 5
   Step 5:

   $$R_P(-\theta)R_P(\theta)=\Big(\cos\tfrac\theta2I+i\sin\tfrac\theta2P\Big)\Big(\cos\tfrac\theta2I-i\sin\tfrac\theta2P\Big)=\Big(\cos^2\tfrac\theta2+\sin^2\tfrac\theta2\Big)I=I$$

   An explicit check with $R_P(\theta)=\cos\frac\theta2I-i\sin\frac\theta2P$ (exponential series with $P^2=I$): the cross terms cancel and $(i\sin\frac\theta2P)(-i\sin\frac\theta2P)=\sin^2\frac\theta2P^2$.
6. 6
   Step 6:

   $$P(\varphi)^\dagger=\mathrm{diag}\big(1,e^{i\varphi}\big)^\dagger=\mathrm{diag}\big(1,e^{-i\varphi}\big)=P(-\varphi),\qquad S^\dagger=P(-\tfrac\pi2),\quad T^\dagger=P(-\tfrac\pi4)$$

   The adjoint of a diagonal matrix conjugates its diagonal, and $\overline{e^{i\varphi}}=e^{-i\varphi}$. Since $S=P(\pi/2)$ and $T=P(\pi/4)$, their inverses are phase gates with negated angles, which are not equal to $S$ and $T$.
7. 7
   Step 7:

   $$\mathrm{CRZ}(\theta)^\dagger=\lvert0\rangle\langle0\rvert^\dagger\otimes I+\lvert1\rangle\langle1\rvert^\dagger\otimes R_Z(\theta)^\dagger=\lvert0\rangle\langle0\rvert\otimes I+\lvert1\rangle\langle1\rvert\otimes R_Z(-\theta)=\mathrm{CRZ}(-\theta)$$

   $(A\otimes B)^\dagger=A^\dagger\otimes B^\dagger$, projectors are Hermitian, and the rotation line above. The same argument inverts every controlled-$U$ gate to controlled-$U^\dagger$, e.g. $\mathrm{CP}(\varphi)^\dagger=\mathrm{CP}(-\varphi)$ and $\mathrm{CRX}(\theta)^\dagger=\mathrm{CRX}(-\theta)$.

∎

1. 1
   Step 1:

   $$U(x')^\dagger=\Big(\bigotimes_jR_X(x'_j)\Big)^\dagger=\bigotimes_jR_X(x'_j)^\dagger=\bigotimes_jR_X(-x'_j)$$

   $(A\otimes B)^\dagger=A^\dagger\otimes B^\dagger$ and $R_X(\theta)^\dagger=R_X(-\theta)$. Gates on different qubits commute, $(A\otimes I)(I\otimes B)=A\otimes B=(I\otimes B)(A\otimes I)$, so the reversed order of the circuit proposition is immaterial here.
2. 2
   Step 2:

   $$U(x')^\dagger U(x)=\bigotimes_jR_X(-x'_j)\cdot\bigotimes_jR_X(x_j)=\bigotimes_jR_X(-x'_j)R_X(x_j)$$

   The mixed-product rule $(\bigotimes_jA_j)(\bigotimes_jB_j)=\bigotimes_jA_jB_j$: each qubit sees only its own two rotations.
3. 3
   Step 3:

   $$R_X(\alpha)R_X(\beta)=\Big(c_\alpha I-is_\alpha X\Big)\Big(c_\beta I-is_\beta X\Big)=\big(c_\alpha c_\beta-s_\alpha s_\beta\big)I-i\big(s_\alpha c_\beta+c_\alpha s_\beta\big)X$$

   Abbreviate $c_\alpha=\cos\frac\alpha2$, $s_\alpha=\sin\frac\alpha2$ and use $R_X(\alpha)=c_\alpha I-is_\alpha X$ and $X^2=I$; the term $(-is_\alpha X)(-is_\beta X)=-s_\alpha s_\beta I$.
4. 4
   Step 4:

   $$=\cos\frac{\alpha+\beta}2\,I-i\sin\frac{\alpha+\beta}2\,X=R_X(\alpha+\beta)$$

   The addition theorems for cosine and sine. Equivalently, $e^{-i\alpha X/2}e^{-i\beta X/2}=e^{-i(\alpha+\beta)X/2}$ because the two exponents are multiples of the same matrix and therefore commute.
5. 5
   Step 5:

   $$R_X(-x'_j)R_X(x_j)=R_X(x_j-x'_j)\ \Rightarrow\ U(x')^\dagger U(x)=\bigotimes_jR_X(x_j-x'_j)$$

   Set $\alpha=-x'_j$, $\beta=x_j$. Compute and uncompute merge into one rotation by the feature difference $\Delta_j=x_j-x'_j$.
6. 6
   Step 6:

   $$R_X(\Delta_j)\lvert0\rangle=\cos\frac{\Delta_j}2\lvert0\rangle-i\sin\frac{\Delta_j}2\lvert1\rangle,\qquad V\lvert0^n\rangle=\bigotimes_j\Big(\cos\frac{\Delta_j}2\lvert0\rangle-i\sin\frac{\Delta_j}2\lvert1\rangle\Big)$$

   First column of $R_X(\Delta_j)$; the output is a product state.
7. 7
   Step 7:

   $$P(b)=\prod_j\Big\lvert\langle b_j\vert R_X(\Delta_j)\vert0\rangle\Big\rvert^2=\prod_j\Big(\cos^2\frac{\Delta_j}2\Big)^{1-b_j}\Big(\sin^2\frac{\Delta_j}2\Big)^{b_j}$$

   The amplitude of $\lvert b\rangle=\bigotimes_j\lvert b_j\rangle$ in a product state is the product of the one-qubit amplitudes; $\lvert-i\rvert=1$. For $b=0^n$ this is the product-kernel formula of the previous lesson. For $R_Y$ the same steps apply with $Y$ in place of $X$ (also $Y^2=I$), and $R_Y(\Delta)\lvert0\rangle=\cos\frac\Delta2\lvert0\rangle+\sin\frac\Delta2\lvert1\rangle$.

∎