Notices of the American Mathematical Society

Welcome to the Notices of the American Mathematical Society.
With support from AMS membership, we are pleased to share the journal with the global mathematical community.

PDFLINK

Introduction to Quantum Algorithms

Jamie Pommersheim

Communicated by Notices Associate Editor Emily J. Olson

book cover — ***Introduction to Quantum Algorithms***
*American Mathematical Society, 2024, 371 pp., https://bookstore.ams.org/amstext-64*
By Johannes A. Buchmann

Quantum computation is a thriving area of computer science. But what is a book on this subject doing in an undergraduate mathematics textbook series? As it turns out, quantum computation makes an excellent course for undergraduate mathematics majors. Naturally, students in such a course learn the basic principles of quantum information and fundamental quantum algorithms. But perhaps more importantly for math majors, the subject showcases advanced concepts of linear algebra and geometry in a natural, modern context. Other branches of mathematics, such as analysis, probability, number theory, representation theory, and category theory, are also likely to enter the fray. Learning quantum computation enhances students’ understanding and appreciation of physics and philosophy. Finally, the subject is undeniably weird and cool.

Johannes Buchmann’s Introduction to Quantum Algorithms, a new book in the AMS Pure and Applied Undergraduate Text Series,⁠Footnote¹ is well-suited to teach this delightful subject to mathematics majors in a rigorous way. Using this book effectively requires students to have successfully completed a proof-based linear algebra course and to have an appetite for rigorous mathematics. However, the book requires very little in the way of nonmathematical prerequisites; background concepts from computer science and physics, including a precise mathematical formulation of quantum mechanical postulates, are given a thorough treatment in the first chapters of the book. Throughout the book, Buchmann maintains a solidly mathematical perspective and high level of rigor. This will appeal to math professors and serious math students alike.

also known as the Sally Series, honoring the memory of beloved University of Chicago mathematician Paul Sally.

✖

Catcentennial

Happy 100th birthday, quantum mechanics! In the 1920s, physicists were starting to understand and formulate the laws that govern the small-scale world, seemingly quite different from what we observe with our eyes. Now accepted science, quantum mechanics, with all its strangeness—particle-wave duality, superpositions, and entanglement—can still boggle the mind. About 50 years ago, the idea that such strangeness could be harnessed for computational purposes started to emerge. Just over 30 years ago, Peter Shor found an algorithm for factoring integers in polynomial time on quantum computer. Shor also gave a quantum algorithm for computing discrete logarithms in polynomial time. These two algorithms, both based on the quantum Fourier transform, had enormous consequences for cryptography, since modern secure communication relies on the apparent difficulty of factoring and discrete logs on classical (i.e., nonquantum) computers.

Fortunately for the mathematician, only a few postulates, easily stated in the language of linear algebra, give a crisp mathematical framework for the quantum world. With these postulates, the foray into the world of complex inner product spaces, unitary transformations, and tensor products begins. The first postulate, the state space postulate, asserts that the state of a quantum system is described by a unit vector in a Hilbert space. Finite-dimensional state spaces mostly suffice for computational purposes; indeed, all of the spaces in Buchmann’s book are finite-dimensional. In this context, Hilbert space is synonymous with complex inner product space. According to the second postulate, the composite systems postulate, the state space of a composite system is the tensor product of the state spaces of the component systems. The evolution postulate asserts that quantum information can be processed by applying unitary transformations. Finally the measurement postulate gives a means of extracting information from a quantum state. Mathematically, a measurement is just a set of positive operators that sum to the identity.

Thus, from the very start, the conversation centers around interesting mathematical objects, just beyond the realm of a typical first course in linear algebra. Operators in this world are likely to be unitary or Hermitian, hence normal, so naturally the spectral theorem underlies the whole subject. In an introductory chapter on Hilbert spaces, Buchmann proves the spectral theorem using Schur decomposition, and he also introduces singular value decomposition and Schmidt decomposition.

A New Kind of Information

