Amplitude Estimation Algorithm — Lambda (Q) Operator

Question

I'm working on an implementation of the algorithms described Brassard et al. in the following paper: arXiv:quant-ph/0005055v1.

I managed to make the amplitude amplification cases working but I'm stuck with the amplitude estimation because in the paper there is the definition of a "special" operator in a way I don't understand how to realize it. It is the $\Lambda_M(U^ĵ)$ defined at the bottom of page 15 as

$$|j\rangle|y\rangle\mapsto|j\rangle(|U^j |j\rangle)$$ for $0 \le j \le M$

For a generic integer M and a unitary operator $U$ of size N (!= M), and where the exponent j is its repetition j times. Any idea on how to realize it in practice, as a product of matrices (not necessarily universal), or build element by element?

Answer 1

There are several different answers to your question, but let me give the answer that computer scientists will find most satisfying here.

As it comes to implementing general unitary operators $U$, I would like to refer you to section 4.5 in the book "Quantum Computation and Information" by Nielsen and Chuang. They give a construction which allows one to implement any unitary operator $U$ approximately, using only a finite set of elementary quantum gates. Note that one can use this construction to implement the controlled-$U$ operation as well.

So then the question remains how one implements the mapping $|j\rangle|y\rangle \mapsto |j\rangle U^j|y\rangle$ for $0 \leq j \leq M$. I will use the convention that if $j = j_{n-1}\dots j_0$ is the binary expansion of $j$, then $|j\rangle = |j_{n-1}\rangle \cdots |j_0\rangle$. If $M \leq 7$, then one can use the following circuit:

If we want to allow for bigger $M$, we just have to increase the size of this circuit. Note that in this construction, the number of times one has to apply the controlled $U$ operation equals $2^{\lceil \log_2(M) + 1\rceil} - 1 = \Theta(M)$.