# Why is the number of qubits linear in the inverse of epsilon in 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:

$$\left|\sum_{n=t+1}^{+\infty}\theta_n\,2^{-n}\right|\leqslant\frac{\varepsilon}{2}$$

In the worst case, both terms are equal and all $$\theta_n$$ are $$1$$. Hence, we have:

$$\sum_{n=t+1}^{+\infty}2^{-n}=\frac\varepsilon2\iff2^{-t}=\frac\varepsilon2\implies t=1+\left\lceil\log_2\left(\frac1\varepsilon\right)\right\rceil$$.

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.

The statement that you’ve made about the size of the register that you use for phase estimation (the value of t) is correct. However, you don’t seem to have made any attempt to count the number of gates used in the circuit. To implement the phase estimation you need controlled-U, $$U^2$$, $$U^4$$, $$U^8$$, $$U^{16}\ldots$$ If you have to make these out of just controlled-$$U$$, this means using exponentially many of them (in t),
• Thanks! I did actually, in this post, where you answered, but I thought as any $U^{2^i}$ gate as a single operation in this case. Thank you again! Apr 8 '20 at 11:02