# How is this definition of the quantum Fourier transform to be understood?

In regards to the quantum Fourier transform Page 845 of The Nature of Computation states

The amplitudes $\tilde{a}_\mathbf{k}$ are the Fourier coefficients of $a_\mathbf{x}$, $$\tilde{a}_\mathbf{k} = \langle \mathbf{k}|\psi\rangle = \frac{1}{\sqrt{2^n}}\sum_\mathbf{x}(-1)^{\mathbf{k\cdot x}}a_\mathbf{x}\,.$$

Here $x$'s are the standard basis vectors and the $k$'s are (presumably) the Fourier basis. And $\psi = \sum_\mathbf{x} a_\mathbf{x}|\mathbf{x}\rangle$.
To pick a concrete example let the number of qubits, $n$, be 2. The book isn't clear on this but my first guess is that the $\mathbf{k}$'s should be these:

$$\begin{bmatrix}1/2\\1/2\\1/2\\1/2\end{bmatrix}, \begin{bmatrix}1/2\\-i/2\\-1/2\\i/2\end{bmatrix},\begin{bmatrix}1\\-1\\1\\-1\end{bmatrix},\begin{bmatrix}1/2\\i/2\\-1/2\\-i/2\end{bmatrix}.$$

Though, I've also heard the argument that they should be the columns of

$$H \otimes H = \begin{bmatrix}1/2 & 1/2 & 1/2 & 1/2\\1/2 & -1/2 & 1/2 & -1/2\\1/2 & 1/2 & -1/2 & -1/2\\1/2 & -1/2 & -1/2 & 1/2 \end{bmatrix},$$

where $H$ is the $2\times 2$ Hadamard matrix. However, the book also states that

each "frequency" is, like $\mathbf{x}$, an $n$-dimensional vector mod 2.

And I don't see how to convert the entries of either of these bases into elements of $\mathbb{Z}_2$.
Ignoring that issue I immediately run in to the following. Take the first vector of either basis as $\mathbf{k}$ and compute the Fourier coefficient $\tilde{a}_\mathbf{k}$ according to the definition above while also using $|\psi\rangle = \begin{bmatrix} 1/2 & 1/2 & 1/2 & 1/2\end{bmatrix}^T$ as an example. On the one hand

$$\langle\mathbf{k}|\psi\rangle = 1\,.$$

But on the other hand

$$\frac{1}{\sqrt{2^n}}\sum_\mathbf{x}(-1)^{\mathbf{k\cdot x}}a_\mathbf{x} = \frac{1}{2} \left((-1)^{1/2}\frac{1}{2} + (-1)^{1/2}\frac{1}{2} + (-1)^{1/2}\frac{1}{2} + (-1)^{1/2}\frac{1}{2}\right) = i\,.$$

What am I not getting here?

The index $\mathbf{k}$ goes over all vectors in $\{0,1\}^n$ (which can be identified with $\mathbb{Z}_2^n$). The index $\mathbf{x}$ also has the same range, and $\mathbf{k} \cdot \mathbf{x} = \sum_{i=1}^n k_i x_i$. You can think of this sum as being computed modulo 2 (or in $\mathbb{Z}_2$) if you wish, since $(-1)^2 = 1$.
As an example, when $n = 2$ we get \begin{align*} \tilde{a}_{00} &= \frac{a_{00} + a_{01} + a_{10} + a_{11}}{2}, \\ \tilde{a}_{01} &= \frac{a_{00} - a_{01} + a_{10} - a_{11}}{2}, \\ \tilde{a}_{10} &= \frac{a_{00} + a_{01} - a_{10} - a_{11}}{2}, \\ \tilde{a}_{11} &= \frac{a_{00} - a_{01} - a_{10} + a_{11}}{2}. \end{align*}
This is exactly the tensor square of the $2\times 2$ Hadamard matrix.
• I see at least one major point I was confused about, namely $\mathbf{k} \neq |\mathbf{k}\rangle$. So if $\mathbf{k} = \begin{bmatrix}0 & 0\end{bmatrix}^T$ then $|\mathbf{k}\rangle = \begin{bmatrix}1&0&0&0\end{bmatrix}^T$. Commented Jan 18, 2018 at 15:42
• However, then I'm confused by the following: $$|\psi\rangle = \sum_\mathbf{x} a_\mathbf{x}|\mathbf{x}\rangle = \sum_\mathbf{k} \tilde{a}_\mathbf{k}|\mathbf{k}\rangle\,.$$ Doesn't this imply in the case $n = 1$ $$a_{|0\rangle}|0\rangle + a_{|1\rangle}|1\rangle = \tilde{a}_{|0\rangle}|0\rangle + \tilde{a}_{|1\rangle}|1\rangle$$ and similarly all the coefficients are equal for all $n$? Commented Jan 18, 2018 at 15:47
• The quantum Fourier transform on $n$ bits is the same as applying the $n$th tensor power of the 2×2 Hadamard matrix. This should answer all your questions. Commented Jan 18, 2018 at 15:49
• You can derive the vector form of $\mathbf{k}$ using the identity $\tilde{a}_{\mathbf{k}} = \langle \mathbf{k} | \mathbf{\psi} \rangle$. Commented Jan 18, 2018 at 15:50
• But when you state "$\mathbf{k}$ goes over all vectors in $\{0,1\}^n$" aren't you saying that for $n=2$ the first vector is $\mathbf{k} = \begin{bmatrix}0 & 0\end{bmatrix}^T$ and $|\mathbf{k}\rangle = \begin{bmatrix}1&0&0&0\end{bmatrix}^T$? So $\langle 0 0|\psi\rangle = \psi_0\,.$ That doesn't look like a Fourier coefficient to me. That's a standard basis coefficient. Commented Jan 18, 2018 at 16:02