Let N be a positive power of 2, N=2n. Then given any number a between 0 and N-1, it can be written as

a = Sumk ak 2k

with the coefficients ak equals to either 0 or 1 (they are the bits of the binary representation of a). Consider the product

Prodk=0 .. n-1 ( 1 + exp(2 pi i Ak )

where the numbers Ak are less than one, and

Ak = Sumi=0 .. k ai 2i-k-1

ie their binary representation is 0.ak...a0.

Prove that the above product is equal to N if a=0, and is zero otherwise.

Consider the sum Sumb=0..N-1 exp( 2 pi i a b / N ). This result is used in the quantum Fourier transform.

Marco Corvi - 2004