Quantum Computing
I was granted a research account from IBM to use their QX quantum computers.
Resources
Summary
For a system $A\vec{x}=\vec{b}$, find a vector $\vec{x}=A^{-1}\vec{b}$. Harrow-Hassidm-Lloyd (HHL) outlined a quantum algorithm to solve linear systems of equations with at a much lower runtime and is comprised of three steps: phase estimation, inversion, and reversion. Its runtime is $O(\log(N) s^2 \kappa^2 / \varepsilon )$ where $\varepsilon$ is the truncation number, and $s$ is the sparsity. There are a lot of conditions on $A$ and $\vec{x}$ but I'm not going to dive too much into them and their workarounds here.
More generally, this can be looked at as the eigendecomposition $A=U\Lambda U^\dagger$ where $U$ is Hermitian and $\Lambda$ is a diagonal matrix of $A$'s eigenvalues.
\[ UAU^\dagger =\begin{bmatrix}\lambda_{1} & \\ & \ddots & \\ & & \lambda_{N} \end{bmatrix} \quad \implies \quad A^{-1} = U^\dagger \begin{bmatrix}\lambda^{-1}_{1} & \\ & \ddots & \\ & & \lambda^{-1}_{N} \end{bmatrix} U \] Instead of using the Quantum Fourier Transform (QFT), Kitaev's Phase Estimation Algorithm (IPEA) was used. The reason being, IPEA can be implemented over any number of quantum registers with the tradeoff being number of runs needed. For a precision of $2^{-m}$ bits, an eigenvalue can be computed using $m$ registers in $\log(m)$ iterations. Alternatively, the same results can be reached using 1 register and $m \log(m)$ iterations. Unlike the QFT, there is no need to reverse the phase estimation steps. The phase estimation circuit for two bits of precision is outlined below.
After the $ k $th bit is measured, the $ R $ gate rotates the phase based on the last measured bit. In outer product notation, $R(\varphi_k) = \vert 0 \rangle \langle 0 \vert + f(\varphi_k) \vert 1 \rangle \langle 1 \vert $ where $f(\varphi_k)$ is given by $$ f(\varphi_k) = \left\{ \begin{array}{ll} e^{\frac{-i\varphi_k \pi}{2^k}} & k > 0 \\ e^{\frac{-i\pi}{2^{k-1}}} & k = 0. \\ \end{array} \right. $$
Once the eigenvalues are known, the inversion is done by a r a rotation in the circular basis by $\theta_j$ produces a solution state proportional to $\vert x\rangle$. The angle is given by: \[ \theta_j = 2\arcsin\Big(\frac{\min\{\lambda_i \}}{\lambda_j}\Big) \]
Looking at some eigenvectors on the Bloch Sphere with respect to the circular (y) basis may be helpful
The proportional state refers to the fact that there is some normalization factor $C$ acting on the system. In other words, the true solution has a component $1-C^2$ which can be recovered by measuring the failed outcome states.
On Iteratvie Phase Estimation
Kitaev's iterative phase estimation algorithm differs from the Quantum Fourier Transform in a few ways. First, The outcomes is measured iteratively so there is no need to uncompute the results. The results are also deterministic.
Most importantly, the algorithm can be implemented with any number of quantum registers. Specifically, there is a lot of flexibility in terms of time-memory trade-offs. Since each QX architecture, is different, this is helpful. The main challenge was implementing the circuits in a way that obeyed the topology of the registers. Register states are entangled with one another by applying a controlled gate operation. The direction in which registers are coupled represents the control and target registers of a controlled gate.
