# Phase estimation error analysis

This question is about Lemma $$7.1.2$$ in Kaye, Laflamme, and Mosca's textbook:

Let $$\omega = \frac{x}{2^n} = 0.x_1x_2\ldots x_n$$ be some fixed number. The phase estimation algorithm applied to the input state $$|\psi\rangle = \frac{1}{\sqrt{2^n}}\sum_{y=0}^{2^n-1}e^{2\pi i \omega y}|y\rangle$$ outputs the integer $$x$$ with probability $$p(x) = \frac{1}{2^{2n}}\frac{\sin^2(\pi(2^n\omega-x))}{\sin^2(\pi(\omega-x/2^n))}$$

Is there a mistake here? I thought that the phase estimation algorithm outputs the integer $$x$$ with 100% certainty, since that's the whole point of the algorithm.

By definition, the quantum Fourier transform is the map:

$$\mathrm{QFT}_m^{-1} : \frac{1}{\sqrt{m}}\sum_{y=0}^{m-1}e^{2\pi i \frac{x}{m} y}|y\rangle \mapsto|x\rangle$$

Why is this not 100% successful?

• No, it's not the "point" of the algorithm to give $x$ with 100% certainty. Quantum algorithms are (almost) always probabilistic. The details of QPE is given on Wikipedia. You might want to read What level of “confidence” of the result from a quantum computer is possible?. May 21, 2019 at 17:02
• As a point of note, quantum algorithms need not be probabilistic; the Deutsch–Jozsa algorithm, for instance, succeeds with certainty on a quantum computer. May 21, 2019 at 18:22
• @SanchayanDutta If I take the inverse QFT of the state $|\psi\rangle$ and then measure in the computational basis, do I not get the value $x$ with 100% certainty?
– NNN
May 21, 2019 at 19:05
• @ChrisGranade Ah, indeed. There are some deterministic quantum algorithms too (belonging to the EQP class). But that isn't the case in OP's QPE algorithm. Thanks for the clarification though! May 21, 2019 at 20:09
• I don’t have the book to hand. Are you sure that both $x$ and $\psi$ are defined with $n$? I would expect one to use n and the other m. May 22, 2019 at 5:41

Let me augment the discussion by adding some insight into the derivation of the estimate provided. This will give you a good understanding of when the result is an approximation and when it is precise. After the algorithm has run, we are left with the following state on the first register:

$$\frac{1}{2^{n}}\sum_{x=0}^{2^n - 1} \sum_{k=0}^{2^n - 1}e^{-\frac{2\pi i k}{2^n} \left ( i_{0} - 2^n \theta \right )} |x\rangle,$$

where $$i_{0}$$ is the integer closest to $$2^{n}\omega$$ such that $$i_{0} < 2^{n}\omega$$ ($$2^{n}\omega = i_{0}-2^{n}\delta$$). When measurement occurs, the axioms of quantum mechanics give you that the probability of measuring $$i_{0}$$ is $$\mathrm{prob}(i_{0})=\frac{1}{2^{2n}} \left | \sum_{k=0}^{2^n-1} e^{2 \pi i \delta k} \right |^2.$$

Notice that at the point you are asked to evaluate a finite geometrical series. We have the formula: $$\sum_{k=0}^{n-1} ar^k= a \left(\frac{1-r^{n}}{1-r}\right), (1)$$

valid only for $$r\neq 1$$ . This is a key point in the whole discussion as for $$\delta = 0$$ we simply end up adding $$\frac{1}{2^{n}}$$ $$2^{n}$$ times and so we get $$\frac{(2^{n})^{2}}{2^{2n}}=1$$ (we do not use the formula). So in the case of $$2^{n}\omega$$ being an integer, we have concluded that the probability of getting the exact value of the phase is 100%. If $$\delta\neq 0$$ we use the formula (1) and get $$\mathrm{prob}(i_{0})=\frac{1}{2^{2n}} \left | \frac{1- {e^{2 \pi i 2^n \delta}}}{1-{e^{2 \pi i \delta}}} \right |^2.(2)$$

Now notice that $$4\left | \sin(x)) \right |^{2}=4\left | \frac{e^{-ix}-e^{ix}}{2i}\right |^{2}=\left | e^{-ix}-e^{ix} \right |^{2}=\left | 1-e^{2ix} \right |^{2}.(3)$$

Using identity (3) we may rewrite (2) as $$\mathrm{prob}(i_{0})=\frac{1}{2^{2n}} \frac{\sin^{2}(\pi \delta 2^{n})}{\sin^{2}(\pi \delta)},$$

using the definition of $$\delta$$ we get (for $$\delta \neq 0$$) $$\mathrm{prob}(i_{0})=\frac{1}{2^{2n}} \frac{\sin^{2}(\pi (2^{n}\omega -i_{0}))}{\sin^{2}(\pi(\omega -\frac{i_{0}}{2^{n}}))},$$

which is exactly the result you were looking for. With a bit more effort it is possible to show that in the case where $$\delta \neq 0$$ the following holds $$\mathrm{prob}(i_{0})\geqslant \frac{4}{\pi ^{2}}.$$

