{"id":11,"date":"2023-10-11T22:22:00","date_gmt":"2023-10-11T22:22:00","guid":{"rendered":"https:\/\/jacksonwalters.com\/blog\/?p=11"},"modified":"2025-12-17T20:48:52","modified_gmt":"2025-12-17T20:48:52","slug":"a-brief-intro-to-quantum-algorithms","status":"publish","type":"post","link":"https:\/\/jacksonwalters.com\/blog\/?p=11","title":{"rendered":"a brief intro to quantum algorithms"},"content":{"rendered":"\n

Introduction<\/h2>\n\n\n\n

\nIn 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\u2019s algorithm for factoring integers, and briefly discuss what a quantum algorithm for graph isomorphism might entail.\n<\/p>\n\n\n\n

\nAfter 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.\n<\/p>\n\n\n\n

What Is a Qubit?<\/h2>\n\n\n\n

\nA 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$.\n<\/p>\n\n\n\n

\nA 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$.\n<\/p>\n\n\n\n

\nWe are free to perform measurements on a qubit by computing expectation values of operators.\n<\/p>\n\n\n\n

1, 2, and 3 Qubit Gates<\/h2>\n\n\n\n

\nA quantum gate is a unitary operation acting on one or more qubits. Solutions to the Schr\u00f6dinger equation are unitary operators of the form $exp(i\\hbar H t)$.\n<\/p>\n\n\n\n

\nSingle-qubit gates are $2 \\times 2$ unitary matrices such as X, Y, Z, H, S, and T. For example, the Hadamard gate is\n<\/p>\n\n\n\n

\n$ H = \\frac{1}{\\sqrt{2}} \\begin{pmatrix} 1 & 1 \\\\ 1 & -1 \\end{pmatrix} $\n<\/p>\n\n\n\n

\nIt acts as:
\n
$|0\\rangle \u2192 (|0\\rangle + |1\\rangle)\/\\sqrt{2}$ \n
$|1\\rangle \u2192 (|0\\rangle \u2212 |1\\rangle)\/\\sqrt{2}$\n<\/p>\n\n\n\n

\nMulti-qubit systems are formed using tensor products. A system of $n$ qubits has $2^n$ amplitudes and state space $\\mathbb{C}P^{2^n\u22121}$.\n<\/p>\n\n\n\n

\nTwo- 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.\n<\/p>\n\n\n\n

Quantum Algorithms<\/h2>\n\n\n\n

\nA quantum algorithm is a unitary evolution on n qubits followed by measurement. Gates are arranged into quantum circuits, analogous to classical logic circuits.\n<\/p>\n\n\n\n

\nQuantum algorithms can simulate any classical algorithm and thus generalize classical computation.\n<\/p>\n\n\n\n

Shor\u2019s Algorithm<\/h2>\n\n\n\n

\nShor\u2019s algorithm factors integers in polynomial time using a quantum computer. It reduces factoring to order finding modulo N.\n<\/p>\n\n\n\n

\nGiven coprime integers $a$ and $N$, the goal is to find the smallest $r$ such that $a^r \u2261 1 \\text{ mod } N$.\n<\/p>\n\n\n\n

\nThe algorithm uses two registers: one to control precision and one to compute modular exponentiation. The key quantum subroutine is phase estimation.\n<\/p>\n\n\n\n

\n\"Quantum\n
Quantum Fourier transform matrix<\/figcaption>\n<\/figure>\n\n\n\n

\nBy applying Hadamard gates, controlled modular exponentiation, and the inverse quantum Fourier transform, the order $r$ can be extracted using classical post-processing.\n<\/p>\n\n\n\n

\n\"Quantum\n
Quantum phase estimation circuit<\/figcaption>\n<\/figure>\n\n\n\n

\nAn implementation using IBM\u2019s Qiskit framework (run on a 127-qubit Eagle QPU) is available here:\n<\/p>\n\n\n\n

\nhttps:\/\/github.com\/walters-labs\/shors_algorithm<\/a>\n<\/p>\n\n\n\n

Representing Graphs<\/h2>\n\n\n\n

\nOne 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.\n<\/p>\n\n\n\n

\nQuantum mechanically, this leads to projective tensor product spaces modulo symmetric group actions.\n<\/p>\n\n\n\n

Topological Properties<\/h2>\n\n\n\n

\nQuantum algorithms are unitary maps on finite-dimensional Hilbert spaces. Since all unitary operators are homotopic to the identity, they have no interesting topological invariants.\n<\/p>\n\n\n\n

\nAs noted by Qiaochu Yuan, the symmetric group action factors through a path-connected group, so it acts trivially on homotopy invariants.\n<\/p>\n\n\n\n

\nThe resulting cohomology is that of complex projective space $\\mathbb{C}P^{2^n \u2212 1}$.\n<\/p>\n\n\n\n

References<\/h2>\n\n\n\n

\n[1] P. W. Shor, Polynomial-time algorithms for factorization and discrete logarithms on a quantum computer<\/em>, SIAM Journal on Computing 26 (1997).\n<\/p>\n\n\n\n

Forum Questions<\/h2>\n\n\n\n