# Intuition behind the use of inverse FFT in Quantum Circuit for Hamming weight

I have found this question from MIT problemset.

I could only design the circuit for 3 qubits. But they have a general solution that shows this circuit.

I am trying to understand this circuit (from the application of $$R_k$$ and then the $$FT^\dagger$$). Can anybody explain the idea so that I can design these kinds of circuits on my own next time?

• Completely unrelated question, but how did you find this problem set ? Is there any well known repository ? – BrockenDuck Feb 27 at 19:10
• @BrockenDuck.: I am extremely sorry for a late reply. I have just found it online when googled some thing about Quantum Phase estimation. I clicked on it and suddenly reached this page. And that is how I got it. Once again sorry for late reply. – user27286 Mar 1 at 4:49

A generic type of problem for which a fast quantum algorithm is known is the task of computing an eigenvalue of a unitary. Therefore, when looking for an algorithm to compute a quantity $$x$$ it is reasonable to first try to define a unitary $$U(x)$$ with an eigenvalue $$e^{i\theta(x)}$$ dependent on $$x$$. If we can efficiently implement controlled powers of $$U(x)$$ as quantum circuits, then we may be able to use Quantum Phase Estimation to find $$\theta(x)$$. We then recover $$x$$ from $$\theta(x)$$, often using classical computation.

Let us apply this strategy to the problem of computing the Hamming weight $$w(z)$$ of a binary string $$z=z_1z_1\dots z_n$$. We notice that each bit $$z_k$$ contributes equally to $$w(z)$$ irrespective of its position and independently of other bits. This suggests that the unitary we seek should be a simple application of the same single-qubit gate to each qubit. Indeed, if we define $$W = R_n^{\otimes n}$$ where $$R_n = \mathrm{diag}\left(1, e^{2\pi i/2^n}\right)$$, then we see that

$$W|z\rangle = W|z_1z_2\dots z_n\rangle = \prod_{k=1}^n e^{2\pi i \frac{z_k}{2^n}} |z\rangle = e^{2\pi i \frac{w(z)}{2^n}}|z\rangle.$$

Thus, we have found unitary $$W$$ whose eigenvectors are the computational basis states and whose eigenvalue associated with $$|z\rangle$$ is $$e^{2\pi i w(z)/2^n}$$. Moreover, the controlled powers of $$W$$ are simple to implement since $$W^{2^k} = R_{n-k}^{\otimes n}$$. Therefore, we can use QPE to compute $$w(z)$$. Indeed, inserting $$W$$ into the machinery of QPE yields the circuit presented in the question.

• Thanks for answering .. +1. I have also tried to understand the solution, I guess I have understood same thing like you said. Maybe you can check it once if I understood it correctly. Thanks – user27286 Feb 27 at 3:24
• Man, you are right. It was simply the phase estimation. You really provided a nice approach and cleared things up for me. I wish I could find this correlation.. Thanks again. – user27286 Feb 27 at 3:48
• Is it better to delete my answer? It seems silly in front of this ... – user27286 Feb 27 at 3:50
• Your answer is not wrong. It's missing some details that we need algebra to show clearly, but it does describe the key of what's happening. – Adam Zalcman Feb 27 at 3:58

I am glad finally I demystified the mystery and now I would like to share my journey. I have applied it to 3 qubits and then tried to check if my understanding is correct.

The realization is that it converts it from computational basis to Fourier basis. To explain simply,

So the rule is, to convert from computation basis we would just take the binary representation of the number that is given as input to the input register (in binary form, that means 8 would become 100 and 5 would be given as input as 101 and apply it to the each of the three arrows lying in the disk. To be more specific, $$|101\rangle$$). Now to get the Fourier basis representation we would move the arrow starting from the disk in the middle of the sphere, just like we move around a unit circle. So if we have 3 qubit in input then we will move around like this. The least significant position’s sphere would have an arrow which moves in $$\frac{2\pi}{2^{3}}$$ and the next one in $$2 \times \frac{2\pi}{2^{3}} = \frac{\pi}{2}$$ and then the most significant one in $$\pi$$.

Given this rule of moving things out we can represent anything in computational basis to Fourier basis (I say it, from up-down movement to disk based movement). Well this is what I understood to be the Fourier transform. So now if somebody gives me these 3 spheres, in Fourier basis (disk based representation) I can apply inverse FFT to get things in computational basis. :)

Well now in this MIT problem, we were asked to find the number of 1’s. If we had to use non quantum circuit we would have to think of setting this bit 0 or 1 based on whether the previous bit is set or not. I was thinking along the same line and found the “not so fun” quantum circuit for 3 qubits.(Not sure maybe it internally does the same thing). But the process I used is same as we use in normal circuit design applying digital logic.

Here things are now in much better done with the Fourier basis in our hand. We are saying, no matter what, whenever you find a 1, move all the three arrows in these 3 spheres once. (because you have encountered just a single 1).

So suppose we have 5 as input. Then we will say the arrows to move like this. But this is exactly the setup we will get after we apply QFT to $$|2\rangle$$ as per our rule. So that means once we do all this movement, which we have done via the rotation circuit component, we will have to apply opposite of QFT which is the inverse FFT. And that’s how we get to the answer.

• This captures the key idea: that we can realize the counting necessary to compute the Hamming weight in the exponents by changing to the Fourier basis. This is what $W$ in my answer does. I think if you were to make your reasoning more rigorous by carrying out all the necessary algebra, you'd end up with a nice explanation of how QPE works. – Adam Zalcman Feb 27 at 3:55
• @AdamZalcman.: Thinking a bit I realized with 3 bits we are trying to realize $2^n \phi$ which is nothing but $w(z)$ over here. And I think all the red ones if put together will give us application $W^4$. What is basically does is “it asks the red arrow to move twice(each time with angle $\pi$) which is exactly the thing done by $W^4$. Then again in the second case we are doing same with $W^2$. Rotating the green arrow twice exactly. This is what you meant? I would be glad if you point me in right direction. – user27286 Feb 27 at 10:59
• Yes, exactly. Compare your observation to the formula for $W^{2^k}$ in my answer. We get $W^4 = W^{2^2} = R_{3-2}^{\otimes 3} = R_{1}^{\otimes 3}$ (corresponding to the red gates) and $W^2 = W^{2^1} = R_{3-1}^{\otimes 3} = R_{2}^{\otimes 3}$ (corresponding to the green gates). – Adam Zalcman Feb 27 at 23:48
• I will modify it once I get time. @AdamZalcman – user27286 Feb 28 at 11:37

They are using the Draper phase adder to count how many of the bits are set. This adder uses the well known fact in classical signal processing that phasing each state t by an amount proportional to t in frequency space is equivalent to shifting in sample space.

This is actually a sub-optimal strategy for this problem, because it uses $$O(n \lg n)$$ gates (there are $$n$$ controlled increments of a $$\lg n$$ sized register). You can get down to $$O(n)$$ by iteratively applying 3-to-2 full adders until the $$n$$ same-weight initial bits are represented by $$\lg n$$ doubling-weight bits (page 4 here). This also has the advantage of avoiding rotations by small angles, which require decomposing into dozens of rotations in the context of a fault tolerant computation.

• +1 for showing this but to be honest I won't be able to understand this in a short time. Maybe I will check it someday future and ask you few questions regarding this. : ) – user27286 Feb 27 at 16:32