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

Question

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.

Answer 1

Your understanding is almost there.

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.