= Cost of exact phase estimation on a dyadic spectrum
If the <eigenvalues> of $A$ are $\ell/2^n$ with $0\leq\ell<2^n$, <exact quantum phase estimation> on $U=e^{2\pi iA}$ uses $n$ controlled powers $U^{2^j}$. Their <Hamiltonian simulation> times reach $2\pi2^{n-1}$. Counting each supplied controlled power as one oracle query is valid in that oracle model, but does not prove a <polynomial time> implementation from generic sparse-matrix access. In the ordinary <HHL algorithm>, one instead chooses finite precision appropriate to the output error and the <condition number>, or exploits additional structure giving efficient access to the needed powers.
Back to article page
