4
$\begingroup$

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?

$\endgroup$
  • 3
    $\begingroup$ 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?. $\endgroup$ – Sanchayan Dutta May 21 at 17:02
  • $\begingroup$ As a point of note, quantum algorithms need not be probabilistic; the Deutsch–Jozsa algorithm, for instance, succeeds with certainty on a quantum computer. $\endgroup$ – Chris Granade May 21 at 18:22
  • $\begingroup$ @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? $\endgroup$ – Alex May 21 at 19:05
  • $\begingroup$ @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! $\endgroup$ – Sanchayan Dutta May 21 at 20:09
  • $\begingroup$ 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. $\endgroup$ – DaftWullie May 22 at 5:41
3
$\begingroup$

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$ ($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}}$.

$\endgroup$
1
$\begingroup$

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.

$\endgroup$

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.