Course Home

Modular Arithmetic & the Quantum Fourier Transform

An interactive guide — from clock arithmetic to the heart of quantum algorithms.

1 Modular Arithmetic Basics

Modular arithmetic is "clock arithmetic." When numbers reach a modulus \(N\), they wrap back to zero — just like hours on a clock wrap after 12. Formally, we write \(a \equiv b \pmod{N}\) when \(N\) divides \(a - b\).

Interactive Clock Face

Pick a modulus and explore addition mod \(N\). Click any number on the clock to add it to the current value. Watch the arc trace the addition path.

Congruence Classes

Every integer belongs to exactly one residue class mod \(N\). Hover over a number to highlight its entire equivalence class — all the numbers that are "the same" mod \(N\).

Key idea: In modular arithmetic, we only care about the remainder after dividing by \(N\). Two numbers are "the same" if they share a remainder. This collapsing of infinitely many integers into \(N\) equivalence classes is exactly the periodicity that quantum algorithms exploit.

Check your understanding

What is \(15 + 19 \pmod{7}\)?

Click to reveal answer \(15 + 19 = 34\), and \(34 = 4 \times 7 + 6\), so the answer is 6. Equivalently, \(15 \equiv 1\) and \(19 \equiv 5\), and \(1 + 5 = 6\). Try it on the clock!

2 Modular Multiplication & Groups

The multiplication table mod \(N\) reveals deep structure. It shows which elements generate the entire group and exposes the cyclic patterns that connect to the QFT.

Cayley Table mod \(N\)

Toggle between addition and multiplication. Click a row header to see the cyclic subgroup generated by that element. Hover any cell to see the computation.

Key idea: The multiplicative group mod \(N\) has cyclic structure — elements raised to successive powers cycle through a subset of residues. This same cyclic behavior appears in the roots of unity that define the QFT matrix.

Check your understanding

In the addition table mod 6, what is \(4 + 5\)?

Click to reveal answer \(4 + 5 = 9 \equiv 3 \pmod{6}\). The result wraps back around, just like on the clock! Try it in the table!

3 Roots of Unity on the Unit Circle

The \(N\)-th roots of unity are the complex numbers \(\omega^k = e^{2\pi i k/N}\) for \(k = 0, 1, \ldots, N-1\). They are evenly spaced on the unit circle and form a group under multiplication.

Interactive Unit Circle

Click a root to inspect it. Then select two roots and press Multiply to see how complex multiplication corresponds to adding exponents mod \(N\). The arc shows the rotation.

Click a root on the circle to inspect it.
×
The bridge: Multiplying two roots of unity \(\omega^j \cdot \omega^k = \omega^{(j+k) \bmod N}\) reduces complex multiplication to modular addition of exponents. This is precisely why modular arithmetic is the algebraic engine behind the QFT.

Check your understanding

For \(N = 6\), what is \(\omega^4 \cdot \omega^5\)? Where does it land on the unit circle?

Click to reveal answer \(\omega^4 \cdot \omega^5 = \omega^{4+5} = \omega^{9 \bmod 6} = \omega^3\). Since \(\omega^3 = e^{2\pi i \cdot 3/6} = e^{i\pi} = -1\), it lands at the leftmost point of the unit circle (180°). Try it on the unit circle!
Where we are: We've seen that modular arithmetic wraps numbers (Section 1), creates cyclic groups (Section 2), and governs how roots of unity multiply on the unit circle (Section 3). Now we'll see how the Quantum Fourier Transform packages all of these ideas into a single matrix.

4 The QFT Matrix Connection

The Quantum Fourier Transform on \(N\) states is defined by the unitary matrix:

$$F_N = \frac{1}{\sqrt{N}} \begin{pmatrix} 1 & 1 & 1 & \cdots & 1 \\ 1 & \omega & \omega^2 & \cdots & \omega^{N-1} \\ 1 & \omega^2 & \omega^4 & \cdots & \omega^{2(N-1)} \\ \vdots & & & \ddots & \vdots \\ 1 & \omega^{N-1} & \omega^{2(N-1)} & \cdots & \omega^{(N-1)^2} \end{pmatrix}$$

where \(\omega = e^{2\pi i / N}\). Entry \((j, k)\) is \(\frac{1}{\sqrt{N}}\,\omega^{jk}\), and the exponent \(jk\) is computed mod \(N\) — connecting us directly back to Section 1.

Interactive QFT Phase Map

Each cell shows the phase \(\omega^{jk \bmod N}\) as a colored disc with the exponent label. Hover a cell for the full computation. Click a column header \(|k\rangle\) to see the QFT output vector visualized on the unit circle.

 

Worked Example: Step Through the QFT

Choose an input state and watch the QFT decompose it row by row. Each step shows how modular arithmetic determines the phase.

1 / 1 ←→ arrow keys

Check your understanding

In the \(N=4\) QFT matrix, what is the phase of entry \((3, 2)\)? Express it as a power of \(\omega\) and as a complex number.

Click to reveal answer The exponent is \(3 \times 2 = 6 \equiv 2 \pmod{4}\), so the entry is \(\frac{1}{\sqrt{4}}\omega^2\). Since \(\omega = e^{2\pi i/4} = i\), we get \(\omega^2 = i^2 = -1\). So the entry is \(\frac{-1}{2}\). Verify it in the matrix!
The punchline: Every entry of the QFT matrix is determined by a single modular multiplication \(jk \bmod N\). The entire power of the quantum Fourier transform — period finding, phase estimation, Shor's algorithm — rests on this elegant connection between modular arithmetic and the roots of unity.