Introduction
In this article I will cover the basics of what a qubit is from both a physics and mathematical standpoint, provide examples of common quantum gates, explain what a quantum algorithm is, introduce Shor’s algorithm for factoring integers, and briefly discuss what a quantum algorithm for graph isomorphism might entail.
After introducing qubits and quantum circuits, I describe some mathematical aspects of modeling networks in a quantum computer. One might expect interesting topological invariants to appear, since quantum state spaces are not discrete. However, the requirement of unitarity forces the maps involved to be topologically trivial.
What Is a Qubit?
A quantum bit, or qubit, generalizes the classical binary bit $\{0,1\}$. Any quantum system with two distinguishable states may serve as a qubit. A common example is an electron with two spin states, denoted $|0\rangle$ and $|1\rangle$.
A general qubit state is a complex superposition $c_o|0 \rangle + c_1|1\rangle$ with $|c_0|^2 + |c_1|^2 = 1$. Writing the coefficients in real and imaginary parts shows that the state space is a 3-sphere modulo phase, yielding $P(\mathbb{C}^2) \cong \mathbb{C}P^1 \cong S^2$.
We are free to perform measurements on a qubit by computing expectation values of operators.
1, 2, and 3 Qubit Gates
A quantum gate is a unitary operation acting on one or more qubits. Solutions to the Schrödinger equation are unitary operators of the form $exp(i\hbar H t)$.
Single-qubit gates are $2 \times 2$ unitary matrices such as X, Y, Z, H, S, and T. For example, the Hadamard gate is
$ H = \frac{1}{\sqrt{2}} \begin{pmatrix} 1 & 1 \\ 1 & -1 \end{pmatrix} $
It acts as:
$|0\rangle → (|0\rangle + |1\rangle)/\sqrt{2}$
$|1\rangle → (|0\rangle − |1\rangle)/\sqrt{2}$
Multi-qubit systems are formed using tensor products. A system of $n$ qubits has $2^n$ amplitudes and state space $\mathbb{C}P^{2^n−1}$.
Two- and three-qubit gates are $4 \times 4$ and $8 \times 8$ unitary matrices respectively. Examples include CNOT, CZ, SWAP, and the Toffoli (CCNOT) gate.
Quantum Algorithms
A quantum algorithm is a unitary evolution on n qubits followed by measurement. Gates are arranged into quantum circuits, analogous to classical logic circuits.
Quantum algorithms can simulate any classical algorithm and thus generalize classical computation.
Shor’s Algorithm
Shor’s algorithm factors integers in polynomial time using a quantum computer. It reduces factoring to order finding modulo N.
Given coprime integers $a$ and $N$, the goal is to find the smallest $r$ such that $a^r ≡ 1 \text{ mod } N$.
The algorithm uses two registers: one to control precision and one to compute modular exponentiation. The key quantum subroutine is phase estimation.
By applying Hadamard gates, controlled modular exponentiation, and the inverse quantum Fourier transform, the order $r$ can be extracted using classical post-processing.
An implementation using IBM’s Qiskit framework (run on a 127-qubit Eagle QPU) is available here:
https://github.com/walters-labs/shors_algorithm
Representing Graphs
One approach to modeling graphs on a quantum computer is to place a qubit on each edge. Classically, graphs are elements of $\{0,1\}^n$ modulo label permutations.
Quantum mechanically, this leads to projective tensor product spaces modulo symmetric group actions.
Topological Properties
Quantum algorithms are unitary maps on finite-dimensional Hilbert spaces. Since all unitary operators are homotopic to the identity, they have no interesting topological invariants.
As noted by Qiaochu Yuan, the symmetric group action factors through a path-connected group, so it acts trivially on homotopy invariants.
The resulting cohomology is that of complex projective space $\mathbb{C}P^{2^n − 1}$.
References
[1] P. W. Shor, Polynomial-time algorithms for factorization and discrete logarithms on a quantum computer, SIAM Journal on Computing 26 (1997).