Exam Prep — QFT Computation

Method

The QFT formula

The Quantum Fourier Transform $F_N$ maps each computational basis state:

$$F_N\ket{x} = \frac{1}{\sqrt{N}} \sum_{j=0}^{N-1} \omega^{jx} \ket{j} \qquad \text{where } \omega = e^{2\pi i / N}$$

For superpositions: $F_N$ is linear. Apply it to each basis state separately, then add:

$$F_N\!\bigl(\alpha\ket{a} + \beta\ket{b}\bigr) = \alpha\, F_N\ket{a} \;+\; \beta\, F_N\ket{b}$$

Key simplification: After expanding, collect coefficients of each $\ket{j}$ and use the geometric series rule to cancel most terms.

Every exam QFT problem follows the same pattern: expand, collect, cancel. The geometric series rule does the heavy lifting.

Roots of Unity Reference

Powers of $\omega$ for common $N$

$N = 2$: $\omega = e^{i\pi} = -1$

$k$	0	1
$\omega^k$	$1$	$-1$

$N = 4$: $\omega = e^{i\pi/2} = i$

$k$	0	1	2	3
$\omega^k$	$1$	$i$	$-1$	$-i$

$N = 8$: $\omega = e^{i\pi/4} = \frac{1+i}{\sqrt{2}}$

$k$	0	1	2	3	4	5	6	7
$\omega^k$	$1$	$\frac{1+i}{\sqrt{2}}$	$i$	$\frac{-1+i}{\sqrt{2}}$	$-1$	$\frac{-1-i}{\sqrt{2}}$	$-i$	$\frac{1-i}{\sqrt{2}}$

Memorise $N=4$ ($\omega = i$). It covers most exam problems. For $N=8$, just remember $\omega = e^{i\pi/4}$ and compute powers as needed.

Geometric Series Rule

The cancellation that simplifies everything

$$\frac{1}{N}\sum_{j=0}^{N-1} \omega^{kj} = \begin{cases} 1 & \text{if } k \equiv 0 \pmod{N} \\ 0 & \text{otherwise} \end{cases}$$

Equivalently: $\displaystyle\sum_{j=0}^{N-1} \omega^{kj} = N \cdot \delta_{k \bmod N,\, 0}$.

When $k \not\equiv 0$, the $N$ roots of unity are evenly spaced around the unit circle and sum to zero. When $k \equiv 0$, every term is $\omega^0 = 1$, so the sum is $N$.

Small example ($N=4$, $\omega = i$):

\(k = 1\): terms don't cancel to zero? Let's check $$\sum_{j=0}^{3} \omega^{1 \cdot j} = \omega^0 + \omega^1 + \omega^2 + \omega^3 = 1 + i + (-1) + (-i) = 0 \quad \checkmark$$ \(k = 0\): every term is 1 $$\sum_{j=0}^{3} \omega^{0 \cdot j} = 1 + 1 + 1 + 1 = 4 = N \quad \checkmark$$

On the exam: after expanding $F_N$ on a superposition and collecting the coefficient of $\ket{j}$, you'll see sums of the form $\sum_x \omega^{jx}$. Apply this rule to kill all but one or two terms.

Worked Examples

Example 1 — $F_2$ on $\ket{0}$ and $\ket{1}$ (= Hadamard)

Compute $F_2\ket{0}$ and $F_2\ket{1}$. Here $N=2$, $\omega = e^{2\pi i/2} = e^{i\pi} = -1$.

\(F_2\ket{0}\) $$F_2\ket{0} = \frac{1}{\sqrt{2}}\sum_{j=0}^{1} \omega^{j \cdot 0}\ket{j} = \frac{1}{\sqrt{2}}\bigl(\omega^0\ket{0} + \omega^0\ket{1}\bigr) = \frac{1}{\sqrt{2}}\bigl(\ket{0} + \ket{1}\bigr) = \ket{+}$$ \(F_2\ket{1}\) $$F_2\ket{1} = \frac{1}{\sqrt{2}}\sum_{j=0}^{1} \omega^{j \cdot 1}\ket{j} = \frac{1}{\sqrt{2}}\bigl(\omega^0\ket{0} + \omega^1\ket{1}\bigr) = \frac{1}{\sqrt{2}}\bigl(\ket{0} - \ket{1}\bigr) = \ket{-}$$