Interesting math already happens in the two-dimensional complex inner product space $V = \mathbb{C}^2$. The basic unit of quantum information is the qubit, which can be thought of as a unit vector $\vert \psi \rangle$ in $\mathbb{C}^2$. While a mathematician might denote a basis of this space by (1, 0) and (0, 1), in quantum computation, these standard basis vectors are denoted by $\vert 0\rangle$ and $\vert 1\rangle$, respectively. This Dirac notation, or “bra-ket” notation, is likely to confuse your students just up until the moment that it no longer confuses them. A qubit thus has the form $\alpha |0\rangle +\beta |1\rangle$, where $|\alpha |^2+|\beta |^2=1$. The measurement postulate allows you to measure this state, and the resulting state will be $|0\rangle$ with probability $|\alpha |^2$, and $\vert 1\rangle$, with probability $|\beta |^2$. For example, the equal superposition state, $\tfrac{1}{\sqrt {2}}\vert 0\rangle +\frac{1}{\sqrt {2}}|1\rangle$, when measured, turns into $|0\rangle$ or $|1\rangle$ with equal probability. This may remind your students of the famous cat that is either alive or dead, but whose status hasn’t been determined until we look. Mathematically, the measurement postulate applies due to the simple fact that the projection operators onto $|0\rangle$ and $|1\rangle$ sum to the identity. At this point, your students might realize that their hard work in linear algebra enables them to understand precisely the laws that govern quantum particles and felines.

A single qubit state $|\psi \rangle$ is represented by a point in the unit sphere in $\mathbb{C}^2$, a shape perhaps hard to visualize since it lives in four real dimensions. However, from the postulates, one sees straightaway that if $u$ is any unit complex number, then the quantum states $|\psi \rangle$ and $u|\psi \rangle$ are completely indistinguishable. This means that quantum state spaces are really quotient spaces, and leads into some lovely geometry. Every unit vector in $\mathbb{C}^2$ has the form $|\psi \rangle =u\bigg (\operatorname {cos}\bigg (\tfrac{\theta }{2}\bigg )\vert 0\rangle +\operatorname {sin}\bigg (\tfrac{\theta }{2}\bigg )e^{i\phi }\vert 1\rangle \bigg )$, where $u$ is a unit complex number, and $\theta \in [0,\pi ]$, $\phi \in [0,2\pi )$ can be interpreted as spherical coordinates. Thus, after you mod out by multiplication by unit complex numbers, the quotient space turns out to be a usual sphere $S^2$. This sphere is called the Bloch sphere, and its points are in one-to-one correspondence with single qubit states.

The plot thickens when one considers the allowable operations on single qubit states, namely the group $U(2)$ of $2\times 2$ unitary transformations. Here the crowning jewel is the isomorphism $SU(2)/\{\pm I\}\cong SO(3)$, which Buchmann creates with care in Chapter 4, with some help from the Pauli matrices. This isomorphism allows one to view unitary maps as acting by the Bloch sphere by rotations. This completes a very nice picture of quantum operations on single qubit states.

Spooky Action at a Distance

The curious phenomenon of quantum entanglement arises the moment one contemplates a multiple qubit system. An $n$-qubit system is a unit vector in the space $V=\mathbb{C}^2\otimes \dots \otimes \mathbb{C}^2$, the tensor product of $n$ copies of $\mathbb{C}^2$. This is a $2^n$-dimensional space with an orthonormal basis corresponding to strings of $n$ bits. For example, a 2-qubit state is a linear combination of the basis elements $|00\rangle$, $|01\rangle$, $|10\rangle$ and $|11\rangle$. In a tensor product $V\otimes W$, every vector can be written as a linear combination of vectors of the form $v\otimes w$, but most vectors cannot be written as a single tensor product. This gives a precise mathematical formulation of entanglement: A state $|\psi \rangle$ in a composite system is entangled if it cannot be written in the form $v\otimes w$. A notable example of an entangled state is the two-qubit state

$$\begin{equation*} \frac{1}{\sqrt {2}}(|00\rangle +|11\rangle ). \end{equation*}$$

A curious feature of this so-called Einstein-Podolsky-Rosen (EPR) pair arises when one measures the first qubit. The measurement postulate implies that the result of the measurement will be 0 or 1, with equal probability. When the result is 0, the state collapses to the $|00\rangle$ and otherwise collapses to $|11\rangle$. If the second qubit is now measured, the result will be the same, 0 or 1, as the result of the first measurement. And it doesn’t matter which qubit is measured first. Somehow measuring the one qubit determines the outcome of the measurement of the other qubit. Things get really weird when the two qubits are separated by a large distance. No information can travel faster than light, and yet making a measurement of one particle seems to have an instantaneous effect on the other particle. This strangeness, known as the EPR paradox, has been demonstrated physically, and presents a fundamental challenge to our notion of reality. The mathematics underlying the paradox is not hard, but you and your students will get the pleasure of playing with some two-dimensional projection operators and laws of probability.

