# 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?. – Sanchayan Dutta May 21 '19 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. – Chris Granade May 21 '19 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? – Alex May 21 '19 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! – Sanchayan Dutta May 21 '19 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. – DaftWullie May 22 '19 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 '19 at 13:52
• @orlp Thank you for your kind comment. Point noted! I added this comment to the answer. – Alex East Nov 28 '19 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$$[1].

[1]: 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.