Content deleted Content added
Added disambiguation to the introduction: Quantum Fourier transform is faster because 2^n amplitudes take O(n^2) gates. |
PaulTheBaker (talk | contribs) →Definition: clarify the use of omega: roots of unity; define omega^jk for DFT instead of simply omega, define omega for matrix form |
||
Line 10:
:<math>y_k = \frac{1}{\sqrt{N}} \sum_{j=0}^{N-1} x_j \omega^{jk}</math>
where <math>\omega^{jk} = e^
Similarly, the quantum Fourier transform acts on a quantum state <math>\sum_{i=0}^{N-1} x_i |i\rangle</math> and maps it to a quantum state <math>\sum_{i=0}^{N-1} y_i |i\rangle</math> according to the formula:
:<math>y_k = \frac{1}{\sqrt{N}} \sum_{j=0}^{N-1} x_j \omega^{jk}
with <math>\omega^{jk}</math> defined as above.
This can also be expressed as the map
Line 29 ⟶ 32:
\end{bmatrix}.
</math>
Here <math>\omega = e^{\frac{2 \pi i}{N}}</math> is a primitive ''N''<sup>th</sup> [[root of unity]].
== Properties ==
| |||