The HHL Algorithm for Ax = b

1. 1
   Step 1:

   $$A^{-1}=\sum_j\lambda_j^{-1}\lvert u_j\rangle\langle u_j\rvert$$

   Spectral theorem: $f(A)=\sum_jf(\lambda_j)\lvert u_j\rangle\langle u_j\rvert$ for $f(\lambda)=1/\lambda$, defined because no $\lambda_j$ vanishes. Check: $A\cdot A^{-1}=\sum_{j,l}\lambda_j\lambda_l^{-1}\lvert u_j\rangle\langle u_j\vert u_l\rangle\langle u_l\rvert=\sum_j\lvert u_j\rangle\langle u_j\rvert=I$.
2. 2
   Step 2:

   $$A^{-1}\lvert b\rangle=\sum_j\lambda_j^{-1}\lvert u_j\rangle\langle u_j\vert b\rangle=\sum_j\frac{\beta_j}{\lambda_j}\lvert u_j\rangle$$

   Apply the operator to $\lvert b\rangle$ and use $\langle u_j\vert b\rangle=\beta_j$.
3. 3
   Step 3:

   $$\lvert x\rangle=\frac{\sum_j\beta_j\lambda_j^{-1}\lvert u_j\rangle}{\sqrt{\sum_j\lvert\beta_j\rvert^2\lambda_j^{-2}}}$$

   Normalise with $\lVert\sum_jc_j\lvert u_j\rangle\rVert^2=\sum_j\lvert c_j\rvert^2$ (orthonormality). HHL therefore only has to multiply each eigencomponent by a number proportional to $\lambda_j^{-1}$.

1. 1
   Step 1:

   $$\tilde A=\begin{pmatrix}0&A\\A^\dagger&0\end{pmatrix},\qquad\tilde A^\dagger=\begin{pmatrix}0^\dagger&(A^\dagger)^\dagger\\A^\dagger&0^\dagger\end{pmatrix}=\begin{pmatrix}0&A\\A^\dagger&0\end{pmatrix}=\tilde A$$

   The adjoint of a block matrix transposes the block positions and takes the adjoint of each block; $(A^\dagger)^\dagger=A$. So $\tilde A$ is Hermitian for any square $A$, at the cost of one extra qubit.
2. 2
   Step 2:

   $$\tilde A\begin{pmatrix}0\\\vec x\end{pmatrix}=\begin{pmatrix}A\vec x\\0\end{pmatrix}=\begin{pmatrix}\vec b\\0\end{pmatrix}$$

   Block multiplication. Solving $\tilde A\vec y=(\vec b,0)^T$ therefore gives $\vec y=(0,\vec x)^T$ with $A\vec x=\vec b$; the eigenvalues of $\tilde A$ are $\pm\sigma_j$ (singular values of $A$), so $\kappa(\tilde A)=\kappa(A)$.

1. 1
   Step 1:

   $$U\lvert u_j\rangle=e^{iAt}\lvert u_j\rangle=e^{i\lambda_jt}\lvert u_j\rangle$$

   Spectral theorem with $f(\lambda)=e^{i\lambda t}$: $e^{iAt}=\sum_je^{i\lambda_jt}\lvert u_j\rangle\langle u_j\rvert$, a unitary because each $\lvert e^{i\lambda_jt}\rvert=1$.
2. 2
   Step 2:

   $$e^{i\lambda_jt}=e^{2\pi i\varphi_j},\qquad\varphi_j=\frac{\lambda_jt}{2\pi}$$

   Write the eigenphase as a fraction of a full turn, as in quantum phase estimation (QPE). Choosing $t$ with $0<\lambda_jt<2\pi$ makes $\varphi_j\in(0,1)$ unambiguous.
3. 3
   Step 3:

   $$\mathrm{QPE}\big(\lvert0\rangle^{\otimes t_c}\lvert u_j\rangle\big)=\lvert k_j\rangle\lvert u_j\rangle,\qquad k_j=2^{t_c}\varphi_j=\frac{\lambda_jt\,2^{t_c}}{2\pi}$$

   QPE with $t_c$ clock qubits applies $H^{\otimes t_c}$, the controlled powers $U^{2^m}$ (phase kickback gives $\tfrac1{2^{t_c/2}}\sum_ke^{2\pi i\varphi_jk}\lvert k\rangle=\mathrm{QFT}\lvert2^{t_c}\varphi_j\rangle$) and $\mathrm{QFT}^\dagger$. The output is exact when $2^{t_c}\varphi_j$ is an integer.
