1
$\begingroup$

I have read two opposite explanations about QFT and IQFT from 2 books for beginners of Quantum Computing. Which one is correct?

The first book said, if we input an n-qubit non-superposition state into QFT, the QFT will output an n-qubit superposition state with periodical phases. On the other hand, IQFT swaps the input and output of QFT; we can apply IQFT to find the period hidden in an input state because the amplitude of the state, which matches the period(or frequency), will be amplified.

e.g., If we input |010〉into QFT, QFT will output a uniformly distributed superposition whose phases shifted two rotations(periods), the 1st rotation is from |000〉 to |011〉, and the 2nd one is from |100〉to |111〉. And if we input the output into IQFT, it will output |010〉.

enter image description here

The second book told me an opposite fact, that QFT allows us to determine how many rotations the relative phase makes per register, and we can use the IQFT to prepare periodically varying register superpositions easily.

e.g. enter image description here

QFT allows us to determine that the frequency of repetition it contained was 2 (i.e., the relative phase makes two rotations per register)

enter image description here

We can use the invQFT to easily prepare periodically varying register superpositions

$\endgroup$

1 Answer 1

1
$\begingroup$

The classical Fourier transform acts on a vector $(x_{0}, x_{1}, \ldots, x_{N-1}) \in {C} ^{N}$ and maps it to the vector $(y_{0}, y_{1}, \ldots, y_{N-1}) \in {C} ^{N}$.

According to the formula:

$y_{k}={\frac {1}{\sqrt {N}}}\sum _{n=0}^{N-1}x_{n}\omega _{N}^{-kn},\quad k=0,1,2,\ldots ,N-1$

Similarly, the quantum Fourier transform acts on a quantum state $|x\rangle = \sum _{i=0}^{N-1}x_{i}|i\rangle$ and maps it to a quantum state $|y\rangle = \sum _{i=0}^{N-1}y_{i}|i\rangle$

Now, different authors use different conventions for the formula which maps the input state $|x\rangle$ to the output state $|y\rangle$. Some authors use the convention that QFT has the same effect as the inverse DFT, and vice versa. In this case, QFT is defined as

$\text{QFT}:|x\rangle \mapsto {\frac {1}{\sqrt {N}}}\sum _{k=0}^{N-1}\omega _{N}^{xk}|k\rangle$

And inverse quantum Fourier transform is defined as

$\text{QFT}^\dagger:|y\rangle \mapsto {\frac {1}{\sqrt {N}}}\sum _{k=0}^{N-1}\omega _{N}^{-yk}|k\rangle$

Other authors use the convention that QFT has the same effect as the DFT. That is, switch the sign of the phase factor exponent.

The difference between these two books because the authors follow different conventions.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

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