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

Question

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?

Answer 1

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.