quantum phase estimation algorithm

The algorithm operates on two sets of qubits, referred to in this context as registers. The two registers contain $n$ and $m$ qubits, respectively. Let $U$ be a unitary operator acting on the $m$-qubit register. The eigenvalues of a unitary operator have unit modulus, and are therefore characterized by their phase. Thus if $|\; \backslash psi\; \backslash rangle$ is an eigenvector of $U$, then $U|\; \backslash psi\backslash rangle\; =\; e^\{\; 2\backslash pi\; i\; \backslash theta\}\backslash left|\backslash psi\; \backslash right\backslash rangle$ for some $\backslash theta\backslash in\backslash mathbb\{R\}$. Due to the periodicity of the complex exponential, we can always assume .

The goal is producing a good approximation for $\backslash theta$ with a small number of gates and a high probability of success. The quantum phase estimation algorithm achieves this assuming oracular access to $U$, and having $|\backslash psi\backslash rangle$ available as a quantum state. This means that when discussing the efficiency of the algorithm we only worry about the number of times $U$ needs to be used, but not about the cost of implementing $U$ itself.

More precisely, the algorithm returns with high probability an approximation for $\backslash theta$, within additive error $\backslash varepsilon$, using $n=O(\backslash log(1/\backslash varepsilon))$ qubits in the first register, and $O(1/\backslash varepsilon)$ controlled-U operations. Furthermore, we can improve the success probability to $1-\backslash Delta$ for any $\backslash Delta>0$ by using a total of $O(\backslash log(1/\backslash Delta)/\backslash varepsilon)$ uses of controlled-U, and this is optimal.{{cite arXiv | eprint = 2305.04908| last1 = Mande| first1 = Nikhil S.| author2 = Ronald de Wolf| title = Tight Bounds for Quantum Phase Estimation and Related Problems| date = 2023| class = quant-ph}}

File:PhaseCircuit.svg

The initial state of the system is:

:$|\backslash Psi\_0\backslash rangle\; =\; |0\backslash rangle^\{\backslash otimes\; n\}|\backslash psi\backslash rangle\; ,$

where $|\backslash psi\backslash rangle$ is the $m$-qubit state that evolves through $U$. We first apply the n-qubit Hadamard gate operation $H^\{\backslash otimes\; n\}$ on the first register, which produces the state:$$|\backslash Psi\_1\backslash rangle\; =\; (H^\{\backslash otimes\; n\}\backslash otimes\; I\_m)|\backslash Psi\_0\backslash rangle\; =\; \backslash frac\{1\}\{2^\{\backslash frac\{n\}\{2\}\}\}(|0\backslash rangle\; +\; |1\backslash rangle)^\{\backslash otimes\; n\}|\backslash psi\backslash rangle\; =\; \backslash frac\{1\}\{2^\{n/2\}\}\; \backslash sum\_\{j\; =\; 0\}^\{2^n\; -\; 1\}\; |j\backslash rangle\; |\backslash psi\backslash rangle.$$Note that here we are switching between binary and $n$-ary representation for the $n$-qubit register: the ket $|j\backslash rangle$ on the right-hand side is shorthand for the $n$-qubit state $|j\backslash rangle\backslash equiv\; \backslash bigotimes\_\{\backslash ell=0\}^\{n-1\}\; |j\_\backslash ell\backslash rangle$, where $j=\backslash sum\_\{\backslash ell=0\}^\{n-1\}\; j\_\backslash ell\; 2^\backslash ell$ is the binary decomposition of $j$.

This state $|\backslash Psi\_1\backslash rangle$ is then evolved through the controlled-unitary evolution $U\_C$ whose action can be written as$$U\_C(|k\backslash rangle\backslash otimes|\backslash psi\backslash rangle)\; =\; |k\backslash rangle\backslash otimes(\; U^\{k\}|\backslash psi\backslash rangle),$$ for all $k=0,...,2^n-1$. This evolution can also be written concisely as$$U\_C\; =\; \backslash sum\_\{k=0\}^\{2^n-1\}\; |k\backslash rangle\backslash !\backslash langle\; k|\backslash otimes\; U^k,$$ which highlights its controlled nature: it applies $U^k$ to the second register conditionally to the first register being $|k\backslash rangle$. Remembering the eigenvalue condition holding for $|\backslash psi\backslash rangle$, applying $U\_C$ to $|\backslash Psi\_1\backslash rangle$ thus gives$$|\backslash Psi\_2\backslash rangle\; \backslash equiv\; U\_C|\backslash Psi\_1\backslash rangle$$

