INTRO
In this article I will cover the basics of what a qubit is from both a physics and mathematical standpoint, provide examples of various common gates that are used to operate on one, two, and three qubits, explain the basics of what a quantum algorithm is, introduce Shor’s algorithm for factoring integers, and mention what a quantum algorithm for graph isomorphism might entail (a lot of work).
After introducing the basics of qubits and quantum circuits, I will describe some basic mathematical aspects of modeling networks in a quantum computer. That is, what is the input space for an algorthim which processes quantum graphs? At first glance, I thought that a quantum algorithm may have an interesting topological invariant like homology or homotopy given that the input and output spaces are actually, well, not discrete spaces like the cases for classical algorithms. However, as we will see, the structure of quantum mechanics forces the maps to be unitary matrices, which are not interesting topologically.
WHAT IS A QUBIT?
First and foremost, what is a quantum bit, or qubit? This is a way to store information using principles of quantum mechanics that generalizes the classical two-state, binary bit usually denoted $\{0,1\}$. We are free to use any quantum system with two distinct states. A common example is an electron which has two “spin states”. These are eigenvectors of the spin operator. Denote the spin down state $|0\rangle$ and spin up state $|1\rangle$. Any complex superposition of states will be a solution to the Schroedinger equation, and a state must be normalized to have probability 1, so our states are of the form $c_0|0\rangle+c_1|1\rangle$ with $|c_0|^2+|c_1|^2=1$. Note that if we write $c_0=a_0+b_0i$ and $c_1=a_1+b_1i$ we get $a_0^2+b_0^2+a_1^2+b_1^2=1$, the equation for a 3-sphere. However, note that we can act on $(c_0,c_1)$ by a phase $e^{i\theta}$ and the probabilities will still add to one, $|e^{i\theta}c_0|^2+|e^{i\theta}c_1|^2=1$. Thus, we are really quotienting by scalars $\lambda$, and so that state space of a quantum bit is $P(\mathbb{C}^2)\cong \mathbb{CP}^1 \cong S^2$, a 2-sphere. We are free to perform measurements (compute expectation values of different operators) on a qubit.
1, 2, 3 QUBIT GATES
A quantum gate is a manipulation that is performed on a number of qubits. These are given by unitary matrices, as solutions to the Schroedinger equation are given by them. The Schroedinger equation reads $i \hbar d/dt |\psi(t)\rangle = \hat{H}|\psi(t) \rangle$. This can be solved by exponentiation $\exp(i\hbar \hat{H} t)$.
Which operations can we perform reliably on a single qubit? Well, these are the single gate operations, which are unitary, 2×2 matrices. That’s because they operate on a pair of complex amplitudes $(c_0,c_1)$ and preserve probability. Examples include the Pauli X, Y, Z, Hadamard H, phase S/P, and $\pi/8$ T gates. For example, the Hadamard gate is given by $$H=(1/\sqrt{2})\begin{pmatrix}
1 & 1 \\
1 & -1
\end{pmatrix}.
$$ Let’s see what this does to a qubit.
$$|0\rangle \mapsto (1/\sqrt{2})(|0\rangle+|1\rangle)$$
$$|1\rangle \mapsto (1/\sqrt{2})(|0\rangle – |1\rangle)$$
When we are operating on qubits, we generally have a system of level $n$, which means that there are $n$ qubits. To concatenate quantum systems, it is necessary to use the tensor product rather than the direct sum. Thus, a generic element of a two qubit system looks like
$$(c_0|0\rangle+c_1|1\rangle) \otimes (d_0|0\rangle + d_1|1\rangle) = c_0d_0|00\rangle + c_0d_1|01\rangle + c_1d_0|10\rangle + c_1d_1|11\rangle$$ where $|00\rangle = |0\rangle\otimes|0\rangle$, etc. Thus, a level two system has $2^2$ amplitudes whose magnitudes squared sum to 1. Generally, a level $n$ system has $N=2^n$ amplitudes whose magnitudes squared sum to 1. Thus, the state space of a level $n$ system is $\mathbb{CP}^{N-1}$.
A two or three qubit gate is simply an $N \times N$ unitary matrix when $n=2$ or $n=3$, so $4 \times 4$ or $8 \times 8$. There are some very useful ones such as controlled not (CNOT, CX), controlled Z (CZ) and SWAP. The controlled not is basically the identity on the first qubit and swaps amplitudes of the second. It’s the identity gate tensor the X gate. It looks like
$$
\begin{bmatrix}
1 & 0 & 0 & 0 \\
0 & 1 & 0 & 0 \\
0 & 0 & 0 & 1 \\
0 & 0 & 1 & 0
\end{bmatrix}.
$$
Finally, the Toffoli gate is CCNOT, a doubly controlled X gate. It is $Id_2 \otimes Id_2 \otimes X$. It operates on three qubits.
QUANTUM ALGORITHMS
Put simply, a quantum algorithm is a map from the space of $n$ qubits to the space of $n$ qubits, followed by a measurement of some kind. It is the evolution of a controlled quantum state from an initial state to a final state via evolution determined by the Schroedinger equation, $i\hbar d/dt |\psi(t) \rangle = \hat{H}|\psi(t) \rangle$ with solution $|\psi(t) \rangle = \exp(i\hbar \hat{H}t)|\psi_0 \rangle$. Note that $exp(i\hbar \hat{H}t) \in U(N)$ is a unitary $N \times N$ matrix.
In order to have control over evolution of the qubits, quantum gates are arranged into a quantum circuit, in total analogy with classical computing. Instead of AND, OR, and NOT gates we are using $X$, $Y$, $Z$, $H$, $CX$, $CZ$, $CCNOT$, etc. gates.
Quantum algorithms are capable of running any classical algorithm, and so generalize the notion of computing.
SHOR’S ALGORITHM
A specific example of a quantum algrithm is “Shor’s algorithm”, which uses a quantum computer to factor an integer in polynomial time. We’ll try to paint in broad strokes what the algorithm is doing. There are many good references
1 including Wikipedia for the details.
The algorithm consists of two parts: 1) classical reduction to order finding 2) quantum order finding. We’ll focus on the second part.
Given coprime integers $N$ and $a$ such that $1 < a < N$, find the order $r$ of $a$ modulo $N$. That is, find the smallest $r$ such that $a^r \equiv 1 \mod N)$.
We're going to build a quantum circuit to perform this task. The circuit has two "registers", so places for input. The first register determines how accurate an approximation the second register produces.
For now, the size of the first register is $2n+1$ qubits, and the size of the second register is $n$ qubits which $n=\lfloor(\log_2(N))+1\rfloor$.
The first register is initialized to $|0\rangle^{\otimes 2n+1}$.
The second register is initialized to $|1\rangle$. We can think of each integer labeling a state so that we have $|k\rangle$ for each $0 \le k < 2^n$. The binary representation of $k$ gives us the element of the $n$-fold tensor product. In this sense, we're initalizing the register to $|1\rangle \otimes |0\rangle^{\otimes n-1}$.
Let's define a unitary operator, $U$. This will act on states of the form $|k\rangle$, where $0 < k < N$. Essentially, the operator is multiplication by $a$ (\mod $N$). We set it to the identity on indices larger than $N$.
\[
U|k\rangle =
\begin{cases}
|a^k \mod N\rangle, & \text{if } 0 \leq k < N, \\
|k\rangle, & \text{if } N \leq k < 2^n.
\end{cases}
\]
Note that $U_a^r=Id_{2^n}$, because $U_a^r|k\rangle=|a^r k \rangle = |k \rangle$. We use modular exponentiation to build the $U_{a^{2^j}}$ gates - repeated matrix multiplication.
Note that the eigenvalues of this $2^n \times 2^n$ matrix are of the form $\omega_{r}^{k}=\exp(2\pi i k/r)$. The eigenvalues are of the form
$|\psi_j\rangle=r^{-1/2}\sum_{k=0}^{r-1} \omega_r^{kj}|a^k \rangle$
Summing the eigenvectors $r^{-1/2}\sum_{j=0}^{r-1}|\psi_j \rangle = |1\rangle$
The "discrete Fourier transform" on a function $f:\mathbb{Z}/n\mathbb{Z} \rightarrow \mathbb{C}$ is $\hat{f}(a)=(1/\sqrt{n})\sum_{j=0}^{n-1}f(j)\exp(-2\pi i\frac{a j}{n})$. The transformation $\hat{}$ is invertible and in fact an automorphism on the $\mathbb{C}$ vector space of such functions and satisfies various identities. This vector space is finite dimensional, and this transformation can be represented as a matrix given basis vectors $\delta_k(i) = 1$ if $i=k$ and $0$ otherwise.
By analogy, the "quantum Fourier transform" acts on states $|a\rangle \mapsto (1/\sqrt{q})\sum_{j=0}^{q-1}|j\rangle \exp(2\pi i j a/q)$ with $0 \le a < q$ for some $q$. The Fourier transform is representable by a unitary matrix
with $\omega=\exp(2 \pi i/N)$ a primitive $N$-th root of unity.
The phase estimation consists of three parts: Hadamard gates on each input bit in the first register, modular exponentiation by the matrix $U_a$ in the second register controlled by bits in the first register, an inverse quantum Fourier transform on the first register.
First, apply Hadamard gates to every bit in the first register. $|0\rangle \mapsto (1/\sqrt{2})(|0\rangle+|1\rangle)$. Expanding this out gives a superposition of all numerical states with the second register fixed. This leaves the machine in state $q^{-1/2}\sum_{j=0}^{q-1}|j\rangle|1\rangle$
Then, apply multiplcation by $a$ to the second register to compute $U^j$ for each $j$ using $U_{a}^{2^k}$ for $0 \le k < q$ and modular exponentiation to obtain $q^{-1/2}\sum_{j=0}^{q-1}|j\rangle |a^j \mod N \rangle$.
Now, use the inverse quantum Fourier transform to map this state to $(1/q)\sum_{j=0}^{q-1}\sum_{c=0}^{q-1}\exp(2\pi i j c/q)|c\rangle|a^j \mod N \rangle$.
We may now consider the probability of finding the output state first register to be $|c\rangle|a^j \mod N \rangle$ for given $c$, $j$. This number is given by $(1/q)|\sum_{i:a^p \equiv a^j}exp(2\pi i p c/q)|^2$. By using clever bounds on this inequality, one can extract $r$ via continued fraction expansion.
Here is an implementation in QisKit, IBM's quantum computing framework with hardware around the world. This was run on a 127 qubit Eagle QPU:
https://github.com/jacksonwalters/shors_algorithm
REPRESENTING GRAPHS
I don’t have much to say yet regarding the graph isomorphism problem, other than that the existence of a polynomial time algorithm has not been ruled out. For now, I have just been working on getting a better understanding of the input space from a mathematical perspective. That is, how does one model networks in a quantum quantum computer?
It seems to me that the most obvious way to do this is to put a qubit on each edge of a standard graph. There are a couple ways to interpret this statement. Note that classically one can model graph space as $N=\binom{n}{2}$ edges labeled by unordered pairs of indices, with an action of the symmetric group on $n$ labels which permutes them, inducing a permutation on the edges. Two graphs are isomorphic if there is a label permutation which makes them identical. Mathematically, the space of networks is $\mathbb{R}_{\ge 0}^N/\Sigma_n$ and the space of graphs is $\{0,1\}^N/\Sigma_n$.
If we place a qubit on the edge naively, then we obtain the space $(CP^1)/\Sigma_n$, because the phase space of a qubit is $P(V_2)=\mathbb{CP}^1$ where $V_2$ is a complex vector space of dimension two. This has a natural map to the moduli space of non-negative edge weight networks by taking $|c_1|^2$ where each qubit is $c_0|0\rangle+c_1|1\rangle$ where $|c_0|^2+|c_1|^2$ and we have quotiented out by the action of the global $U(1)$ gauge group.
In quantum mechanics, a joint system is given by the tensor product. That is, we are considering a system of $N$ edges which have endpoints labeled, and permutations of these labels should give rise to identical systems. Thus, we want to consider $P((V_2)^{\otimes N})/\Sigma_n$.
TOPOLOGICAL PROPERTIES
Note that a quantum algorithm is a function $f:P(\mathcal{H}_p) \rightarrow P(\mathcal{H}_p)$ where $\mathcal{H}_p$ is the Hilbert state of a system of $p$ qubits. $\mathcal{H}_p$ is finite dimensional, and $f$ is a unitary operator which can be represented by a unitary matrix $U_f \in U(2^p)$. When $p=1$, we have a single qubit and we are looking at maps $f:\mathbb{CP}^1\rightarrow\mathbb{CP}^1$. Since $\mathbb{CP}^1 \cong S^2$, we are looking at self maps of the 2-sphere. One might imagine that these are topologically interesting, that they might have a degree. However, any unitary matrix is homotopic to the identity, so the degree must be 1. Same for higher dimensions. Thus, there is nothing to gain by trying to classify algorithms by their topological invariants. There are extended theories which drop the unitarity assumption, with surprising results.
On the space of graphs, one might ask what the cohomology of the input space, $P((V_2)^{\otimes N})/\Sigma_n$, is. Well, $H^*(P((V_2)^{\otimes N})/\Sigma_n)=H^*(P((V_2)^{\otimes N}))^{\Sigma_n}$.
“This action comes from a linear action on $V^{\otimes N}$ and so it factors through the action of the general linear group $GL(V^{\otimes N})$, which is path-connected, so every element acts trivially on any homotopy invariant.” -Qiaochu Yuan
The cohomology is just that of $\mathbb{CP}^{2^N-1}$.
REFS
[1] – [P. W. Shor, Polynomial-time algorithms for factorization and discrete logarithms on a quantum computer, SIAM Journal on Computing 26: pages 1484-1509, 1997](
https://epubs.siam.org/doi/10.1137/S0097539795293172)
FORUM QUESTIONS
