The Exercise

A list of $N = 2^n$ complex numbers $x_0, \dots, x_{N-1}$, as many as the amplitudes of $n$ qubits, is to be Fourier transformed on a classical computer. The discrete Fourier transform sends it to the list $y_0, \dots, y_{N-1}$ with $$y_k = \frac{1}{\sqrt{N}} \sum_{j=0}^{N-1} e^{2\pi i jk/N} x_j .$$(1) The exercise asks how the number of elementary arithmetic operations grows with $n$, once when (1) is evaluated directly, one output $y_k$ at a time, and once when the transform is computed by the fast Fourier transform.

The Operation Counts

The operation count $T_{\mathrm{dir}}(n)$ of the direct evaluation of a transform of $2^n$ numbers is the whole number $$T_{\mathrm{dir}}(n) = 4^n + 2^n \bigl(2^n - 1\bigr),$$(2)^✦

The fast Fourier transform’s operation count $T_{\mathrm{FFT}}(n)$ for $2^n$ numbers satisfies the recursion $$T_{\mathrm{FFT}}(0) = 0, \qquad T_{\mathrm{FFT}}(n+1) = 2\,T_{\mathrm{FFT}}(n) + 2^{n+1}.$$(3)^✦

The Claim

For real functions $f$ and $g$ of the whole number $n$, $f(n) = \Theta(g(n))$ means that there are constants $c, C > 0$ and $n_0$ with $c\,g(n) \le f(n) \le C\,g(n)$ for all $n \ge n_0$.

What Is Checked

The claim is stated over the two operation counts: the closed formula (2) for the direct evaluation and the recursion (3) for the fast Fourier transform.

What the library proves about these counts is their order of growth, (4) for the direct evaluation and (5) for the fast Fourier transform.