# How to implement projective measurement from multiple measurements?

In the following paper by Harrow et al.: https://arxiv.org/pdf/1607.03236.pdf, they want to implement a measurement operator that is the average of a set of measurement operators. On page 9, right above theorem 9, they say:

One special case that will be important for us is when we have a sequence of projectors $$\Lambda_i$$, where $$\Lambda_i$$ corresponds to the two-outcome measurement $$M_i = {\Lambda_i, I−\Lambda_i}$$, and we would like to implement the POVM element $$\Lambda := \frac{1}{n} \sum_{j=1}^{n} \Lambda_j$$. Define the projector $$\Pi = \sum_{i=0}^{n-1} \Lambda_{i+1} \otimes (Q |{i} \rangle \langle{i}| Q^{-1})$$ where $$Q$$ is the quantum Fourier transform on $$\mathbb{Z}_n$$. Given quantum circuits which implement each measurement $$M_i$$, it is easy to write down a circuit that implements the measurement $${\Pi, I − \Pi}$$.

I don't see why this is easy. How do we write down this circuit?

Also, I do not see why we need the fourier transform for this implementation. Why can't we just have $$|{0} \rangle \langle{0}|$$ for the second register. I am guessing its necessary for the implementation but I do not see why.

The point of the second register is to initialize it in some state with an equal probability of being found in any basis state $$|i\rangle$$. Then, conditioned on the state of the second register, one chooses which of the measurement procedures $$M_i$$ to perform on the state. Then the Fourier transform sets each of the projectors $$\Lambda_i$$ to have equal weight for the $$|0\rangle$$ state in the second register, and we can project onto that one to proceed. One could also project onto a different register state to avoid requiring $$Q$$ here.
Okay, so we know how to implement $$M_i$$, so we can do the projector $$\Lambda_i$$. Now construct a circuit that says "implement $$\Lambda_i$$ if the register is in state $$|i\rangle$$." That looks like $$\Pi^\prime=\sum_i \Lambda_i\otimes|i\rangle\langle i|.$$ Next, perform a Fourier transform on the second register and project the result into state $$|0\rangle$$. Also do that prior to $$\Pi^\prime$$, but with the inverse Fourier transform. That looks like, using their notation $$\Delta=\mathbb{I}\otimes |0\rangle\langle 0|$$, $$\Delta (\mathbb{I}\otimes Q)\Pi^\prime (\mathbb{I}\otimes Q^{-1})\Delta=\sum_i \Lambda_i\otimes |0\rangle\langle 0|Q|i\rangle\langle i|Q^{-1}|0\rangle\langle 0|.$$ Now, the purpose of the Fourier transform is to realize that $$Q^{-1}=Q^\dagger$$ and $$|\langle 0| Q|i\rangle|=1/\sqrt{n}$$ regardless of $$i$$. Then, we find that implementing first $$\Delta$$, then the inverse Fourier transform on the second register, then $$\Pi^\prime$$, then the Fourier transform on the second register, then $$\Delta$$ again enacts $$\Delta (\mathbb{I}\otimes Q)\Pi^\prime (\mathbb{I}\otimes Q^{-1})\Delta=\frac{1}{n}\sum_i \Lambda_i\otimes |0\rangle\langle 0|=\Lambda\otimes|0\rangle\langle 0|.$$ So if the second register is initialized in state $$|0\rangle$$ prior to all of these operations, the combined circuit will enact $$\Lambda$$ on the first register.
To recap: initialize the second register in state $$|0\rangle$$. Apply inverse Fourier transform $$Q^{-1}$$ on second register. Apply projector $$\Lambda_i$$ on first register conditioned on second register being in state $$|i\rangle$$ (this step requires the assumed knowledge of the circuits $$M_i$$ to implement such projectors, and the ability to choose which circuit to implement). Apply Fourier transform $$Q$$ to second register. Project second register onto state $$|0\rangle$$. You have enacted the desired transformation $$\Lambda$$ on the first register!
The same can be done with a replacement $$\Lambda_i\to\mathbb{I}-\Lambda_i$$ to lead to the overall replacement $$\Lambda\to\mathbb{I}-\Lambda$$.