15.1 Quantum Fourier Transform
In the classical setting, the discrete Fourier transform maps a vector
to a vector
the components of which read
|
Similarly, the QFT is the linear map
|
and the operator
represents the Fourier transform matrix which is unitary as qFqF† = I. In an n-qubit system with basis (
,…,
), for a given state 
, we use the binary representation
|
with (j1,…,jn) ∈{0,1}n so that
Likewise, the notation
represents the binary fraction ∑ i=1n2−iji. Elementary algebra (see [238, Section 5.1] for details) then yields
|