A Universal Set of Gates

Computer science students learn that AND, OR, and NOT gates are universal for classical computation. Given any function $f\colon \mathbb{Z}^m_2\to \mathbb{Z}^n_2$ from bitstrings to bitstrings, there is a circuit for computing $f$ built out of these basic gates, which operate on only one or two bits at a time. In fact, these three gates can be replaced by a single gate, the NAND gate, which is universal all by itself. Buchmann proves these results in an extensive background chapter on classical computation. This chapter also includes a good introduction to probabilistic and reversible classical computation, topics that students are unlikely to have encountered before. The same chapter also rigorously introduces the complexity classes such as P, NP, and BPP (bounded-error probabilistic polynomial time), in preparation for introducing the quantum complexity class BQP (bounded-error quantum polynomial time) later in the book.

Naturally, one wonders which gates are universal for quantum computation. We seek a set of gates, each of which acts on a single qubit or two qubits, such that any unitary transformation on $n$ qubits can be built, at least approximately, out of the gates in our set. Even for single qubit operations this is an interesting problem. Via the close relation between $U(2)$ and $SO(3)$, we naturally arrive at a question of geometry: What basic rotations are needed to generate all rotations in three-space? Here one quickly enters the lovely classical world of Euler angles. If you fix your favorite two perpendicular axes in $\mathbb{R}^3$, say the $z$-axis and the $y$-axis, then every rotation in $SO(3)$ can be written as the product of a rotation around the $z$-axis, followed by rotation around the $y$-axis, followed by another rotation around the $z$-axis. When two axes are given that are not perpendicular, there is still a decomposition as a product of rotations around these two axes, where the number of factors in the product depends on the angle between the axes. These two decomposition theorems underpin important universality theorems for quantum computing. For example, Buchmann’s treatment culminates with Theorem 4.11.1, which asserts that a small number of single qubit operations and one two-qubit operation, the controlled NOT, can be used to approximate an arbitrary $n$-qubit operation. He mentions, but does not prove, the Solovay-Kitaev theorem regarding the efficiency of the approximations. Buchmann navigates this territory thoroughly, nicely allowing the geometry to play the starring role.

Searching for Something

New and interesting mathematics often arises organically when you try to move your favorite classical algorithm or theorem over to the quantum setting. Simply asking, “Hmm, is there a quantum version of this?” often leads you into the intricate, fun world of ideas that mathematicians like to inhabit.

A good example of this phenomenon is provided by Grover’s algorithm, covered in Chapter 7 of Buchmann’s text. One of the most celebrated quantum algorithms, Grover’s algorithm solves a problem known as unstructured search. Suppose there is a list of $N$ names, and the name GROVER appears somewhere in the list, say at position $a$. You are given the power to query this list: you name a number $j$, with $1\le j\le N$, and an oracle responds by telling you the $j$th name in the list. Your job is to determine the value of $a$, the position where GROVER appears in the list. If the list were alphabetically ordered, you could use a binary search to find the location of GROVER in about $\log _2(N)$ queries. However, the list is not promised to be ordered in any manner. This may sound like a silly problem. Indeed, there is no better strategy than going down the list, querying each name in succession, until you find GROVER. In the worst case, you will need to make $N-1$ queries to determine the value of $a$.

Any oracle problem such as the unstructured search problem has a quantum version, in which you can make quantum queries. Now, instead of querying with single value of $j$, you query with a linear combination of the basis states $|j\rangle$. (The details of how this works are found on p. 256.) It turns out that a single quantum oracle call can be used to create the vector in $\mathbb{C}^N$ whose coordinates are all 1, except the $a$th coordinate, which is $-1$. According to the postulates of quantum mechanics, we now face a question about the geometry of this collection of $N$ vectors in $\mathbb{C}^N$. If these vectors are orthogonal, we can distinguish them with probability 1. For $N=4$, this is in fact true. However, for large values of $N$, the vectors in question are far from orthogonal: they all point in nearly the same direction, the direction of the vector $(1,1,\dots ,1)$.

