9
$\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, 2021 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$ Mar 5, 2021 at 12:13

2 Answers 2

4
+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$ Mar 7, 2021 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$ Apr 15, 2021 at 20:46
0
$\begingroup$
  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'

use 'simulator_statevector'

$\endgroup$
3
  • $\begingroup$ Hey Jason, thanks for the reply! I don't think the $\frac{8}{\pi^2}$ probability includes $\frac{1}{2}-\frac{1}{4} = \frac{1}{4}$, since $\frac{9}{16}-\frac{1}{4} > 2^{-n}$ for $n=2$. $\endgroup$ May 3, 2021 at 21:05
  • $\begingroup$ Also I don't think we can actually get the output $\frac{1}{2} \pm \frac{1}{8}$ since we only have two ancilla qubits, which limits us to a precision of $\frac{1}{4}$. $\endgroup$ May 3, 2021 at 21:14
  • $\begingroup$ I hava amended my original answer. For the case $\frac{1}{2} + \frac{1}{8}=\frac{10}{16}=0.1010$, $\frac{1}{2} - \frac{1}{8}=\frac{6}{16}=0.0110$, the circuit of QPE has computed , even though the bits of register is not enough, which can also be testify in IBM Q. $\endgroup$
    – Jason Zhao
    May 4, 2021 at 7:23

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.