Sanity check: $F_2 = \frac{1}{\sqrt{2}}\bigl(\begin{smallmatrix}1 & 1 \\ 1 & -1\end{smallmatrix}\bigr) = H$. The QFT on 1 qubit is the Hadamard gate.

Example 2 — $F_4\ket{2}$

Compute $F_4\ket{2}$. Here $N=4$, $\omega = i$.

Apply the formula $$F_4\ket{2} = \frac{1}{\sqrt{4}}\sum_{j=0}^{3} \omega^{2j}\ket{j} = \frac{1}{2}\bigl(\omega^0\ket{0} + \omega^2\ket{1} + \omega^4\ket{2} + \omega^6\ket{3}\bigr)$$ Compute each power (using \(\omega = i\), reduce mod 4) $$\omega^0 = 1, \quad \omega^2 = i^2 = -1, \quad \omega^4 = i^4 = 1, \quad \omega^6 = i^6 = i^4 \cdot i^2 = -1$$ Substitute $$F_4\ket{2} = \frac{1}{2}\bigl(\ket{0} - \ket{1} + \ket{2} - \ket{3}\bigr)$$

Notice the alternating $+1, -1$ pattern. This happens because $\omega^2 = -1$ for $N=4$, so $\omega^{2j}$ alternates sign.

Example 3 — $F_4$ on $\frac{1}{2}(\ket{0}+\ket{1}+\ket{2}+\ket{3})$

Compute $F_4 \cdot \frac{1}{2}(\ket{0}+\ket{1}+\ket{2}+\ket{3})$.

Step 1 — Apply linearity $$F_4\!\left(\frac{1}{2}\sum_{x=0}^{3}\ket{x}\right) = \frac{1}{2}\sum_{x=0}^{3} F_4\ket{x} = \frac{1}{2}\sum_{x=0}^{3}\frac{1}{2}\sum_{j=0}^{3}\omega^{jx}\ket{j}$$ Step 2 — Swap the sums (collect coefficient of each \(\ket{j}\)) $$= \frac{1}{4}\sum_{j=0}^{3}\left(\sum_{x=0}^{3}\omega^{jx}\right)\ket{j}$$ Step 3 — Apply geometric series rule $$\sum_{x=0}^{3}\omega^{jx} = \begin{cases} 4 & \text{if } j = 0 \\ 0 & \text{if } j = 1, 2, 3 \end{cases}$$ Step 4 — Only \(j=0\) survives $$= \frac{1}{4} \cdot 4 \cdot \ket{0} = \ket{0}$$

The uniform superposition $\frac{1}{\sqrt{N}}\sum_x \ket{x}$ is exactly $F_N\ket{0}$, so applying $F_N$ again gives $\ket{0}$ (since $F_N^2$ is close to identity — specifically, $F_N^2$ is the "reversal" operator, which maps $\ket{0} \to \ket{0}$).

Example 4 — $F_4$ on $\frac{1}{2}(\ket{0}-\ket{1}+\ket{2}-\ket{3})$ (exam-level)

Compute $F_4 \cdot \frac{1}{2}(\ket{0}-\ket{1}+\ket{2}-\ket{3})$.

