Bagaimana cara kerja Fourier sampling sebenarnya (dan menyelesaikan masalah paritas)?

Saya menulis sehubungan dengan bagian I dan bagian II dari ceramah video pengambilan sampel Fourier oleh Profesor Umesh Vazirani. Pada bagian I mereka mulai dengan: Dalam Hadamard Transform: |0...0⟩→∑{0,1}n12n/2|x⟩|0...0⟩→∑{0,1}n12n/2|x⟩|0...0\rangle \to