Period Finding as HSP

Shor's factoring algorithm, the most celebrated application of quantum computing, rests on a single mathematical engine: period finding. Once you understand how period finding fits inside the Hidden Subgroup Problem (HSP) framework, the structure of the algorithm becomes almost inevitable.

What period finding asks

Fix a positive integer $N$ and an integer $a$ with $\gcd(a, N) = 1$. Define the function

$f(x) = a^x \bmod N, \qquad x \in \mathbb{Z}_{\geq 0}.$

Because the multiplicative group $\mathbb{Z}_N^*$ is finite, this function is periodic: there exists a smallest positive integer $r$ (the order of $a$ modulo $N$) such that

$a^r \equiv 1 \pmod{N}, \quad \text{and therefore } f(x + r) = f(x) \text{ for all } x.$

The period $r$ is the information Shor needs. Given $r$, a simple classical calculation finds a non-trivial factor of $N$ with probability at least $\tfrac{1}{2}$ (Nielsen & Chuang, §5.3): if $r$ is even and $a^{r/2} \not\equiv -1 \pmod{N}$, then $\gcd(a^{r/2} \pm 1, N)$ yields a factor.

Casting period finding as an HSP

To place period finding inside the HSP framework, we work over the group $G = \mathbb{Z}$ (the integers under addition), but in practice a finite approximation suffices — use $G = \mathbb{Z}_M$ for a large power of two $M \geq N^2$.

The function $f(x) = a^x \bmod N$ has a crucial property: it takes the same value on a whole coset of $r\mathbb{Z}$ and distinct values across different cosets. In HSP language:

• The group is $G = \mathbb{Z}_M$.
• The hidden subgroup is $H = r\mathbb{Z}_M = \{0, r, 2r, \ldots\}$ (the multiples of $r$ inside $\mathbb{Z}_M$).
• $f$ is constant on every left coset $x + H$ and distinct across cosets.

Finding $r$ is therefore the same as finding the generator of the hidden subgroup $H \leq \mathbb{Z}_M$.

Because $\mathbb{Z}_M$ is abelian, this is an instance of the abelian HSP, which is efficiently solvable by the standard quantum HSP algorithm using the Quantum Fourier Transform (QFT).

The quantum algorithm in four steps

The abelian-HSP template applied to period finding gives exactly Shor's circuit:

1. Prepare a uniform superposition of the first (index) register over $\mathbb{Z}_M$:

   $\frac{1}{\sqrt{M}} \sum_{x=0}^{M-1} |x\rangle |0\rangle.$

2. Query the oracle $U_f : |x\rangle|y\rangle \mapsto |x\rangle|y \oplus f(x)\rangle$, creating the entangled state

   $\frac{1}{\sqrt{M}} \sum_{x=0}^{M-1} |x\rangle |a^x \bmod N\rangle.$

3. Measure the second register. Suppose the outcome is $a^{x_0} \bmod N$ for some $x_0$. The first register collapses to the uniform superposition over the coset

   $|x_0 + H\rangle = \frac{1}{\sqrt{M/r}} \sum_{k=0}^{M/r - 1} |x_0 + kr\rangle.$

4. Apply the QFT to the first register. The QFT maps the uniform superposition over $x_0 + H$ to amplitudes that are non-zero only at integer multiples of $M/r$:

   $\frac{1}{\sqrt{r}} \sum_{j=0}^{r-1} e^{2\pi i x_0 j / r} \left| j \cdot \frac{M}{r} \right\rangle.$

   Measuring yields a uniformly random $j \cdot M/r$. The ratio $j/r$ can be extracted from this integer by classical continued-fraction expansion, giving $r$ in $O(1)$ repetitions.

The measurement step (step 3) is not strictly necessary — modern presentations skip it and show that the QFT still produces the right distribution — but it makes the coset structure transparent.

Why the QFT is the right tool

The QFT over $\mathbb{Z}_M$ is the quantum analogue of the discrete Fourier transform. Its defining action is

$\text{QFT}_M |x\rangle = \frac{1}{\sqrt{M}} \sum_{y=0}^{M-1} e^{2\pi i xy / M} |y\rangle.$

A state that is uniform over an arithmetic progression with step $r$ (i.e., the coset $x_0 + H$) has a discrete Fourier transform that is itself concentrated on multiples of $1/r$. The QFT makes this frequency visible in the computational basis, where a single measurement reads it off. This is the Fourier sampling principle that underlies every abelian HSP algorithm.

Complexity

The QFT over $\mathbb{Z}_M$ (with $M = 2^L$ for $L = O(\log N)$ qubits) requires only $O(L^2) = O(\log^2 N)$ gates (Nielsen & Chuang, §5.1). The modular exponentiation oracle is implementable in $O(\log^3 N)$ gates using repeated squaring. The total circuit depth is therefore $O(\log^3 N)$, compared to the best known classical factoring algorithm (the Number Field Sieve), which runs in sub-exponential time $\exp\!\left(O((\log N)^{1/3}(\log\log N)^{2/3})\right)$ — an exponential quantum speedup for large $N$.

The HSP unification

Period finding joins a family of problems that all reduce to the abelian HSP:

| Problem | Group $G$ | Hidden subgroup $H$ | |---|---|---| | Deutsch-Jozsa | $\mathbb{Z}_2$ | $\{0\}$ or $\mathbb{Z}_2$ | | Simon's problem | $(\mathbb{Z}_2)^n$ | $\{0^n, s\}$ | | Period finding (Shor) | $\mathbb{Z}_M$ | $r\mathbb{Z}_M$ | | Discrete logarithm | $\mathbb{Z}_r \times \mathbb{Z}_r$ | a cyclic subgroup |

All of these are solved by the same algorithmic template: prepare a uniform superposition, query the oracle, apply the appropriate group-theoretic Fourier transform, measure, and use classical post-processing to identify the hidden subgroup. The next lesson examines what happens when we move beyond abelian groups, where this beautiful template breaks down.

Sign in on the full site to ask questions and join the discussion.