Step 1 — Rewrite the signs as powers of \(\omega\) The coefficients are \(+1, -1, +1, -1\). Since \(\omega^2 = i^2 = -1\), we have \((-1)^x = \omega^{2x}\). So: $$\frac{1}{2}\sum_{x=0}^{3}(-1)^x\ket{x} = \frac{1}{2}\sum_{x=0}^{3}\omega^{2x}\ket{x}$$ Recognise this: from Example 2, this is \(F_4\ket{2}\). So we're computing \(F_4(F_4\ket{2})\). Step 2 — Apply \(F_4\) and collect $$F_4\!\left(\frac{1}{2}\sum_{x=0}^{3}\omega^{2x}\ket{x}\right) = \frac{1}{2}\sum_{x=0}^{3}\omega^{2x}\cdot\frac{1}{2}\sum_{j=0}^{3}\omega^{jx}\ket{j} = \frac{1}{4}\sum_{j=0}^{3}\left(\sum_{x=0}^{3}\omega^{(j+2)x}\right)\ket{j}$$ Step 3 — Apply geometric series rule with \(k = j+2\) $$\sum_{x=0}^{3}\omega^{(j+2)x} = \begin{cases} 4 & \text{if } j+2 \equiv 0 \pmod{4}, \text{ i.e. } j = 2 \\ 0 & \text{otherwise} \end{cases}$$ Step 4 — Only \(j=2\) survives $$= \frac{1}{4}\cdot 4 \cdot \ket{2} = \ket{2}$$

Pattern: the input was $F_4\ket{2}$, and applying $F_4$ again gave $\ket{2}$. For $F_4$, applying it twice to $\ket{x}$ gives $\ket{(-x) \bmod 4}$. Since $-2 \equiv 2 \pmod{4}$, we get $\ket{2}$.

Watch Out

Common pitfalls

$N$ vs $n$. $N$ is the number of basis states (the dimension), $n$ is the number of qubits. They're related by $N = 2^n$. The formula uses $N$, not $n$. For 2 qubits, $N = 4$, not 2.
Forgetting $1/\sqrt{N}$. Every $F_N\ket{x}$ has a $1/\sqrt{N}$ prefactor. When the input also has a prefactor (like $1/2$ for a uniform superposition over 4 states), multiply them: $\frac{1}{2} \cdot \frac{1}{2} = \frac{1}{4}$.
Sign errors in $\omega$ powers. Reduce exponents mod $N$. For $N=4$: $\omega^5 = \omega^1 = i$, not $-i$. Write out the power table if unsure.
Not using the geometric series rule. If you're computing 16 individual terms for $F_4$ on a 4-term superposition, you're doing it wrong. Swap the sums, identify $\sum \omega^{kx}$, and cancel.
Confusing $F_N$ with $F_N^\dagger$. The inverse QFT uses $\omega^{-jx}$ (negative exponent). The exam will specify which one — read carefully.

Practice

Problem 1

Compute $F_4\ket{1}$. Express the result using powers of $\omega = i$, then simplify to explicit coefficients.

Solution

$$F_4\ket{1} = \frac{1}{2}\sum_{j=0}^{3}\omega^{j \cdot 1}\ket{j} = \frac{1}{2}\bigl(\ket{0} + i\ket{1} - \ket{2} - i\ket{3}\bigr)$$

Powers used: $\omega^0 = 1$, $\omega^1 = i$, $\omega^2 = -1$, $\omega^3 = -i$.

Problem 2

Compute $F_4\ket{3}$.

Solution

$$F_4\ket{3} = \frac{1}{2}\sum_{j=0}^{3}\omega^{3j}\ket{j} = \frac{1}{2}\bigl(\omega^0\ket{0} + \omega^3\ket{1} + \omega^6\ket{2} + \omega^9\ket{3}\bigr)$$

Reduce mod 4: $\omega^0 = 1$, $\omega^3 = -i$, $\omega^6 = \omega^2 = -1$, $\omega^9 = \omega^1 = i$.

$$F_4\ket{3} = \frac{1}{2}\bigl(\ket{0} - i\ket{1} - \ket{2} + i\ket{3}\bigr)$$

Problem 3

Compute $F_4 \cdot \frac{1}{2}(\ket{0} + i\ket{1} - \ket{2} - i\ket{3})$.

Hint: recognise the input first.

Solution