4. 4
   Step 4:

   $$\mathrm{QPE}\big(\lvert0\rangle^{\otimes t_c}\lvert b\rangle\big)=\sum_j\beta_j\lvert k_j\rangle\lvert u_j\rangle$$

   QPE is linear and $\lvert b\rangle=\sum_j\beta_j\lvert u_j\rangle$. The eigenvectors are never computed: the circuit acts on all components at once.

1. 1
   Step 1:

   $$R_Y(\theta)\lvert0\rangle=\cos\tfrac\theta2\lvert0\rangle+\sin\tfrac\theta2\lvert1\rangle$$

   First column of $R_Y(\theta)=\begin{pmatrix}\cos\frac\theta2&-\sin\frac\theta2\\\sin\frac\theta2&\cos\frac\theta2\end{pmatrix}$.
2. 2
   Step 2:

   $$\sin\tfrac{\theta_k}2=\frac Ck\iff\theta_k=2\arcsin\frac Ck$$

   Requires $0<C/k\le1$, i.e. $C\le\min_jk_j$; then $\cos\tfrac{\theta_k}{2}=\sqrt{1-C^2/k^2}\ge0$ because $\theta_k/2\in(0,\pi/2]$.
3. 3
   Step 3:

   $$\sum_j\beta_j\lvert k_j\rangle\lvert u_j\rangle\lvert0\rangle_a\mapsto\sum_j\beta_j\lvert k_j\rangle\lvert u_j\rangle\Big(\sqrt{1-\tfrac{C^2}{k_j^2}}\lvert0\rangle_a+\tfrac{C}{k_j}\lvert1\rangle_a\Big)$$

   The rotation is controlled by the clock: for each basis value $k$ of the clock apply $R_Y(\theta_k)$ to the ancilla. With $t_c$ clock qubits this is a uniformly controlled rotation; in the worked example the clock values $1=\lvert01\rangle$ and $2=\lvert10\rangle$ each have a single set bit, so one CRY per clock qubit suffices.

1. 1
   Step 1:

   $$\mathrm{QPE}^\dagger:\ \sum_j\beta_j\lvert k_j\rangle\lvert u_j\rangle\lvert a_j\rangle\mapsto\sum_j\beta_j\lvert0\rangle^{\otimes t_c}\lvert u_j\rangle\lvert a_j\rangle$$

   $\mathrm{QPE}^\dagger$ (reverse order, adjoint gates: QFT, controlled $U^{-2^m}$, $H^{\otimes t_c}$) maps $\lvert k_j\rangle\lvert u_j\rangle\mapsto\lvert0\rangle\lvert u_j\rangle$ and does not act on the ancilla. Without uncomputation the clock stays entangled with $\lvert u_j\rangle$ and the system would be in a mixed state.
2. 2
   Step 2:

   $$(\langle1\rvert_a\otimes I)\,\lvert\Psi\rangle=\lvert0\rangle^{\otimes t_c}\otimes C\sum_j\frac{\beta_j}{k_j}\lvert u_j\rangle$$

   Project the ancilla onto $\lvert1\rangle$: only the amplitudes $C/k_j$ survive, and $k_j\propto\lambda_j$.
3. 3
   Step 3:

   $$p_{\text{succ}}=\Big\lVert C\sum_j\frac{\beta_j}{k_j}\lvert u_j\rangle\Big\rVert^2=\sum_j\lvert\beta_j\rvert^2\frac{C^2}{k_j^2}$$

   Born rule; orthonormality of the $\lvert u_j\rangle$.
