Quantum Computing Algorithm Examples

This page contains links to examples of Quantum Computing Algorithms developed for the Quantum Computing Algorithms Lecture at the LLNL CASIS "Quantum Sensing and Information Processing" Summer Lecture Series. All examples are made using the drag-and-drop quantum circuit simulator Quirk (How To). Accompanying Slides (LA-UR-19-27665).

1) Phase Kickback, Amplitude Amplification & Quantum Search (Grover)

This section introduces Phase Kickback, Amplitude Amplification and Grover Search on an instance of 3-SAT on the formula \( f(x) = f(x_1,x_2,x_3) = (\overline{x_1}) \wedge (x_1 \vee \overline{x_2} \vee x_3) \wedge (x_1 \vee x_2) \) with the only satisfying assignment \( (x_1, x_2, x_3) = (0,1,1) \).

2) Quantum Fourier Transform, Phase Estimation & Period Finding (Shor)

This section introduces Shor's Period Finding Algorithm (the quantum subroutine for Integer Factorization) as a special case of Phase Estimations. In particular we use that the unitary modular arithmetic operation \( \times B \pmod R \) with to be found period \(p\) has Eigenstates \( |u_s\rangle = \frac{1}{\sqrt{r}} \sum_{k=0}^{r-1} e^{-2\pi i k (s/p)} |B^k \bmod R\rangle \) with Eigenvalue \( e^{2\pi i (s/p)} \) and, correspondingly, Phase \( \frac{s}{p} \).

3) Hamiltonian Simulation

This section uses the state channel duality to display the matrix of an \(n\)-qubit operation in the amplitude display af a \(2n\)-qubit state. For more background information see Quirk's How To.

4) Quantum Linear System Problem (HHL)

This section gives two implementations of the HHL Algorithm by Harrow, Hassidim and Lloyd to solve the following Linear System Problem: $$ A \cdot \vec{x} = \vec{b}:\quad \begin{pmatrix} 0.75 & 0.25 \\ 0.25 & 0.75 \end{pmatrix} \cdot \begin{pmatrix} x_1 \\ x_2 \end{pmatrix} = \begin{pmatrix} 2 \\ 0 \end{pmatrix}. $$ Classically, one would solve $$ \vec{x} = A^{-1} \cdot \vec{b} = \begin{pmatrix} 1.5 & -0.5 \\ -0.5 & 1.5 \end{pmatrix} \cdot \begin{pmatrix} 2 \\ 0 \end{pmatrix} = \begin{pmatrix} 3 \\ -1 \end{pmatrix}. $$ Quantumly, we start with a normalized state vector \( |b\rangle := \frac{\vec{b}}{||\vec{b}||} = |0\rangle \) and get a normalized solution state $$ |x\rangle = \frac{A^{-1}|b\rangle}{|| A^{-1}|b\rangle||} = \frac{1}{\sqrt{10}} \begin{pmatrix} 3 \\ 1 \end{pmatrix}. $$ Note that \(A\) has Eigenvectors \( |+\rangle = \frac{1}{\sqrt{2}} \begin{pmatrix} 1 \\ 1 \end{pmatrix}\) and \( |-\rangle = \frac{1}{\sqrt{2}} \begin{pmatrix} 1 \\ -1 \end{pmatrix} \) with corresponding Eigenvalues \(1, 0.5\) and condition number \(\kappa = 2\).