2
$\begingroup$

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.

| cite | improve this question | |
$\endgroup$
  • $\begingroup$ This isn't particularly unique to the quantum version ─ the (classical) Fast Fourier Transform also has this restriction, and it is very often so much faster than the standard DFT that it's cheaper to pad your vector with zeros and use the FFT on a longer input than to run the DFT directly. There are also variations of the FFT that can whittle that down and keep the $O(n\log(n))$ runtime, which could potentially be replicated on the quantum side if you ran things on qudits (not that it makes much sense to explore those, though). $\endgroup$ – Emilio Pisanty Mar 7 '18 at 20:45
  • $\begingroup$ @EmilioPisanty Padding does not result in a FT over Z_N. $\endgroup$ – Norbert Schuch Mar 8 '18 at 7:05
  • $\begingroup$ @EmilioPisanty not that it makes much sense to explore those, though -- not in the context of quantum computing with qubits maybe, but there are interesting applications of (fast) QFT over qudits, see for example arxiv.org/abs/1508.00782 $\endgroup$ – glS Mar 8 '18 at 19:21
  • $\begingroup$ @Norbert indeed it doesn't; in some applications the difference matters and in others it doesn't. If you care about the difference and you really want a DFT over $\mathbb Z_p$ for $p$ a large prime, then you're stuck with a slow algorithm already on the classical side. $\endgroup$ – Emilio Pisanty Apr 20 '18 at 9:14
1
$\begingroup$

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$.

| cite | improve this answer | |
$\endgroup$
  • $\begingroup$ I still don't quite get it. I think about qubits in similar way like bits. For ex. we can have decimal number j = 10 = (1010)_bin = 1*2^3 + 0*2^2 + 1*2^1 + 0*2^0 (where _bin is binary notation). So, by analogy, wouldn't the basis for a quantum computer with n quibts be like |2^0>, |2^1>, |2^2>, |2^3>? $\endgroup$ – brzepkowski Mar 7 '18 at 18:23
  • $\begingroup$ I think you're getting it. $N$ vs $n$ is just the number of total states in a basis vs the number of qubits. This is the same classically when talking about the number of bits vs the number of possible options. I've expanded my answer with an example to (hopefully) clarify this. Let me know if you're still confused and I'll expand on this more. $\endgroup$ – Punk_Physicist Mar 7 '18 at 19:47
  • $\begingroup$ So, when we say, that we have basis in form |0>, |1>, ..., |2^n - 1> it is like list of all possible quantum states, that can be represented on $n$ qubits? So it is not like the orthonormal basis (which in our case is made of qubits), where we express vector in form $\alpha |j_1> + \beta |j_2> + ... + \omega |j_n>$? Maybe my problem is about the misuse of word "basis" in these two contexts? $\endgroup$ – brzepkowski Mar 7 '18 at 20:29
  • $\begingroup$ It is an interesting question, though, whether one can do a QFT over Z_N for any N. $\endgroup$ – Norbert Schuch Mar 7 '18 at 20:43
  • $\begingroup$ @Ozaru There are an infinite number of possible states, but a (complete) basis is set a linearly independent states that can be used to represent any state. So for a single qubit you need two states to be the basis, e.g. $|0\rangle$ and $|1\rangle$ are a basis that can represent any (pure) state $|\psi\rangle = \alpha|0\rangle + \beta|1\rangle$. For $n$ qubits you need $2^n$ independent states to form a basis. $\endgroup$ – Punk_Physicist Mar 7 '18 at 21:00

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.