1
$\begingroup$

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}$

$\endgroup$

1 Answer 1

1
$\begingroup$

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.

$\endgroup$
5
  • $\begingroup$ Thanks for answering! I understand how you got that with probability at least $1-\frac{1}{2^r}$ we will have at least one correct outcome but how does this imply that the majority of outcomes will be correct with probability at least $1-\frac{1}{2^r}$? $\endgroup$ Aug 27, 2022 at 18:28
  • $\begingroup$ @GiorgosGiapitzakis, I clarified my answer to address your question. $\endgroup$
    – MonteNero
    Aug 28, 2022 at 2:21
  • $\begingroup$ I don't quite agree with that reasoning. I see three potential problems with this approach. Firstly, why can we take $r\to \infty$ when this is not specified in the problem? Also, there are two correct answers but we cannot treat them as one. That is, we might get around 40% of the time the closest to the left and 40% the closest to the right. Finally, the argument that we will get the correct answer $0.8 \cdot O(\log_2(r))$ times again makes sense only when $r$ is sufficiently large. $\endgroup$ Aug 28, 2022 at 2:40
  • $\begingroup$ If you take a look at the question I posted in Math SE you will see that it seems like such a result does not hold in general. What I omitted there is the fact I included in this question regarding the probability of getting the $2k$ closest integers. Therefore, I think this should necessarily be used in the solution. $\endgroup$ Aug 28, 2022 at 2:44
  • $\begingroup$ Anyways, if you figure out the correct way, please make sure to post it here. $\endgroup$
    – MonteNero
    Aug 28, 2022 at 4:22

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Not the answer you're looking for? Browse other questions tagged or ask your own question.