I am interested in Shor's algorithm, and I am reading several papers that related to the quantum Fourier transform (QFT).
I know the there is a difference between the output of QFT and DFT (DFT). But I do not know how to derive QFT from DFT. I do not know how to link from QFT and DFT, and maybe I have not comprehend all the differences between QFT and DFT.
Mathematically, QFT and DFT are exactly the same thing. You can verify this by comparing the first equation on each of the Wikipedia pages. On Wikipedia these two differ by a minus sign in the exponent and by a normalization factor, but these are just conventions.
The difference between Quantum Fourier Transform and classical Fast Fourier transform is in the speed and in the way the data is represented physically. Classically, a dimension $n$ vector is represented using $n$ floating point numbers. On a quantum computer, the QFT operates on the wave function of $\log_2 n$ qubits, an exponential space savings. The classical FFT runs in time $O(n\log n)$ and the QFT runs in time $O((\log n)^2)$ where again $n$ is the dimension of the vector. Note that the classical FFT must take time $O(n)$ to even read the input!
It should also be noted that the classical and quantum versions differ in another important respect, as a consequence of the way the data is stored. After the classical FFT algorithm completes, you have the entire output vector to do whatever you want with (e.g. print out the $100^{\textrm{th}}$ component of the vector or whatever). The QFT leaves the answer in a quantum state, which you can think of as a sort of generalized probability distribution, and you can do certain measurements to get certain types of information out, but you have to be crafty. Shor's algorithm is of course the canonical place to look for an example here, although Simon's algorithm illustrates many of the same concepts without having to deal with the computational tedium of Shor's algorithm (Simon uses the Hadamard rather than Fourier transform but conceptually there is not much difference).
By the way, the circuit that implements the QFT is a reflection of Cooley and Tukey's divide and conquer algorithm for FFT. When Cooley-Tukey splits the input in half, the QFT inspects one qubit. Ponder this and you will understand something about the power of quantum computers.
The above answer appears to be mostly correct however, I'm not sure about the first paragraph. The definitely differ by a normalization factor, but the exponent appears the same for both. One should be able to say that algorithmically, if we input a sequence of qubits in vector form then, we should get QFT = $\sqrt{N}$DFT, where $N$ is the number of qubits. Please correct me if I'm wrong.
The QFT can be defined directly as the Normalized DFT (1/sqrt(N) convention) over the quantum state vector.
For example, consider a circuit with 3 qubits. Then, its quantum state vector is composed of 2^3 = 8 complex numbers $s_i$, each one representing the probability of each possible measurement outcome:
s_0|000> + s_1|001> + s_2|010> + s_3|011> +
s_4|100> + s_5|101> + s_6|110> + s_7|111>
so example if we had a state:
1/sqrt(2) |000> + 0.0 |001> + 0.0 |010> + 0.0 |011> +
0.0 |100> + 0.0 |101> + 0.0 |110> + i/sqrt(2) |111>
we would have a 50/50 chance of measuring either 000 or 111.
Next remember that the DFT is a mathematical operation that takes a sequence of N complex numbers as input, and outputs another sequence of N complex numbers.
So, if we apply the DFT to one quantum state, defined by its 8 complex numbers, it produces another quantum state, also defined by its 8 complex numbers.
Using the Normalized DFT rather than the 1/N is essential because that one maintains power and therefore the total probability to 1.0, which leaves us with a well defined quantum circuit.
We should also verify this by playing around a bit with Qiskit. E.g. here I setup a quantum state with a sinus, which we expect to have a relatively simple DFT representation with only 2 non-zero points:
import math
from qiskit import QuantumCircuit, transpile
from qiskit.circuit.library import QFT
from qiskit_aer import Aer, AerSimulator
n = 3
N = 2**n
def test(init, print_qc=False):
qc = QuantumCircuit(n)
qc.initialize(init)
qft = QFT(num_qubits=n).to_gate()
qc.append(qft, qargs=range(3))
print(f'init: {init}')
if print_qc:
print('qc')
print(qc)
qc = transpile(qc, AerSimulator())
if print_qc:
print('transpiled qc')
print(qc)
print(Aer.get_backend('statevector_simulator').run(qc, shots=1).result().get_statevector())
print()
test([math.sin(i * 2 * math.pi / N)/2 for i in range(N)])
and it produces:
init: [0.0, 0.35355339059327373, 0.5, 0.3535533905932738, 6.123233995736766e-17, -0.35355339059327373, -0.5, -0.35355339059327384]
Statevector([ 7.71600526e-17+5.22650714e-17j,
1.86749130e-16+7.07106781e-01j,
-6.10667421e-18+6.10667421e-18j,
1.13711443e-16-1.11022302e-16j,
2.16489014e-17-8.96726857e-18j,
-5.68557215e-17-1.11022302e-16j,
-6.10667421e-18-4.94044770e-17j,
-3.30200457e-16-7.07106781e-01j],
dims=(2, 2, 2))
Most of those numbers are tiny and simply numerical noise, so the output is approximately:
[0, 1j/sqrt(2), 0, 0, 0, 0, 0, 1j/sqrt(2)]
which you should easily be able to verify is the DFT of our input signal [math.sin(i * 2 * math.pi / N)/2 for i in range(N)].
Tested on:
qiskit==0.45.1
qiskit-aer==0.12.2
