Ideally, we would want the success probability to be as high as possible. While the success probability is not 1, it is lower bounded by a constant. To show this, we will analyze the worst-case scenario: how low can the numerator get, and how high can the denominator get? Let's use some geometric arguments to determine some bounds. Let us first analyze the denominator, which is the difference of $1$ and $e^{2\pi i \delta/{2^t}}$. That is the length of the line segment as shown in the picture below:

--- ***Exercise P.3.3.*** What is the upper-bound for the denominator of Eq. ($3$)?

Solution.

This length is upper-bounded by the arc length between 1 and $e^{2 \pi i \delta/{2^t}}$ which is $2\pi\delta/{2^t}$, therefore, $$ \vert 1 - e^{2 \pi i \delta/{2^t}} \vert \leq 2 \pi \delta/{2^t}. $$

▢

--- Finding the lower bound of the numerator is a bit trickier. We want to know the difference between $1$ and $e^{2\pi i \delta}$. Knowing the arc length will not give us a lower bound as it is longer than the line segment by some factor. Therefore, we will look at the arc length and multiply it by some factor to lower-bound the numerator. The length of the arc between $1$ and $e^{2\pi i \delta}$ is $2\pi \delta $. The largest value that $e^{2\pi i \delta}$ can have will give us the largest factor by which the arc is longer than the line segment.

--- ***Exercise P.3.4.*** What is the lower-bound for the numerator of Eq. ($3$)?

Solution.

This would be possible when $\delta$ has its largest value, i.e. $\delta = \frac{1}{2^{t+1}}$. In this case, the length of the line segment (indicated by the red dotted line) is $2$ and the arc length is $\pi$ giving us a factor of $\frac{\pi}{2}$, meaning that the line segment has to be multiplied by $\frac{\pi}{2}$ to get the arc length. Therefore, a lower bound for the numerator is the arc length multiplied by the inverse of the maximum factor $\frac{2}{\pi}$ which will give us the length of the line segment. Therefore, $$ \vert 1 - e^{2 \pi i \delta} \vert \geq 2 \pi \delta \left( \frac{2}{\pi}\right) = 4\delta. $$

▢

--- Substituting in the bounds for the numerator and the denominator in Eq. ($3$), we have $$ \begin{align} \frac{1}{2^t}\frac{1 - e^{2 \pi i \delta}}{1 - e^{2 \pi i \delta/{2^t}}} & \geq \frac{1}{2^t} \frac{4\delta2^t}{2\pi\delta} \\ &= \frac{2}{\pi} \end{align} $$ The success probability described in Eq. ($2$) is $$ \begin{align} \left \vert\frac{1}{2^t} \sum_{y = 0}^{2^t -1} e^{2\pi i \delta y/{2^t}} \right \vert^2 &= \left \vert \left( \frac{2}{\pi} \right) \right \vert^2 \\ &= \frac{4}{\pi^2}. \end{align} $$ Therefore, the probability of finding the correct $t$-bit approximation is greater than $\frac{4}{\pi^2} = 0.4053$, which is a constant and, therefore, doesn't depend on any other factors such as the number of qubits used for estimation.

Codercise P.3.1 - Sampling for the phase

Codercise P.3.2 - Improving the estimates

Beyond exact fractional binaries

Computing the success probability

A lower bound for success