So we may conclude with stating that for some special phases (such that $$2^{n}\omega$$ is an integer) we can extract the exact value of the phase. However, in the general case where $$2^{n}\omega$$ is not an integer, we get an approximation of the phase with a probability of at least $$\frac{4}{\pi ^{2}}$$.

• $i_0$ is not the integer closest to $2^n \omega$, it's the closest integer smaller than $2^n\omega$. Consider $\omega = 1 - \epsilon$ for small $\epsilon$, you'd end up with $i_0 = 2^n$ which is not an $n$-bit integer, but $n+1$ bit. See Nielsen and Chuang 5.2.1.
– orlp
Nov 27, 2019 at 13:52
• @orlp Thank you for your kind comment. Point noted! I added this comment to the answer. Nov 28, 2019 at 19:29

First point: in most of the cases, the QPE algorithm cannot output the integer $$x$$. That is why $$w$$ is introduced in the algorithm: to represent the closest approximation of $$x$$ that can be returned by the QPE.

About your question, no the QPE is not always 100% successful (in this case successful means that the algorithm returns $$w$$, the closest approximation of $$x$$ possible on $$n$$ qubits).

The final state of the QPE before measurement is given by (according to Wikipedia):

$$\frac{1}{2^{n}} \sum_{x=0}^{2^n - 1} \sum_{k=0}^{2^n - 1} e^{-\frac{2\pi i k}{2^n} \left ( x-w \right )} e^{2 \pi i \delta k} |x\rangle \otimes |\psi\rangle.$$ where:

1. $$n$$, $$w$$, and $$x$$ are defined as in your question.
2. $$\delta = \left\vert \frac{x}{2^n} - w \right\vert = \left\vert \frac{x}{2^n} - \text{round}\left(\frac{x}{2^n}\right) \right\vert$$ is the error due to the finite representation of $$w$$.

I will not rewrite all the calculations, but you can check on the intermediate results on the Wikipedia page.

The probability of getting the right result $$w$$ when measuring is then

$$\Pr(w) = \left | \left \langle w \underbrace{\left | \frac{1}{2^{n}} \sum_{x=0}^{2^n-1} \sum_{k=0}^{2^n-1} e^{\frac{-2\pi i k}{2^n}(x-w)} e^{2 \pi i \delta k} \right |}_{\text{State of the first register}} x \right \rangle \right |^2 = \frac{1}{2^{2n}} \left | \sum_{k=0}^{2^n-1} e^{2 \pi i \delta k} \right |^2 = \begin{cases}1 & \delta = 0\\ & \\ \frac{1}{2^{2n}} \left | \frac{1- {e^{2 \pi i 2^n \delta}}}{1-{e^{2 \pi i \delta}}} \right|^2 & \delta \neq 0 \end{cases}$$

So:

• if the result $$x$$ can be represented exactly on $$n$$ qubits (i.e. $$\delta$$, the error, is $$0$$), the QPE succeed with a probability of $$1$$,
• but if $$n$$ bits are not enough to represent exactly $$x$$, the QPE might fail.

I tried quickly to derive the expression of your book from the one found on Wikipedia, without success but when the error $$\delta$$ tends to $$0$$, both formulas have the same behaviour: the probability of error is $$\sim \mathcal{O}\left( \frac{1}{2^{2n} \delta^2} \right)$$.

We can simplify further this big-$$\mathcal{O}$$ notation by noticing that, by construction, $$\delta \leqslant \frac{1}{2^{n+1}}$$. The final probability of error is then $$\Pr(\text{measurement not returning } \vert w \rangle) \sim \mathcal{O}\left( \frac{1}{2^{4n+1}} \right)$$

This means that, when you increase the number of qubits $$n$$ used to represent the solution by $$1$$, the probability of the QPE returning a bad result is divided by $$16$$.

: There are constants ignored by the big-$$\mathcal{O}$$ notation that change this value of $$16 = 2^4$$ to something like $$\frac{2^5}{\pi^2} = \frac{32}{\pi^2}$$. The additional factor of $$2$$ in the previous constant is needed to bound the expression $$\left\vert 1- {e^{2 \pi i 2^n \delta}} \right\vert$$ found for $$\Pr(w)$$ above but is not needed for the expression given in your book.

You are right. There is a slight typo. What the lemma is supposed to say is $$\omega=0.x_1 x_2 \ldots x_n x_{n+1} \ldots$$ or $$\omega=0.x_1 x_2 \ldots x_n + a$$ where $$a \leq 2^{-(n+1)}$$. In other words, $$x=x_1, x_2, \ldots x_n$$ are the the first $$n$$ digits of $$\omega$$.

Note that as written, the lemma doesn't make much sense since the denominator of $$p(x)$$ becomes $$sin^2(\pi(\omega-x/2^n))=sin^2(0)=0$$ when $$a=0$$. On the other hand, note that $$\lim_{a\rightarrow 0} p(x) = \lim_{b\rightarrow 0}\frac{1}{2^{2n}}\left(\frac{sin(2^n b)}{sin(b)}\right)^2=\lim_{b\rightarrow 0}\frac{1}{2^{2n}}\left(\frac{2^n b}{b}\right)^2 = 1$$ since $$sin(x) \approx x$$ for small $$x$$. So if you extend $$f(a)=p(0.x_1\ldots x_n + a)$$ continuously to $$a=0$$, then the lemma makes sense for the edge case as well.