Let be a unitary operator and let be in the spectrum of . We use a mix of Walsh-Hadamard gates and controlled- gates to prepare the state where, as usual for an qubit circuit. Apply the adjoint of , where is the Fourier transform. Then
Thus we measure outcome with probability We are interested in as an -bit approximation to and so we write . Calculate where and using the identity . Thus we measure outcome with probability Observe that is is equal to where is the Fejér Kernel.
Another way of seeing this is to observe that the probability of measuring is where can be recognized as the 'th Cesàro Mean of the formal Fourier Series and from elementary Fourier Analysis this is equal to the Fejér Kernel, .
Now observe that since and , there is a value of such that . But thus both and are less than and for any , Thus the probability of measuring this value of is Thus we can summarize