Quantum phase estimation is usually explained via repeated applications of controlled $U^{2^k}$ gates in order to realize the map

$$ |j\rangle|\psi\rangle \mapsto |j\rangle U^j|\psi\rangle $$

If I assume that $U$ can be implemented as a quantum circuit, is there a general method to compute $U^{2^k}$ efficiently, or do I need to assume that $U^{2^k}$ can be implemented efficiently for all $k=0,\ldots,n$?


1 Answer 1


The phase estimation algorithm assumes that you have an efficient way to calculate $U^{2^k}$. Generically, this may place a limit on $k$ and $2^k$, the precision to which you wish to calculate the phase.

This point is indeed often elided over. If you wish very (very) accurate calculation of the phase $\phi$ of your eigenstate $|\psi\rangle$ then you should be prepared to repeatedly run controlled versions of $U$ many times.

Nonetheless in the prototypical phase estimation algorithm used for factoring (in Shor's algorithm), we have, for very interesting number-theoretical reasons related to repeated squaring, a situation where we can "fast-forward" the calculation of $U^{2^k}$. Aharanov and Gilyen briefly touch on this point in a lecture at the Israeli Institute for Advanced Studies.


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.