5
$\begingroup$

Quick question concerning the probability of success after a phase estimation algorithm vs an amplitude estimation algorithm.

Given the calculation on the wikipedia page, the probability of measuring the desired output in a phase estimation algorithm is at least $\frac{4}{\pi^2}$. This is something that I think I have a pretty good handle on.

However, when looking at the amplitude estimation algorithm, we see that the probability of measuring the desired output is at least $\frac{8}{\pi^2}$ (i.e. twice as likely). The only proof that I have found was in Theorem 11 from the original paper. To be honest I am still working through this paper but it is quite terse and a bit difficult to read. Does anyone either have a good intuitive explanation for the difference in success probabilities between phase estimation and amplitude estimation? Or can someone maybe recommend a resource that describes this difference in a nice way? Thanks!

$\endgroup$
2
  • $\begingroup$ QAE relies on the concept of amplitude amplification, this is essentially a series of rotations that increases the probability of the given eigenstate being observed, hence it increases the probability. More recent papers have shown it is possible to implement QAE without using QPE. $\endgroup$ – Sam Palmer Mar 4 at 20:44
  • 1
    $\begingroup$ Thanks for the comment! I understand the idea that amplitude estimation is just the phase estimation using the Grover operator. I am also aware of some of the various works written on QAE without PE. My question though was why do QPE and the canonical QAE (with PE) have different success probabilities (precisely by a factor of 2)? Naïvely I would've have thought they were the same. $\endgroup$ – Rajiv Krishnakumar Mar 5 at 12:13
1
+50
$\begingroup$

Ok let's break this down. Firstly the success probability for QPE and QAE are defined slightly differently.

With QPE there are two error bounds $|\hat{x} - x| < \epsilon$ to consider

$\epsilon < \frac{1}{2^{n+1}}$ with probability $ \geq \frac{4}{\pi}$, or $\epsilon < \frac{1}{2^{n}}$ with probability $ \geq \frac{8}{\pi}$.

We can use the results of the QAE to show that for the given error bounds in QPE is equivalent.

The error expression for QPE can be given in the form of Theorem 11 in the QAE paper (see Kaye, LaFlamme and Mosca). For QPE:

$P(x) = \frac{1}{2^{2n}}\frac{\sin^2(\pi(2^n\omega - x))}{\sin^2(\pi(\omega - x/2^n))}$

Now Theorem 11 states that:

$P(x) = \frac{1}{M^2}\frac{\sin^2(M\pi\Delta)}{\sin^2(M\pi\Delta)}$

Comparing these two equations we can see that for QPE $M=2^n$ and $\Delta = \omega - x/2^n$ . Finally Theorem 11 states that

$P(\Delta < 1/M) \geq \frac{8}{\pi^2}$.

So therefore with $M=2^n$ the two results are actually equivalent for the same degree of accuracy.

However, the difference occurs that in QAE $M$ is a parameter (number of iterations) set by the algorithm whereas in QPE it is fixed as $2^n$. So the QAE error result, Theorem 12, states it more generally with respect to this parameter $M$. For Theorem 12 If you take the limiting case with $k=1$ $M=2^n$ you can see that the error results are equivalent with $\leq 2\pi\frac{1}{2^n} + O(1/M^2)$, the factor of $2\pi$ comes from the definition of $|\hat{x} - x |$ which uses the arclength. So in QAE if we take $M > 2^{n + 1}$ we can achieve higher success probability with QAE than QPE.

$\endgroup$
2
  • 1
    $\begingroup$ Awesome, thank you! Comparing the variables made things very clear! Just to make sure I understand, I wanted to try a simple example in phase estimation. Let's say I have $U|\psi\rangle = e^{2\pi i \frac{9}{16}}|\psi\rangle$ (so the angle is $0.1001$ in binary). Now I use $n=2$ so $2^n=4$ (i.e. I am using two ancilla qubits with $U$ and $U^2$). So now I can say that I will get $\frac{9}{16} \pm \frac{1}{4}$ (i.e. either $\frac{1}{2}$ or $\frac{3}{4}$) with prob $\geq \frac{8}{\pi^2}$, but I will get $\frac{9}{16} \pm \frac{1}{8}$ (i.e. only $\frac{1}{2}$) with prob $\geq \frac{4}{\pi^2}$? $\endgroup$ – Rajiv Krishnakumar Mar 7 at 13:11
  • $\begingroup$ The main answer above has a small typo: the first set of equations should say "with probability $\geq \frac{4}{\pi^2}$" and "with probability $\geq \frac{8}{\pi^2}$". However StackExchange won't let me propose edits that are fewer than 6 characters, but I don't want to change anything else in the answer just for the sake of change because it's fine otherwise... $\endgroup$ – Rajiv Krishnakumar 2 days ago

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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