This lack of orthogonality means that a single query does not suffice; more queries are needed. Grover’s algorithm ultimately succeeds by rotating the state vector in the direction of the answer vector by a fixed angle with each query. After some analysis, one finds remarkably that only about $\sqrt {N}$ queries are needed to find $a$ with high probability. This represents a quadratic speedup over the $N-1$ classical queries required. A problem with very little interest classically becomes fertile ground for geometric thought and discovery.

From Fourier to Factoring

If you have a signal that exhibits periodic behavior, taking the Fourier transform is often useful. The values of the Fourier transform point you to the frequencies that comprise your signal. The discrete Fourier transform over $\mathbb{Z}_N$ is the map $F_N\colon \mathbb{C}^N\to \mathbb{C}^N$ defined as follows: let $\omega =\exp (2\pi i/N)$ be a primitive root of unity, and for $k=0,\dots ,N-1$, set $F_N\vert k\rangle =\tfrac{1}{\sqrt {N}}\sum ^{N-1}_{j=0}\omega ^{jk}\vert j\rangle$. That is, $F_N$ is the $N\times N$ matrix whose $j$, $k$ entry is $\tfrac{1}{\sqrt {N}}\omega ^{jk}$. Among other amazing properties, $F_N$ is unitary, and when $N=2^n$, there is a clever classical algorithm called the fast Fourier transform that requires about $N\log N$ steps to perform this transformation on a given vector. Quantum mechanically, there is a much faster algorithm, the quantum Fourier transform (QFT), that takes as input an $n$-qubit input state $|\psi \rangle \in (\mathbb{C}_2)^{\otimes n}$ and returns $F_N|\psi \rangle$ in only about $n^2$ steps. This represents an exponential speedup over the classical algorithm. This comes with the caveat that one only has access to $F_N\vert \psi \rangle$ via quantum measurement, which is much weaker access than the access one has to classical information. However, if the signal $|\psi \rangle$ is periodic, this quantum access is often sufficient, since $F_N\vert \psi \rangle$ will be highly spiked, and thus measuring $F_N\vert \psi \rangle$ will give one a good chance of being able to deduce the period.

Shor used the QFT to give a quantum algorithm for factoring integers in polynomial time. A key observation here is that factoring a number $N$ can be reduced to finding the order $\operatorname {ord}_N(a)$ of a given element $a\in \mathbb{Z}^*_N$, the multiplicative group modulo $N$. This ties immediately back to the Fourier transform since $\operatorname {ord}_N(a)$ is the period of the function $x\mapsto a^x\mod N$. Understanding Shor’s algorithm requires a careful look at some intricate yet elementary number theory, which may excite some of your students (and likely also their professor). Such students will be absolutely delighted by the appearance of continued fractions at the final step of Shor’s algorithm. This whole story is, of course, an excellent opportunity to dive into the wonderful, general story of Fourier transforms, which all math majors should encounter before being handed a degree.

In addition to the quantum factoring algorithm, Chapter 6 also presents Shor’s quantum algorithm for computing discrete logarithms in the multiplicative group $\mathbb{Z}^*_N$. Buchmann approaches this via quantum phase estimation and includes a section relating the discrete logarithm problem to the more general hidden subgroup problem.

The Road Not Taken

The field of quantum computing boasts an inordinate number of cool concepts with cool names. While some true scholars shun frivolity, many people are nevertheless attracted to math with fun names, such as “quantum teleportation,” “the Elitzur-Vaidman bomb,” “superdense coding,” “the no-cloning theorem,” etc. I wish the author had capitalized on the opportunity to include more of these fun, approachable topics. This choice may relate to the book’s focus specifically on quantum algorithms (the book’s title, after all), rather than the larger subject of quantum computation. Omitting such topics is not a huge flaw, since instructors can easily sprinkle in short discussions of these topics; students will certainly be well prepared by the foundational material covered in the book.

