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) \).
- Reversible Satisfiability Computation with an
Oracle Operator \(O_f\) that maps function inputs \((x_1, x_2, x_3)\) and answer qubit \(b\) to \((x_1, x_2, x_3, b\oplus f(x))\), where \(\oplus\) denotes addition\(\bmod 2\).
- Phase Kickback
using the Oracle Operator \(O_f\)from above. Negates the amplitude of the solution state.
- Amplitude Amplification with the Grover Diffusion Operator \(O_D\): Reflects the current state around the \(|+\rangle^{\otimes n}\) axis, in conjunction with \(O_f\) amplifying the amplitude of the solution state.
- Complete Grover Search over all truth assignments to \((x_1,x_2,x_3)\), reaching maximum success probability after two rounds.
- Bonus: Possible Implementation
of \(O_f\) for 3-SAT. Computes violation of each clause in an assigned ancilla qubit, checks for all clauses to be non-violated / satisfied, and uncomputes the ancillas again.
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} \).
- Quantum Fourier Transform QFT,
mapping \( |1011\rangle \rightarrow \frac{1}{\sqrt{16}}
(|0\rangle + e^{2\pi i \cdot 0.1}|1\rangle) \otimes (|0\rangle + e^{2\pi i \cdot 0.11}|1\rangle) \otimes
(|0\rangle + e^{2\pi i \cdot 0.011}|1\rangle) \otimes (|0\rangle + e^{2\pi i \cdot 0.1011}|1\rangle) \),
with binary fraction notation, e.g. \( 0.1011 = \frac{1}{2} + \frac{0}{4} + \frac{1}{8} + \frac{1}{16}\).
- Phase Estimation for T-gate
\( T=\begin{pmatrix} 1 & 0 \\ 0 & e^{2 \pi i / 8} \end{pmatrix} \), combining Phase Kickback and Inverse Quantum Fourier Transform \(QFT^{\dagger}\).
- Phase Estimation for \(Z^{2/3} = \begin{pmatrix} 1 & 0 \\ 0 & e^{2 \pi i / 3} \end{pmatrix} \):
low precision,
high precision.
- Phase Estimation for the iSWAP-Gate
which swaps \( |01\rangle \leftrightarrow |10\rangle \) and – under swapping – adds a phase of \(i\).
Note that the Eigenstate \( \tfrac{1}{\sqrt{2}}(|01\rangle - |10\rangle) \) has Eigenvalue \(-i = e^{2\pi i \cdot 0.110}\) and that we have
$$ \mathrm{iSWAP}^1 = \begin{pmatrix} 1 & 0 & 0 & 0 \\ 0 & 0 & i & 0 \\ 0 & i & 0 & 0 \\ 0 & 0 & 0 & 1 \end{pmatrix},\quad
\mathrm{iSWAP}^2 = \begin{pmatrix} 1 & 0 & 0 & 0 \\ 0 & -1 & 0 & 0 \\ 0 & 0 & -1 & 0 \\ 0 & 0 & 0 & 1 \end{pmatrix} = Z \otimes Z,\quad
\mathrm{iSWAP}^4 = \begin{pmatrix} 1 & 0 & 0 & 0 \\ 0 & 1 & 0 & 0 \\ 0 & 0 & 1 & 0 \\ 0 & 0 & 0 & 1 \end{pmatrix} = \mathrm{Id} \otimes \mathrm{Id}. $$
- Shor's Period Finding Algorithm for \( B^r \equiv 1 \pmod R\) with \(B=5, R= 21\):
small register,
large register,
simplified presentation.
- Shor's Period Finding Algorithm for \( B^r \equiv 1 \pmod R\) with \(B=8, R=15\):
large register,
simplified presentation.
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.
- Exact Simulation of \(e^{-i t H} \) of Tensor Product Hamiltonian \(H = Z \otimes Y \otimes X\) for time \(t= \pi/4\):
original,
diagonalized,
broken down,
fully implemented.
We first diagonalize using \(X = H \cdot Z \cdot H,\ Y = S \cdot H \cdot Z \cdot H \cdot S^{-1}\),
then build \(\mathit{CNOT}\) stairs to compute and uncompute parity,
and finally use \(e^{-i \pi/4 Z} = e^{-i \pi/4} Z^{1/2} = e^{-i \pi/4} S = T^{-1} \cdot (X \cdot T^{-1} \cdot X) \cdot S\).
- Lie-Trotterization of \(e^{-i t H}\) for Sum Hamiltonian \(H = X + Z\) of non-commuting terms \( X, Z\) for time \(t= \pi/2\):
original,
1 time interval,
2 time intervals,
4 time intervals,
8 time intervals.
- Suzuki 2nd-order integration of \(e^{-i t H}\) for Sum Hamiltonian \(H = X + Z\) of non-commuting terms \( X, Z\) for time \(t= \pi/2\):
original,
1 time interval,
2 time intervals,
4 time intervals.
Here we use \(e^{-i \pi / 2^k X} = e^{-i \pi / 2^{k}} X^{1/2^{k-1}} \) and \(e^{-i \pi / 2^k Z} = e^{-i \pi / 2^{k}} Z^{1/2^{k-1}} \)
and combine global phases into a single global phase of \(e^{-i \pi} = -1\) for readability.
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\).
- Full implementation, with:
- Standard Phase Estimation, using the inverse Quantum Fourier Transform \(QFT^{\dagger}\),
- Direct Hamiltonian Simulation, using knowledge of \( e^{\pi i A} = -X^{-1/2}\) and \(e^{2\pi i A} = X \),
- Post-Selection replacing Amplitude Amplification.
- Stripped down implementation, with:
- Direct Phase Estimation, using knowledge of the Eigenstates of \(A\): \( |+\rangle \) and \( |-\rangle \),
- no Hamiltonian Simulation,
- Post-Selection replacing Amplitude Amplification.