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?


1 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:

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

  • $\begingroup$ Thanks a lot! Smart solution. I will try it out asap. $\endgroup$
    – Gianni
    Apr 28, 2019 at 11:21

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.