Naturally, there are also many larger topics in quantum computation that do not appear in the book. Quantum error correction stands out as an important topic with interesting mathematics that Buchmann decided not to include. Another such topic is lower bounds, i.e., limitations on what can be done with a quantum computer. For example, the $\sqrt {N}$ from Grover’s algorithm cannot be asymptotically improved. The hidden subgroup problem is mentioned at several points in the book, including a nice series of exercises leading to a solution for the group $\mathbb{Z}^n_2$. However, general approaches to the hidden subgroup problem are not explored. Going down this road establishes a nice framework for some of the existing quantum algorithms and leads students quickly into the world of representation theory. (The survey CvD10 is a useful source.) Omitting these topics was a reasonable choice, and again, the core material that Buchmann actually covers provides a good foundation for students and professors who wish to venture in these other directions.

There are many introductory books on quantum computing books of many different flavors. Ask someone who has taught the subject, and they will likely mention the rather comprehensive introduction by Nielsen and Chuang NC00, which balances the mathematical, computer science, and physics perspectives. The book by Kaye, Laflamme, and Mosca KLM07 covers the basics and has an entire chapter on lower bounds. Many students may appreciate the more intuitive approach of Mermin’s book Mer07, or Tom Wong’s delightfully elementary introduction to the subject Won22. If you teach a quantum computation course with a strong mathematical focus, or wish to push your course in a more mathematical direction, take a good look at Buchmann’s new book. Written with the math student in mind, the book provides a mathematically appealing approach, treating the required geometry and linear algebra with the care and depth it deserves.

It may be many years before we all have quantum computers on our desks. But in the meantime, the subject will provide mathematicians with complex and beautiful ideas, a seemingly endless supply of interesting problems, and a gateway to graduate-level mathematics.

Acknowledgment

The author thanks Daniel Copeland, Zeph Landau, David Meyer, Chinmay Nirkhe, Ryan O’Donnell, and the many students he has taught over the years.

References

[CvD10]: Andrew M. Childs and Wim van Dam, Quantum algorithms for algebraic problems, Rev. Modern Phys. 82 (2010), no. 1, 1–52, DOI 10.1103/RevModPhys.82.1. MR2629607,

Show rawAMSref
\bib{CvD10}{article}{ label={CvD10}, author={Childs, Andrew M.}, author={van Dam, Wim}, title={Quantum algorithms for algebraic problems}, journal={Rev. Modern Phys.}, volume={82}, date={2010}, number={1}, pages={1--52}, issn={0034-6861}, review={\MR {2629607}}, doi={10.1103/RevModPhys.82.1}, }
[KLM07]: Phillip Kaye, Raymond Laflamme, and Michele Mosca, An introduction to quantum computing, Oxford University Press, Oxford, 2007. MR2311153,

Show rawAMSref
\bib{KLM07}{book}{ label={KLM07}, author={Kaye, Phillip}, author={Laflamme, Raymond}, author={Mosca, Michele}, title={An introduction to quantum computing}, publisher={Oxford University Press, Oxford}, date={2007}, pages={xii+274}, isbn={978-0-19-857049-3}, isbn={0-19-857049-X}, review={\MR {2311153}}, }
[Mer07]: N. David Mermin, Quantum computer science: An introduction, Cambridge University Press, Cambridge, 2007, DOI 10.1017/CBO9780511813870. MR2341010,

Show rawAMSref
\bib{Mer07}{book}{ label={Mer07}, author={Mermin, N. David}, title={Quantum computer science}, subtitle={An introduction}, publisher={Cambridge University Press, Cambridge}, date={2007}, pages={xvi+220}, isbn={978-0-521-87658-2}, review={\MR {2341010}}, doi={10.1017/CBO9780511813870}, }
[NC00]: Michael A. Nielsen and Isaac L. Chuang, Quantum computation and quantum information, Cambridge University Press, Cambridge, 2000. MR1796805,

Show rawAMSref
\bib{NC00}{book}{ label={NC00}, author={Nielsen, Michael A.}, author={Chuang, Isaac L.}, title={Quantum computation and quantum information}, publisher={Cambridge University Press, Cambridge}, date={2000}, pages={xxvi+676}, isbn={0-521-63235-8}, isbn={0-521-63503-9}, review={\MR {1796805}}, }
[Won22]: T. G. Wong, Introduction to classical and quantum computing, Rooted Grove, 2022.

Graphic without alt text — Jamie Pommersheim is the Katharine Piggott Professor of Mathematics at Reed College. His email address is jamie@reed.edu.

Article DOI: 10.1090/noti3137

Credits

Photo of Jamie Pommersheim is courtesy of Jing-Ming Chen.

AMS Website Down