6
$\begingroup$

Firstly, I'd like to specify my goal: to know why QFT runs exponentially faster than classical FFT. I have read many tutorials about QFT (Quantum Fourier Transform), and this tutorial somehow explains something important between classical and quantum Fourier Transform.

Inside 1, it describes that:

The quantum Fourier transform is based on essentially the same idea with the only difference that the vectors x and y are state vectors (see formula 5.2, 5.3),

formulas 5.2, 5.3, 5.4, and 5.5 from the mentioined pdf file

However, I couldn't catch up the statement regarding "x and y are state vectors"; I get stuck at the formula 5.2 and 5.3. I want to know how to convert the classical input vector x to the right hand side of the formula 5.2. If this confusing problem is solved, it'll be better for me to understand the time complexity issue of QFT.

Improve this question
$\endgroup$
1

2 Answers 2

Reset to default
6
$\begingroup$

Formula 5.2 refers to an encoding we call amplitude encoding. Imagine you have a vector $x$ with components $x_i$, the components are then encoded as amplitudes of a quantum state.

This encoding is very important as a vector that has a dimension $N$, will be encoded in quantum form using about $log(N)$ qubits. This is the main reason why in many quantum algorithms using this encoding we can achieve exponential speedup in the size of the problem.

However, generally in quantum computing, you have to assume that this encoding is done using a device called quantum random access memory for loading in this form a vector. Or you are given a circuit that do the job for you.

Improve this answer
$\endgroup$
2
  • $\begingroup$ Thank you for your answer. I'm not sure if your answer contradicts with Norbert's(the other answer). Or maybe both of you are saying the same thing but I cannot see through it.......... $\endgroup$
    – user3176354
    Commented Nov 20, 2018 at 10:41
  • $\begingroup$ @user3176354 It does not. When I say "a circuit that does the job for you", a circuit is also an algorithm whose output is the state x. Formula 5.2 is typical of an amplitude encoding done by QRAM, which will create this preparation by applying a circuit for this purpose. The purpose of the QRAM will be to prepare classical data to quantum form (however we do not have an efficient implementation of such device so far). $\endgroup$
    – cnada
    Commented Nov 20, 2018 at 11:09
5
$\begingroup$

You don't convert a classical input to the r.h.s. of Eq. (5.2). The r.h.s. of Eq. (5.2) is something you get as the output of a preceding quantum computation as a quantum state, such as in Shor's algorithm. This is the only way to get an exponential speedup -- if you had to start from an exponentially big classical vector, there would be no way to solve this in polynomial time.

Improve this answer
$\endgroup$
2
  • $\begingroup$ Thank you for your answer. But I'm still confused; according to the referenced pdf/website, the author says something between formula 5.3 and 5.4 in a way that makes want to think that we convert a classical input to the r.h.s. of Eq. (5.2). What the author says between formula 5.3 and 5.4 is " Then the action on the components of state vector x is described by 5.1 so that". $\endgroup$
    – user3176354
    Commented Nov 20, 2018 at 10:38
  • $\begingroup$ @user3176354 In the formulation you quote, there is nothing saying that this is converted to classical. $\endgroup$
    – Norbert Schuch
    Commented Nov 20, 2018 at 12:36

Your Answer

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

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