# Complexity of controlled-$U^j$ operations in QPE applied to Hamiltonian simulation

One method to obtain the eigenvalues of a Hamiltonian $$H$$ is by applying quantum phase estimation to its time-evolution operator $$U(t) = e^{-iHt}$$. If I want to obtain an eigenvalue to $$k$$ bits in accuracy, I will need to apply the set of unitaries

$$U^{2^j}(t) = U(2^jt), \quad 0 \leq j \leq k-1.$$

By the no-fast-forwarding theorem, implementing $$U(t)$$ takes $$O(t)$$ gates for a general Hamiltonian $$H$$. My question is: does this imply that quantum phase estimation, when applied to Hamiltonian simulation, has complexity that scales exponentially in the desired accuracy? I tried looking for the answer in Nielsen and Chuang and they seem to treat the controlled-$$U^j$$ operations as a black-box, and, to the best of my knowledge, don't discuss their complexity.

If $$k$$ is the number of desired bits, then yes its exponential in $$k$$. However, given $$k$$ correct bits of the eigenvalue, the error is $$1/2^{k+1}$$. This is because if you have a $$k$$-bit binary number: $$0.b_1b_2...b_k$$ with $$b_i \in \{0, 1\}$$, then this has error $$\pm 0.0...01$$ with $$k$$ 0's after the decimal.

If you had started with a desired error $$\epsilon$$ instead, you then only need $$O(\log(1/\epsilon))$$ bits of precision, so you need to repeat the unitary $$O(1/\epsilon)$$ times (if no fast forwarding is possible). Its exponential in $$k$$, but $$k$$ is logarithmic in 1/error, so overall its linear in 1/error.