= \left(\frac{1}{2^{n/2}}\sum_{k=0}^{2^n-1} e^{2\pi i \theta k}|k\rangle\right)\otimes |\psi\rangle, where we used $U^\{k\}|\; \backslash psi\backslash rangle\; =\; e^\{\; 2\backslash pi\; i\; k\backslash theta\}|\backslash psi\; \backslash rangle$.

To show that $U\_C$ can also be implemented efficiently, observe that we can write $U\_C\; =\; \backslash prod\_\{\backslash ell=0\}^\{n-1\}\; C\_\backslash ell(U^\{2^\backslash ell\})$, where $C\_\backslash ell(U^\{2^\backslash ell\})$ denotes the operation of applying $U^\{2^\backslash ell\}$ to the second register conditionally to the $\backslash ell$-th qubit of the first register being $|1\backslash rangle$. Formally, these gates can be characterized by their action as$$C\_\backslash ell(U^k)\; (|j\backslash rangle\backslash otimes\; |\backslash psi\backslash rangle)$$

= |j\rangle\otimes ( U^{j_\ell k}|\psi\rangle).This equation can be interpreted as saying that the state is left unchanged when $j\_\backslash ell=0$, that is, when the $\backslash ell$-th qubit is $|0\backslash rangle$, while the gate $U^k$ is applied to the second register when the $\backslash ell$-th qubit is $|1\backslash rangle$. The composition of these controlled-gates thus gives$$\backslash prod\_\{\backslash ell=0\}^\{n-1\}\; C\_\backslash ell(U^\{2^\backslash ell\})(|j\backslash rangle\backslash otimes|\backslash psi\backslash rangle)$$

= |j\rangle\otimes\left(U^{\sum_{\ell=0}^{n-1} j_\ell 2^\ell} |\psi\rangle\right)= U_C , with the last step directly following from the binary decomposition $j=\backslash sum\_\{\backslash ell=0\}^\{n-1\}\; j\_\backslash ell\; 2^\backslash ell$.

From this point onwards, the second register is left untouched, and thus it is convenient to write $|\backslash Psi\_2\backslash rangle=|\backslash tilde\backslash Psi\_2\backslash rangle\backslash otimes|\backslash psi\backslash rangle$, with $|\backslash tilde\backslash Psi\_2\backslash rangle$ the state of the $n$-qubit register, which is the only one we need to consider for the rest of the algorithm.

The final part of the circuit involves applying the inverse quantum Fourier transform (QFT) $\backslash mathcal\{QFT\}$ on the first register of $|\backslash Psi\_2\backslash rangle$:$$|\backslash tilde\backslash Psi\_3\backslash rangle\; =\; \backslash mathcal\{QFT\}^\{-1\}\_\{2^n\}\; |\backslash tilde\backslash Psi\_2\backslash rangle.$$The QFT and its inverse are characterized by their action on basis states as$$\backslash begin\{align\}$$

\mathcal{QFT}_N|k\rangle &= N^{-1/2}\sum_{j=0}^{N-1} e^{\frac{2\pi i}{N}jk}|j\rangle, \\

\mathcal{QFT}_N^{-1}|k\rangle &= N^{-1/2}\sum_{j=0}^{N-1} e^{-\frac{2\pi i}{N}jk}|j\rangle.

\end{align} It follows that

:$|\backslash tilde\backslash Psi\_3\backslash rangle\; =\; \backslash frac\{1\}\{2^\{\backslash frac\{n\}\{2\}\}\}\backslash sum\_\{k=0\}^\{2^n\; -\; 1\}\; e^\{2\backslash pi\; i\; \backslash theta\; k\}\; \backslash left(\; \backslash frac\{1\}\{2^\{\backslash frac\{n\}\{2\}\}\}\backslash sum\_\{x=0\}^\{2^n\; -\; 1\}\; e^\{\backslash frac\{-2\backslash pi\; i\; k\; x\}\{2^n\}\}|x\backslash rangle\; \backslash right)\; =\; \backslash frac\{1\}\{2^\{n\}\}\backslash sum\_\{x=0\}^\{2^n\; -\; 1\}\; \backslash sum\_\{k=0\}^\{2^n\; -\; 1\}e^\{-\backslash frac\{2\backslash pi\; i\; k\}\{2^n\}\; \backslash left\; (\; x\; -\; 2^n\; \backslash theta\; \backslash right\; )\}\; |x\backslash rangle.$

