Quantum Computing Stack Exchange is a question and answer site for engineers, scientists, programmers, and computing professionals interested in quantum computing. It only takes a minute to sign up.
Sign up to join this community
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?
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.
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.
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.