4. 4
   Step 4:

   $$\frac{\sum_j\beta_jk_j^{-1}\lvert u_j\rangle}{\sqrt{\sum_j\lvert\beta_j\rvert^2k_j^{-2}}}=\frac{\sum_j\beta_j\lambda_j^{-1}\lvert u_j\rangle}{\sqrt{\sum_j\lvert\beta_j\rvert^2\lambda_j^{-2}}}=\lvert x\rangle$$

   The post-measurement state; the common factor $2\pi/(t2^{t_c})$ in $k_j^{-1}=\tfrac{2\pi}{t2^{t_c}}\lambda_j^{-1}$ cancels in the normalisation.
5. 5
   Step 5:

   $$C=k_{\min}\ \Rightarrow\ \frac{C^2}{k_j^2}=\frac{\lambda_{\min}^2}{\lambda_j^2}\ge\frac1{\kappa^2}\ \Rightarrow\ p_{\text{succ}}\ge\frac1{\kappa^2}\sum_j\lvert\beta_j\rvert^2=\frac1{\kappa^2}$$

   Each term is bounded below by $1/\kappa^2$ and $\sum_j\lvert\beta_j\rvert^2=1$. Repeating until success needs on average $1/p_{\text{succ}}=O(\kappa^2)$ runs; amplitude amplification boosts an amplitude $\sqrt p$ to $\Theta(1)$ with $O(1/\sqrt p)=O(\kappa)$ rounds.

1. 1
   Step 1:

   $$A=I-\tfrac13X,\qquad X\lvert\pm\rangle=\pm\lvert\pm\rangle$$

   $A$ has $1$ on the diagonal and $-\tfrac13$ off it. The eigenvectors of $X$ are $\lvert\pm\rangle=(1,\pm1)/\sqrt2$.
2. 2
   Step 2:

   $$\lambda_1=1-\tfrac13=\tfrac23,\ \ u_1=\tfrac{1}{\sqrt2}(1,1);\qquad\lambda_2=1+\tfrac13=\tfrac43,\ \ u_2=\tfrac1{\sqrt2}(1,-1)$$

   $A\lvert\pm\rangle=(1\mp\tfrac13)\lvert\pm\rangle$. Condition number $\kappa=\tfrac{4/3}{2/3}=2$.
3. 3
   Step 3:

   $$\lvert0\rangle=\tfrac1{\sqrt2}\big(u_1+u_2\big),\qquad\beta_1=\beta_2=\tfrac1{\sqrt2}$$

   $u_1+u_2=\tfrac1{\sqrt2}(2,0)=\sqrt2\,(1,0)$.

1. 1
   Step 1:

   $$e^{iAt}=e^{it}e^{-i\frac t3X}$$

   $I$ and $X$ commute, so $e^{i(I-X/3)t}=e^{itI}e^{-itX/3}$.
2. 2
   Step 2:

   $$e^{-i\alpha X}=\cos\alpha\,I-i\sin\alpha\,X,\qquad\alpha=\tfrac t3=\tfrac\pi4$$

   Power series with $X^2=I$: even powers give $\cos\alpha\,I$, odd powers give $-i\sin\alpha\,X$.
3. 3
   Step 3:

   $$e^{i\frac{3\pi}4}=\frac{-1+i}{\sqrt2},\qquad e^{-i\frac\pi4X}=\frac1{\sqrt2}\big(I-iX\big)$$

   $\cos\tfrac{3\pi}4=-\tfrac1{\sqrt2}$, $\sin\tfrac{3\pi}4=\tfrac1{\sqrt2}$, $\cos\tfrac\pi4=\sin\tfrac\pi4=\tfrac1{\sqrt2}$.
4. 4
   Step 4:

   $$e^{iAt}=\frac{-1+i}{2}\big(I-iX\big)=\frac12\begin{pmatrix}-1+i&1+i\\1+i&-1+i\end{pmatrix}$$

   Diagonal entries $\tfrac{-1+i}2$; off-diagonal entries $\tfrac{(-1+i)(-i)}2=\tfrac{i-i^2}{2}=\tfrac{1+i}2$.
