Quantum Amplitude Estimation vs Quantum Phase Estimation

Question

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!

Answer 1

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.

Answer 2

1. Let's say I have $U|ψ⟩=e^{2πi\frac{9}{16}}|ψ⟩$ (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{1}{2}, \frac{1}{2} \pm \frac{1}{8}$ or $\frac{1}{2} \pm \frac{1}{4}$ with prob ≥$ \frac{8}{π^2}$, but I will get $ \frac{1}{2}$ or $\frac{1}{2} \pm \frac{1}{8}$ with prob ≥$ \frac{4}{π^2} $ .

2. Amplitude estimation is an application of phase estimation procedure to estimation the eigenvalue of the Grover iteration G, which in turn enable us to determine the amplitude of the initial state.

---

QPE:

Considering the phase $\varphi=\frac{9}{16}$, we use two bits to estimeate $\varphi=0.1001$. If the outcome of the final measurement is $ 10$, we obtain a pretty good estimate to $\varphi$(i.e., $\varphi$ is expressed exactly in two bits).

And supposing we wish to approximate $\varphi$ to an accuracy $2^{-1}$(i.e., $|\hat{\varphi} - \varphi| \le \epsilon =2^{-2}$), that is $\frac{-1}{4}\le \hat{\varphi} - \frac{1}{2} \le \frac{1}{4}$. The output of measurement is $\hat{\varphi}*2^2$, with the probability of success at least $P(|\hat{\varphi} - \varphi| \le 2^{-2}$)

IBM Q circuit use 'simulator_statevector'