# Amplitude Estimation Algorithm — Lambda (Q) Operator

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?

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)$$.