On Wikipedia, one can read the following about Quantum Phase Estimation:
the algorithm estimates the value of $\theta$ with high probability within additive error $\varepsilon$, using $O(1/\varepsilon )$ controlled-$U$ operations.
Why do we need so much qubits? What we want is a $t$-qubits string such that it is equal to the $t$ first bits in the binary writing of $\theta$. We also want this binary writing to be at most at $\varepsilon$ from the true value. Hence, we have that:
In the worst case, both terms are equal and all $\theta_n$ are $1$. Hence, we have:
Hence, we would have $O(\log(1/\varepsilon))$ controlled operations, since we have as much operations as qubits in the first register. Is it Wiki that is wrong, or my calculations?
Side question: is it some sort of convention to write $O(1/\varepsilon)$ rather than $O\left(\frac1\varepsilon\right)$? I only see the former written, while I find the latter less ambiguous.