5. 5
   Step 5:

   $$\big(e^{iAt}\big)^2=e^{2i\frac{3\pi}4}\big(e^{-i\frac\pi4X}\big)^2=e^{i\frac{3\pi}2}e^{-i\frac\pi2X}=(-i)(-iX)=-X$$

   $e^{i3\pi/2}=-i$ and $e^{-i\frac\pi2X}=\cos\tfrac\pi2I-i\sin\tfrac\pi2X=-iX$; $(-i)(-i)=i^2=-1$.
6. 6
   Step 6:

   $$\frac14\begin{pmatrix}(-1+i)^2+(1+i)^2&2(-1+i)(1+i)\\2(1+i)(-1+i)&(1+i)^2+(-1+i)^2\end{pmatrix}=\frac14\begin{pmatrix}-2i+2i&-4\\-4&2i-2i\end{pmatrix}=\begin{pmatrix}0&-1\\-1&0\end{pmatrix}$$

   Direct matrix check: $(-1+i)^2=-2i$, $(1+i)^2=2i$, $(-1+i)(1+i)=-1-i+i+i^2=-2$. So $U^2=-X$, $U^{-2}=(-X)^{-1}=-X$ and $U^{-1}=U^\dagger=\tfrac12\begin{pmatrix}-1-i&1-i\\1-i&-1-i\end{pmatrix}$.

1. 1
   Step 1:

   $$k_j=\frac{\lambda_j t\,2^{t_c}}{2\pi}=\frac{\lambda_j\cdot\frac{3\pi}{4}\cdot4}{2\pi}=\frac{3\lambda_j}{2}\ \Rightarrow\ k_1=1,\ k_2=2$$

   Two clock qubits, $2^{t_c}=4$. Both values are integers, so QPE is exact: the clock holds $\lvert01\rangle$ for $u_1$ and $\lvert10\rangle$ for $u_2$ (qubit $1$ is the MSB). Consistency: $U u_1=e^{i\pi/2}u_1=iu_1$ and $Uu_2=e^{i\pi}u_2=-u_2$.
2. 2
   Step 2:

   $$C=1=\min_jk_j:\qquad\theta_1=2\arcsin1=\pi,\qquad\theta_2=2\arcsin\tfrac12=\tfrac\pi3$$

   $\arcsin\tfrac12=\tfrac\pi6$. The rotation for $k_1=1$ is controlled by the LSB clock qubit, the one for $k_2=2$ by the MSB.
3. 3
   Step 3:

   $$\big(\langle1\rvert_a\otimes\langle00\rvert_c\big)\lvert\Psi\rangle=\tfrac1{\sqrt2}\Big(\tfrac11u_1+\tfrac12u_2\Big)=\tfrac12\Big(\tfrac32,\tfrac12\Big)=\Big(\tfrac34,\tfrac14\Big)$$

   $\beta_j=\tfrac1{\sqrt2}$, $C/k_1=1$, $C/k_2=\tfrac12$; $u_1+\tfrac12u_2=\tfrac1{\sqrt2}(\tfrac32,\tfrac12)$.
4. 4
   Step 4:

   $$p_{\text{succ}}=\tfrac12\Big(1+\tfrac14\Big)=\tfrac58=\Big(\tfrac34\Big)^2+\Big(\tfrac14\Big)^2,\qquad\lvert x\rangle=\frac{(3,1)}{\sqrt{10}}=(0.948683,\ 0.316228)$$

   $\tfrac9{16}+\tfrac1{16}=\tfrac{10}{16}=\tfrac58$. Normalising $(\tfrac34,\tfrac14)$ gives $(3,1)/\sqrt{10}$. This exceeds the bound $1/\kappa^2=\tfrac14$.
5. 5
   Step 5:

   $$A^{-1}=\frac{1}{1-\frac19}\begin{pmatrix}1&\frac13\\\frac13&1\end{pmatrix}=\frac98\begin{pmatrix}1&\frac13\\\frac13&1\end{pmatrix},\qquad A^{-1}\vec b=\frac98\Big(1,\frac13\Big)\propto(3,1)$$

   Classical check with the $2\times2$ inverse $\tfrac1{\det A}\begin{pmatrix}d&-b\\-c&a\end{pmatrix}$, $\det A=1-\tfrac19=\tfrac89$. The direction agrees with the quantum output.

Quick check