Decomposing the state in the computational basis as $|\backslash tilde\backslash Psi\_3\backslash rangle\; =\; \backslash sum\_\{x=0\}^\{2^n-1\}\; c\_x\; |x\backslash rangle,$ the coefficients thus equal$$c\_x\; \backslash equiv$$

\frac{1}{2^n} \sum_{k=0}^{2^n-1} e^{-\frac{2\pi ik}{2^n}(x-2^n \theta) } =

\frac{1}{2^{n}} \sum_{k=0}^{2^n - 1} e^{-\frac{2\pi i k}{2^n} \left ( x-a \right )} e^{2 \pi i \delta k},where we wrote $2^n\; \backslash theta\; =\; a\; +\; 2^n\; \backslash delta,$ with $a$ is the nearest integer to $2^n\; \backslash theta$. The difference $2^n\backslash delta$ must by definition satisfy $0\; \backslash leqslant\; |2^n\backslash delta|\; \backslash leqslant\; \backslash tfrac\{1\}\{2\}$. This amounts to approximating the value of $\backslash theta\; \backslash in\; [0,\; 1]$ by rounding $2^n\; \backslash theta$ to the nearest integer.

The final step involves performing a measurement in the computational basis on the first register. This yields the outcome $|y\backslash rangle$ with probability$$\backslash Pr(y)\; =\; |c\_y|^2\; =\; \backslash left|\; \backslash frac\{1\}\{2^\{n\}\}\; \backslash sum\_\{k=0\}^\{2^n-1\}\; e^\{\backslash frac\{-2\backslash pi\; i\; k\}\{2^n\}(y-a)\}\; e^\{2\; \backslash pi\; i\; \backslash delta\; k\}\; \backslash right\; |^2.$$

It follows that $\backslash operatorname\{Pr\}(a)=1$ if $\backslash delta=0$, that is, when $\backslash theta$ can be written as $\backslash theta=a/2^n$, one always finds the outcome $y=a$. On the other hand, if $\backslash delta\backslash neq0$, the probability reads$$\backslash operatorname\{Pr\}(a)=\backslash frac\{1\}\{2^\{2n\}\}\; \backslash left\; |\; \backslash sum\_\{k=0\}^\{2^n-1\}\; e^\{2\; \backslash pi\; i\; \backslash delta\; k\}\; \backslash right\; |^2\; =\; \backslash frac\{1\}\{2^\{2n\}\}\; \backslash left\; |\; \backslash frac\{1-\; \{e^\{2\; \backslash pi\; i\; 2^n\; \backslash delta\}\}\}\{1-\{e^\{2\; \backslash pi\; i\; \backslash delta\}\}\}\; \backslash right|^2.$$

From this expression we can see that $\backslash Pr(a)\; \backslash geqslant\; \backslash frac\{4\}\{\backslash pi^2\}\; \backslash approx\; 0.405$ when $\backslash delta\backslash neq0$. To see this, we observe that from the definition of $\backslash delta$ we have the inequality $|\backslash delta|\; \backslash leqslant\; \backslash tfrac\{1\}\{2^\{n+1\}\}$, and thus:{{cite book|last1=Benenti|first1=Guiliano|last2=Casati|first2=Giulio|last3=Strini|first3=Giuliano|title=Principles of quantum computation and information|date=2004|publisher=World Scientific| location=New Jersey [u.a.]|isbn=978-9812388582|edition=Reprinted.}}{{rp|157}}{{cite journal| last1=Cleve| first1=R.| last2=Ekert |first2=A. |last3=Macchiavello| first3=C.| last4=Mosca|first4=M.|title=Quantum algorithms revisited|journal=Proceedings of the Royal Society A: Mathematical, Physical and Engineering Sciences|date=8 January 1998| volume=454| issue=1969| pages=339–354|doi=10.1098/rspa.1998.0164|arxiv=quant-ph/9708016|bibcode=1998RSPSA.454..339C| s2cid=16128238}}{{rp|348}}$$\backslash begin\{align\}$$

