Kaye Exercise 7.1.3, Quantum Phase Estimation

Question

Prove that $O(\log_2(r))$ phase estimations with $n = m$ and taking the outcome that occurs most often provides an estimate $\tilde \omega$ of the phase $\omega$ which will with probability at least $1 − \frac{1}{2^r}$ have error $|\omega − \tilde \omega| \leq \frac{1}{2^m}$.

Hint: Find an upper bound on the probability of obtaining anything other than one of the two closest estimates, and then guarantee that with high probability the outcome is one of the two closest estimates.

I have asked this question (although a bit modified) here as well but I think this is a more appropriate place. You can see in the Math SE post my attempt but I think I might need to use the following fact as well:

It is easy to verify that with probability at least $1-\frac{1}{2(k-1)}$ the phase estimation algorithm will output one of the $2k$ closest integers. This implies that with probability at least $1-\frac{1}{2(k-1)}$, the output $\tilde \omega$ of the phase estimation algorithm will satisfy $|\omega - \tilde \omega|\leq \frac{k}{2^n}$

Answer 1

I find this exercise really tricky and a bit confusing. I'm not very happy with my attempt, but I'll post it, hoping somebody points us in the right direction.

Suppose we perform $O(\log_2(r))$ phase estimations and obtain a set of estimates $\left \{\tilde{w}_i\right\}_{i=1}^{O(\log_2(r))}$.

The probability of obtaining anything other than one of the two closest estimates can be expressed as $\Pr\left(\forall i, |\tilde{w_i}-w|>\frac{1}{2^n} \right)$. We can bound this as follows: $$\tag{1} \Pr\left(\forall i, |\tilde{w}_i-w|>\frac{1}{2^n}, \right) \leq \left(1-8/\pi^2 \right)^{O(\log_2(r))}.$$

This can be viewed as bounding a binomial probability distribution of the number of successes (zero successes in our case) in a sequence of $O(\log_2(r))$ independent experiments.

Now, the probability that there exists at least one $i_0$ such that $\left|\tilde{w}_{i_0}-w \right| \leq 1/2^n$ is $$\tag{2} \Pr \left(\exists i_0 \ \textrm{s.t.} \ \left|\tilde{w}_{i_0}-w \right| \leq \frac{1}{2^n}\ \right) = 1 - \Pr\left(\forall i, |\tilde{w}_i-w|>\frac{1}{2^n} \right).$$

Given (1), we can bound (2) as follows: $$ 1 - \Pr\left(\forall i, |\tilde{w}_i-w|>\frac{1}{2^n} \right)\geq 1 - \left(1-8/\pi^2 \right)^{O(\log_2(r))}.$$

Therefore, we have: $$\tag{3} \Pr(\exists i_0 \ \textrm{s.t.} \ \left|\tilde{w}_{i_0}-w \right| \leq 1/2^n\ ) \geq 1 - \left(1-8/\pi^2 \right)^{O(\log_2(r))}.$$

Finally, we note that the following is true in the asymptotic sense: $$\tag{4} \left(\frac{1}{2}\right)^r =\left(1-8/\pi^2 \right)^{O(\log_2(r))} \textrm{ as} \ r \rightarrow \infty.$$

Given (4), all is left is to rewrite (3) as follows: $$\tag{5} \Pr(\exists i_0 \ \textrm{s.t.} \ \left|\tilde{w}_{i_0}-w \right| \leq 1/2^n\ ) \geq 1 - \frac{1}{2^r}.$$

Here, we argued that there exists at least one or more estimates that satisfy the condition $|\tilde{w}_{i_0} - w| \leq 1/2^n$ with the probability $1-1/2^r$. The trick is that we already know how many more estimates satisfy the condition. From Theorem 7.1.5 on page 119, we know that with the probability of at least $8/\pi^2 \approx 0.8$, QPE produces an estimate $\tilde{w}$ such that $|\tilde{w}-w| < 1/2^n$. This means that roughly 80% of the estimates in $\{w_i\}_{i=1}^{O(\log_2(r))}$ satisfy the condition.

Therefore, it follows that we can rewrite (5) with a slightly more precise bound on the number of phase estimates that satisfy the condition. Specifically, we can say that instead of at least one estimate, there are, on average, $0.8 \cdot O(\log_2(r))$ estimates that satisfy the condition, and this happens with the probability $1-1/2^r$. Of course $0.8 \cdot O(\log_2(r))$ is the majority.