3
$\begingroup$

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?

$\endgroup$
1
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ 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$. $\endgroup$ – Sebastian Oberhoff Jan 18 '18 at 15:42
  • $\begingroup$ 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$? $\endgroup$ – Sebastian Oberhoff Jan 18 '18 at 15:47
  • $\begingroup$ 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. $\endgroup$ – Yuval Filmus Jan 18 '18 at 15:49
  • $\begingroup$ You can derive the vector form of $\mathbf{k}$ using the identity $\tilde{a}_{\mathbf{k}} = \langle \mathbf{k} | \mathbf{\psi} \rangle$. $\endgroup$ – Yuval Filmus Jan 18 '18 at 15:50
  • $\begingroup$ 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. $\endgroup$ – Sebastian Oberhoff Jan 18 '18 at 16:02

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.