# How to implement exponentiation of a gate without breaking complexity?

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.

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.

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