The coefficients are $1, i, -1, -i = \omega^0, \omega^1, \omega^2, \omega^3$. So the input is $\frac{1}{2}\sum_{x=0}^{3}\omega^{x}\ket{x} = F_4\ket{1}$.

Apply $F_4$:

$$F_4\!\left(\frac{1}{2}\sum_{x=0}^{3}\omega^{x}\ket{x}\right) = \frac{1}{4}\sum_{j=0}^{3}\left(\sum_{x=0}^{3}\omega^{(j+1)x}\right)\ket{j}$$

Geometric series: $\sum_{x}\omega^{(j+1)x} = 4$ when $j+1 \equiv 0 \pmod{4}$, i.e. $j = 3$. Zero otherwise.

$$= \frac{1}{4}\cdot 4 \cdot \ket{3} = \ket{3}$$

$F_4^2\ket{1} = \ket{-1 \bmod 4} = \ket{3}$. Checks out.

Problem 4

Compute $F_2 \cdot \frac{1}{\sqrt{2}}(\ket{0} - \ket{1})$.

Solution

Here $N=2$, $\omega = -1$. The input is $\frac{1}{\sqrt{2}}(\ket{0} - \ket{1}) = \ket{-}$. Recognise: this is $F_2\ket{1}$.

Direct computation:

$$F_2\!\left(\frac{1}{\sqrt{2}}(\ket{0}-\ket{1})\right) = \frac{1}{\sqrt{2}}\bigl(F_2\ket{0} - F_2\ket{1}\bigr)$$

$$= \frac{1}{\sqrt{2}}\left[\frac{1}{\sqrt{2}}(\ket{0}+\ket{1}) - \frac{1}{\sqrt{2}}(\ket{0}-\ket{1})\right] = \frac{1}{2}\bigl[2\ket{1}\bigr] = \ket{1}$$

Or by the geometric series shortcut: input coefficients are $1, -1 = \omega^0, \omega^1$, so input is $F_2\ket{1}$. Then $F_2^2\ket{1} = \ket{-1 \bmod 2} = \ket{1}$.

Problem 5

Compute $F_8\!\left(\frac{1}{\sqrt{2}}(\ket{0} + \ket{4})\right)$.

Hint: after expanding, which values of $j$ survive?

Solution

Here $N=8$, $\omega = e^{2\pi i/8} = e^{i\pi/4}$.

$$F_8\!\left(\frac{1}{\sqrt{2}}(\ket{0}+\ket{4})\right) = \frac{1}{\sqrt{2}}\left(\frac{1}{\sqrt{8}}\sum_{j=0}^{7}\omega^{0 \cdot j}\ket{j} + \frac{1}{\sqrt{8}}\sum_{j=0}^{7}\omega^{4j}\ket{j}\right)$$

$$= \frac{1}{\sqrt{16}}\sum_{j=0}^{7}(1 + \omega^{4j})\ket{j} = \frac{1}{4}\sum_{j=0}^{7}(1 + \omega^{4j})\ket{j}$$

Now $\omega^4 = e^{i\pi} = -1$, so $\omega^{4j} = (-1)^j$. Therefore:

$$1 + \omega^{4j} = 1 + (-1)^j = \begin{cases} 2 & \text{if } j \text{ even} \\ 0 & \text{if } j \text{ odd}\end{cases}$$

Only even $j$ survive:

$$= \frac{1}{4}\bigl(2\ket{0} + 2\ket{2} + 2\ket{4} + 2\ket{6}\bigr) = \frac{1}{2}\bigl(\ket{0} + \ket{2} + \ket{4} + \ket{6}\bigr)$$

Example 1 — \(F_2\) on \(\ket{0}\) and \(\ket{1}\) (= Hadamard)

Example 2 — \(F_4\ket{2}\)

Example 3 — \(F_4\) on \(\frac{1}{2}(\ket{0}+\ket{1}+\ket{2}+\ket{3})\)

Example 4 — \(F_4\) on \(\frac{1}{2}(\ket{0}-\ket{1}+\ket{2}-\ket{3})\) (exam-level)