Why do we consider vectors of length $N = 2^n$ for the Quantum Fourier Transform?

Question

Discrete Fourier Transform

Classical Discrete Fourier transform acts on a vector $(x_0, x_1, ..., x_{N-1}) \in C^N$ and maps it to vector $(y_0, y_1, ..., y_{N-1}) \in C^N$ according to the formula $$ y_k = \frac{1}{\sqrt{N}} \sum_{j=0}^{N-1} e^{\frac{2\pi ijk}{N}} x_j, $$ where $k = 0, 1, 2, ..., N-1$.

My understanding of this, is that we are expressing the same vector in new basis (which has the same amount of dimensions as the original one). Moreover, each coefficient standing by the vector from new basis depends on each coefficient from the original basis.

Quantum Fourier Transform

In Quantum Fourier Transform we consider vecotrs of length $N = 2^n$. So each coefficient is calculated as folows

$$ y_k = \frac{1}{2^{n/2}} \sum_{j=0}^{2^n - 1} e^{\frac{2 \pi ijk}{2^n}} x_j$$

Wiki page (https://en.wikipedia.org/wiki/Quantum_Fourier_transform) gives the following example:

Consider the quantum Fourier transform on 3 qubits. It is the following transformation:

$$ QFT:|x\rangle \ \rightarrow \frac{1}{\sqrt{2^3}} \sum_{j=0}^{2^3 - 1} e^{\frac{2 \pi ixk}{2^3}} |k\rangle$$

I can't grasp the correspondence between number of qubits $n$ needed to express quantum state and this $N = 2^n$. Nielsen and Chuang in their book "Quantum Computation and Quantum Information" also write, that "because we take $N = 2^n$ we have the basis $|0\rangle, |1\rangle, ..., |2^n-1\rangle$ which is computational basis for $n$ qubit quantum computer".

Can you explain me, why we change the basis from $|0\rangle, |1\rangle, ..., |N-1\rangle$ to $|0\rangle, |1\rangle, ..., |2^n - 1\rangle$? My intuition tels me, that we now operate on such vectors $(x_0, x_1, ..., x_{2^n - 1}) \in C^{2^n - 1}$, but I know this is wrong.

Answer 1

This is simply the difference between asking what is the dimensionality of your space $N$ (or equivalently the number of basis states), and how many bit (or qubits) $n$ you have. For each (qu)bit you double the number of distinct basis states, so the relation between $N$ and $n$ is $$N = 2^n.$$ Counting from $0$ this is $j\in[0,N-1]=[0,2^n-1]$.

As an example, 3 qubits span a space of dimension $2^3 = 8$ because each qubit in the basis state can be represented by a binary $0$ or $1$. So the basis states are $$|b_1\rangle\otimes|b_2\rangle\otimes|b_3\rangle,$$ where $b_m$ is the $m^\text{th}$ qubit, and can be labeled as $0$ or $1$ in a given basis. In condensed form I might write $|0\rangle\otimes|1\rangle\otimes|0\rangle$ as $|010\rangle$, or I might number the states so this state might be written as $|2\rangle$.