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 &amp; 1/2 &amp; 1/2 &amp; 1/2\\1/2 &amp; -1/2 &amp; 1/2 &amp; -1/2\\1/2 &amp; 1/2 &amp; -1/2 &amp; -1/2\\1/2 &amp; -1/2 &amp; -1/2 &amp; 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 &amp; 1/2 &amp; 1/2 &amp; 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} &amp;= \frac{a_{00} + a_{01} + a_{10} + a_{11}}{2}, \\
\tilde{a}_{01} &amp;= \frac{a_{00} - a_{01} + a_{10} - a_{11}}{2}, \\
\tilde{a}_{10} &amp;= \frac{a_{00} + a_{01} - a_{10} - a_{11}}{2}, \\
\tilde{a}_{11} &amp;= \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.