Given a sequence of \(N\) complex numbers \(x_{n}\), the Fourier-transformed sequence of \(N\) complex numbers \(y_{n}\) is given by
\begin{equation*}
y_{n} = \frac{1}{\sqrt{N}} \sum_{m = 0}^{N-1} x_{m} \exp{\left(- \frac{2 \pi m n i}{N} \right)}
\end{equation*}
This expression can be re-written in terms of \(f_{N}\):
\begin{equation*}
f_{N} = \exp{\left(- \frac{2 \pi i}{N} \right)}
\end{equation*}
The first few values for \(f_{N}\) are
\begin{align*}
f_{1} &= 1, & f_{2} &= -1, & f_{3} &= -\frac{1}{2} - \frac{\sqrt{3}}{2}i, & f_{4} &= -i, & f_{5} &= \frac{\sqrt{5} - 1}{4} - \frac{\sqrt{5 + \sqrt{5}}}{2\sqrt{2}}i, & f_{6} &= \frac{1}{2} - \frac{\sqrt{3}}{2}i
\end{align*}
For quantum state vectors, you can introduce a transform for basis vectors. Given an \(N\)-dimensional quantum state space with ortho-normal basis vectors \(| x_{n} \rangle\), the quantum Fourier transform of that basis is
\begin{equation*}
|y_{n} \rangle = \frac{1}{\sqrt{N}} \sum_{m = 0}^{N-1} (f_{N})^{mn} |x_{m} \rangle
\end{equation*}
This can be stated in terms of a unitary matrix
\begin{equation*}
F_{N} = \frac{1}{\sqrt{N}} \begin{pmatrix}
1 & 1 & 1 & 1 & \cdots & 1 \\
1 & f_{N} & (f_{N})^{2} & (f_{N})^{3} & \cdots & (f_{N})^{N-1} \\
1 & (f_{N})^{2} & (f_{N})^{4} & (f_{N})^{6} & \cdots & (f_{N})^{2(N-1)} \\
1 & (f_{N})^{3} & (f_{N})^{6} & (f_{N})^{9} & \cdots & (f_{N})^{3(N-1)} \\
\vdots & \vdots & \vdots & \vdots & \ddots & \vdots \\
1 & (f_{N})^{N-1} & (f_{N})^{2(N-1)} & (f_{N})^{3(N-1)} & \cdots & (f_{N})^{(N-1)(N-1)}
\end{pmatrix}
\end{equation*}
Let us look at the first few cases.
The \(N = 1\) case is pretty boring. Only one state, so the transform is trivial:
\begin{equation*}
| y_{0} \rangle = | x_{0} \rangle
\end{equation*}
The \(N = 2\) case is slightly more interesting. The relevant coefficients are
\begin{align*}
f_{2} &= -1, & (f_{2})^{2} &= 1
\end{align*}
The \(F_{2}\) matrix is given by
\begin{equation*}
F_{2} = \frac{1}{\sqrt{2}} \begin{pmatrix}
1 & 1 \\
1 & -1
\end{pmatrix}
\end{equation*}
You can recognize this as the Hadamard transform. For the Fourier basis vectors, you have
\begin{align*}
|y_{0} \rangle &= \frac{1}{\sqrt{2}} \left( |x_{0} \rangle + |x_{1} \rangle \right), & |y_{1} \rangle &= \frac{1}{\sqrt{2}} \left( |x_{0} \rangle - |x_{1} \rangle \right)
\end{align*}
Note that this value of \(N\) is a power of 2 and is also prime.
The \(N = 3\) case is next. The relevant coefficients are
\begin{align*}
f_{3} &= -\frac{1}{2} - \frac{\sqrt{3}}{2}i, & (f_{3})^{2} &= -\frac{1}{2} + \frac{\sqrt{3}}{2}i = (f_{3})^{*}, & (f_{3})^{4} &= -\frac{1}{2} - \frac{\sqrt{3}}{2}i = f_{3}
\end{align*}
The \(F_{3}\) matrix is given by
\begin{align*}
F_{3} &= \frac{1}{\sqrt{3}} \begin{pmatrix}
1 & 1 & 1 \\
1 & c & c^{2} \\
1 & c^{2} & c
\end{pmatrix}, & c &= f_{3}
\end{align*}
Then, the Fourier basis is
\begin{align*}
|y_{0} \rangle &= \frac{1}{\sqrt{3}} \left( |x_{0} \rangle + |x_{1} \rangle + |x_{2} \rangle \right), & |y_{1} \rangle &= \frac{1}{\sqrt{3}} \left( |x_{0} \rangle + c|x_{1} \rangle + c^{2}|x_{2} \rangle \right), & |y_{2} \rangle &= \frac{1}{\sqrt{3}} \left( |x_{0} \rangle + c^{2}|x_{1} \rangle + c|x_{2} \rangle \right)
\end{align*}
Note that this value of \(N\) is not a power of 2 but it is also prime.
The case of \(N = 4\) follows. The relevant coefficients are
\begin{align*}
f_{4} &= -i, & (f_{4})^{2} &= -1, & (f_{4})^{3} &= i \\
(f_{4})^{2} &= -1, & (f_{4})^{4} &= 1, & (f_{4})^{6} &= -1 \\
(f_{4})^{3} &= i, & (f_{4})^{6} &= -1, & (f_{4})^{9} &= -i
\end{align*}
The \(F_{4}\) matrix is given by
\begin{equation*}
F_{4} = \frac{1}{\sqrt{4}} \begin{pmatrix}
1 & 1 & 1 & 1 \\
1 & -i & -1 & i \\
1 & -1 & 1 & -1 \\
1 & i & -1 & -i
\end{pmatrix}
\end{equation*}
The Fourier basis is
\begin{align*}
|y_{0} \rangle &= \frac{1}{\sqrt{4}} \left( |x_{0} \rangle + |x_{1} \rangle + |x_{2} \rangle + |x_{3} \rangle \right), & |y_{1} \rangle &= \frac{1}{\sqrt{4}} \left( |x_{0} \rangle -i |x_{1} \rangle - |x_{2} \rangle +i |x_{3} \rangle \right) \\
|y_{2} \rangle &= \frac{1}{\sqrt{4}} \left( |x_{0} \rangle - |x_{1} \rangle + |x_{2} \rangle - |x_{3} \rangle \right), & |y_{3} \rangle &= \frac{1}{\sqrt{4}} \left( |x_{0} \rangle +i |x_{1} \rangle - |x_{2} \rangle -i |x_{3} \rangle \right)
\end{align*}
Note that this value of \(N\) is a power of 2 and thus not prime. Thus, you can write the basis states in binary
\begin{align*}
|x_{0}\rangle &= |00\rangle, & |x_{1}\rangle &= |01\rangle, & |x_{2}\rangle &= |10\rangle, & |x_{3}\rangle &= |11\rangle
\end{align*}
Thinking of the four basis states as tensor products gives
\begin{align*}
|y_{00} \rangle &= \frac{1}{\sqrt{4}} \left( |00\rangle + |01 \rangle + |10 \rangle + |11\rangle \right) = \frac{1}{\sqrt{2}}\left(|0\rangle + |1\rangle \right) \otimes \frac{1}{\sqrt{2}}\left(|0\rangle + |1\rangle \right) \\
|y_{01} \rangle &= \frac{1}{\sqrt{4}} \left( |00\rangle -i |01 \rangle - |10 \rangle +i |11\rangle \right) = \frac{1}{\sqrt{2}}\left(|0\rangle - |1\rangle \right) \otimes \frac{1}{\sqrt{2}}\left(|0\rangle -i |1\rangle \right) \\
|y_{10} \rangle &= \frac{1}{\sqrt{4}} \left( |00\rangle - |01 \rangle + |10 \rangle - |11\rangle \right) = \frac{1}{\sqrt{2}}\left(|0\rangle + |1\rangle \right) \otimes \frac{1}{\sqrt{2}}\left(|0\rangle - |1\rangle \right) \\
|y_{11} \rangle &= \frac{1}{\sqrt{4}} \left( |00\rangle +i |01 \rangle - |10 \rangle -i |11\rangle \right) = \frac{1}{\sqrt{2}}\left(|0\rangle - |1\rangle \right) \otimes \frac{1}{\sqrt{2}}\left(|0\rangle +i |1\rangle \right)
\end{align*}
Thus, the Fourier transform takes you to another basis where the basis vectors are again tensor products and thus separable into two individual qubits. Note that \(F_{4}\) is distinct from the tensor product of two \(F_{2}\) matrices:
\begin{equation*}
F_{2} \otimes F_{2} = \frac{1}{\sqrt{4}} \begin{pmatrix}
1 & 1 & 1 & 1 \\
1 & -1 & 1 & -1 \\
1 & 1 & -1 & -1 \\
1 & -1 & -1 & 1
\end{pmatrix}
\end{equation*}
The \(F_{4}\) is the Fourier transform over \(\mathbb{Z}_{4}\) whereas the tensor product of two \(F_{2}\) matrices is the Fourier transform over \(\mathbb{Z}_{2} \times \mathbb{Z}_{2}\). These two are the only finite groups of order 4.
Next you would have \(N = 5\). This value of \(N\) is not a power of 2, but it is prime. Thus this case does not allow an interpretation in terms of basis states as tensor products.
Finally, consider the \(N = 6\) case. This value of \(N\) is not a power of 2 and it is also not prime. The \(F_{6}\) matrix is given by
\begin{align*}
F_{6} &= \frac{1}{\sqrt{6}} \begin{pmatrix}
1 & 1 & 1 & 1 & 1 & 1 \\
1 & g & g^{2} & -1 & -g & -g^{2} \\
1 & g^{2} & -g & 1 & g^{2} & -g \\
1 & -1 & 1 & -1 & 1 & -1 \\
1 & -g & g^{2} & 1 & -g & g^{2} \\
1 & -g^{2} & -g & -1 & g^{2} & g
\end{pmatrix}, & g &= f_{6}
\end{align*}
Comparing \(f_{6}\) to \(f_{3}\), you have
\begin{align*}
g^{2} &= c, & c^2 &= -g
\end{align*}
In terms of \(f_{3}\), you have
\begin{equation*}
F_{6} = \frac{1}{\sqrt{6}} \begin{pmatrix}
1 & 1 & 1 & 1 & 1 & 1 \\
1 & -c^{2} & c & -1 & c^{2} & -c \\
1 & c & c^{2} & 1 & c & c^{2} \\
1 & -1 & 1 & -1 & 1 & -1 \\
1 & c^{2} & c & 1 & c^{2} & c \\
1 & -c & c^{2} & -1 & c & -c^{2}
\end{pmatrix}
\end{equation*}
You can interpret the six basis vectors as tensor products of a qubit and a qutrit:
\begin{align*}
|x_{0}\rangle &= |0\rangle |0\rangle, & |x_{1}\rangle &= |1\rangle |1\rangle, & |x_{2}\rangle &= |0\rangle |2\rangle, & |x_{3}\rangle &= |1\rangle |0\rangle, & |x_{4}\rangle &= |0\rangle |1\rangle, & |x_{5}\rangle &= |1\rangle |2\rangle
\end{align*}
Then it follows that
\begin{equation*}
F_{6} = F_{2} \otimes F_{3}
\end{equation*}
This is not that surprising, considering that
\begin{equation*}
\mathbb{Z}_{6} = \mathbb{Z}_{2} \times \mathbb{Z}_{3}
\end{equation*}
That is, \(\mathbb{Z}_{6}\) is isomorphic to \(\mathbb{Z}_{2} \times \mathbb{Z}_{3}\).
I know I promised to end with \(N = 6\), but let me say that a similar situation happens with \(N = 10\), \(N = 14\), \(N = 15\), and beyond:
\begin{align*}
\mathbb{Z}_{10} &= \mathbb{Z}_{2} \times \mathbb{Z}_{5}, & \mathbb{Z}_{14} &= \mathbb{Z}_{2} \times \mathbb{Z}_{7}, & \mathbb{Z}_{15} &= \mathbb{Z}_{3} \times \mathbb{Z}_{5}
\end{align*}
and thus
\begin{align*}
F_{10} &= F_{2} \otimes F_{5}, & F_{14} &= F_{2} \otimes F_{7}, & F_{15} &= F_{3} \otimes F_{5}
\end{align*}
Also, a quick comment about \(N = 8\). There are three abelian finite groups of order eight:
\begin{align*}
\mathbb{Z}_{8} && \mathbb{Z}_{2} \times \mathbb{Z}_{4} && \mathbb{Z}_{2} \times \mathbb{Z}_{2} \times \mathbb{Z}_{2}
\end{align*}
Thus you expect three Fourier-like matrices acting on eight-dimensional spaces:
\begin{align*}
F_{8} && F_{2} \otimes F_{4} && F_{2} \otimes F_{2} \otimes F_{2}
\end{align*}
From this point of view, you can distinguish an octit, a tetrit-and-bit sequence, and a three-bit sequence.
Okay, for real, this is the last remark. There is one non-abelian group of order six (\(D_{6}\)), and two non-abelian groups of order eight (\(D_{8}\) and \(Q_{8}\)).