\Pr(a) &= \frac{1}{2^{2n}} \left | \frac{1- {e^{2 \pi i 2^n \delta}}}{1-{e^{2 \pi i \delta}}} \right |^2 && \text{for } \delta \neq 0 \\

&= \frac{1}{2^{2n}} \left | \frac{2 \sin \left ( \pi 2^n \delta\right)}{ 2\sin( \pi \delta)} \right |^2 && \left| 1-e^{2ix}\right|^2 = 4\left| \sin (x)\right|^2 \\

&= \frac{1}{2^{2n}} \frac {\left | \sin\left(\pi 2^n \delta\right) \right |^2}{| \sin( \pi \delta) |^2} \\

&\geqslant \frac{1}{2^{2n}} \frac {\left | \sin\left(\pi 2^n \delta\right) \right |^2}{| \pi \delta |^2} && | \sin(\pi \delta) | \leqslant | \pi \delta | \\

&\geqslant \frac{1}{2^{2n}} \frac {|2 \cdot 2^n \delta|^2}{| \pi \delta |^2} && | 2\cdot2^n \delta | \leqslant | \sin(\pi 2^n\delta) | \text{ for } |\delta| \leqslant \frac{1}{2^{n+1}} \\

&\geqslant \frac {4}{\pi^2}

.\end{align}

We conclude that the algorithm provides the best $n$-bit estimate (i.e., one that is within $1/2^n$ of the correct answer) of $\backslash theta$ with probability at least $4/\backslash pi^2$. By adding a number of extra qubits on the order of $O(\backslash log(1/\backslash epsilon))$ and truncating the extra qubits the probability can increase to $1\; -\; \backslash epsilon$.

Consider the simplest possible instance of the algorithm, where only $n=1$ qubit, on top of the qubits required to encode $|\backslash psi\backslash rangle$, is involved. Suppose the eigenvalue of $|\backslash psi\backslash rangle$ reads $\backslash lambda=e^\{2\backslash pi\; i\; \backslash theta\}$, $\backslash theta\backslash in[0,1)$. The first part of the algorithm generates the one-qubit state $|\backslash phi\backslash rangle\backslash equiv\; \backslash frac\{1\}\{\backslash sqrt2\}(|0\backslash rangle+\backslash lambda\; |1\backslash rangle)$. Applying the inverse QFT amounts in this case to applying a Hadamard gate. The final outcome probabilities are thus $p\_\backslash pm\; =\; |\backslash langle\backslash pm|\backslash phi\backslash rangle|^2$ where $|\backslash pm\backslash rangle\backslash equiv\backslash frac\{1\}\{\backslash sqrt2\}(|0\backslash rangle\backslash pm|1\backslash rangle)$, or more explicitly,$$p\_\backslash pm\; =\; \backslash frac\{|1\backslash pm\backslash lambda|^2\}\{4\}$$

=\frac{1 \pm \cos(2\pi \theta)}{2}. Suppose $\backslash lambda=1$, meaning $|\backslash phi\backslash rangle=|+\backslash rangle$. Then $p\_+=1$, $p\_-=0$, and we recover deterministically the precise value of $\backslash lambda$ from the measurement outcomes. The same applies if $\backslash lambda=-1$.

If on the other hand $\backslash lambda=e^\{2\backslash pi\; i/3\}$, then $p\_\backslash pm\; =\; [1\; \backslash pm\; \backslash cos(2\backslash pi/3)]/2$, that is, $p\_+=1/4$ and $p\_-=3/4$. In this case the result is not deterministic, but we still find the outcome $|-\backslash rangle$ as more likely, compatibly with the fact that $2/3$ is closer to 1 than to 0.

More generally, if $\backslash lambda=e^\{2\backslash pi\; i\backslash theta\}$, then $p\_+\backslash ge\; 1/2$ if and only if $|\backslash theta|\backslash le\; 1/4$. This is consistent with the results above because in the cases $\backslash lambda=\backslash pm1$, corresponding to $\backslash theta=0,1/2$, the phase is retrieved deterministically, and the other phases are retrieved with higher accuracy the closer they are to these two.

• Shor's algorithm
• Quantum counting algorithm
• Parity measurement

{{Reflist}}

{{Quantum information}}

{{DEFAULTSORT:Quantum Phase Estimation Algorithm}}

Category:Quantum algorithms