How to implement exponentiation of a gate without breaking complexity?

Question

In the application of QFT for quantum phase estimation (QPE) of a unitary $\mathbf{U}$, one has to perform successive controlled operations using powers of $\mathbf{U}$. In order not to break the complexity, each of the controlled $\mathbf{U}^{2^i}$ gates must have the same complexity when applying them as $\mathbf{U}$.

Hence, if I want to apply a QPE on a gate whose circuit is known, how should I proceed? If I just concatente the circuit of $\mathbf{U}$ to itself $2^i$ times, applying $\mathbf{U}^{2^i}$ is $2^i$ times as long as applying $\mathbf{U}$, which breaks the complexity.

I've seen papers and posts about modular exponentiation, but I'm not sure this would work in my case, since I do not work modulo some whole number.

I understand that fundamentally, what I want to do is to implement a unitary which, given a state $|x\rangle\,|y\rangle$ returns the state $|x\rangle\,\mathbf{U}^x|y\rangle$, but I don't know how should I perform this.

Answer 1

As a general rule, just because you can produce controlled-$U$, it does not mean that you can produce controlled-$U^{2^k}$ with the same complexity. Modular exponentiation is a very special case where it turns out that you can.

It is probably worth noting (iirc) that even if the best way of implementing controlled-$U^{2^k}$ is with $2^k$ controlled-$U$s, phase estimation in this manner still gives a square-root speed-up compared to other methods. It's just that you don't get the exponential speed-up.

Answer 2

Partial answer:

If a operator $U$ is a single qubit rotation around axis $a$ for angle $\theta$ (denote $R_a(\theta)$) you can use additivity of such operator, i.e.

$$ [R_{a}(\theta)]^k = R_{a}(k\theta). $$

The same is true for global phase gate $[Ph(\theta)]^k=Ph(k\theta)$.

Overall, you only change the angle and only one gate is applied.