Quantum algorithms for algebraic problems

Quantum computers can execute algorithms that dramatically outperform classical computation. As the best-known example, Shor discovered an efficient quantum algorithm for factoring integers, whereas factoring appears to be difficult for classical computers. Understanding what other computational problems can be solved significantly faster using quantum algorithms is one of the major challenges in the theory of quantum computation, and such algorithms motivate the formidable task of building a large-scale quantum computer. This article reviews the current state of quantum algorithms, focusing on algorithms with superpolynomial speedup over classical computation and, in particular, on problems with an algebraic flavor.

Figure 1

An efficient [size $O\left(n^2\right)$] quantum circuit for the quantum Fourier transform over $\mathbb{Z}∕2^n\mathbb{Z}$. Note that the order of the $n$ output bits $z_0,\dots ,z_{n-1}$ is reversed, as compared with the order of the $n$ input bits $x_0,\dots ,x_{n-1}$.

Figure 2

Sampling a $\mathbb{Z}$-periodic function over $\mathbb{Z}∕N\mathbb{Z}$.

Figure 3

The group law for an elliptic curve: $P+Q=-R$. The points $P$ and $Q$ sum to the point $-R$, where $R$ is the intersection between the elliptic curve and the line through $P$ and $Q$ and $-R$ is obtained by the reflection of $R$ about the $x$ axis.