Quantum phase estimation algorithm

In quantum computing, the quantum phase estimation algorithm (also referred to as quantum eigenvalue estimation algorithm), is a quantum algorithm to estimate the phase (or eigenvalue) of an eigenvector of a unitary operator. More precisely, given a unitary matrix $U$ and a quantum state $|\psi \rangle$ such that $U|\psi \rangle =e^{2\pi i\theta }|\psi \rangle$, the algorithm estimates the value of $\theta$ with high probability within additive error $\varepsilon$, using $O(\log(1/\varepsilon ))$ qubits (without counting the ones used to encode the eigenvector state) and $O(1/\varepsilon )$ controlled-U operations. The algorithm was initially introduced by Alexei Kitaev in 1995.

Phase estimation is frequently used as a subroutine in other quantum algorithms, such as Shor's algorithm, the quantum algorithm for linear systems of equations, and the quantum counting algorithm.

The problem

Let U be a unitary operator that operates on m qubits with an eigenvector $|\psi \rangle ,$ such that $U|\psi \rangle =e^{2\pi i\theta }\left|\psi \right\rangle ,0\leq \theta <1$.

We would like to find the eigenvalue $e^{2\pi i\theta }$of $|\psi \rangle$, which in this case is equivalent to estimating the phase $\theta$, to a finite level of precision. We can write the eigenvalue in the form $e^{2\pi i\theta }$ because U is a unitary operator over a complex vector space, so its eigenvalues must be complex numbers with absolute value 1.

The algorithm

The circuit for quantum phase estimation.

Setup

The input consists of two registers (namely, two parts): the upper $n$ qubits comprise the first register, and the lower $m$ qubits are the second register.

The initial state of the system is:

$|0\rangle ^{\otimes n}|\psi \rangle .$

After applying n-bit Hadamard gate operation $H^{\otimes n}$ on the first register, the state becomes:

${\frac {1}{2^{\frac {n}{2}}}}(|0\rangle +|1\rangle )^{\otimes n}|\psi \rangle ={\frac {1}{2^{n/2}}}\sum _{j=0}^{2^{n}-1}|j\rangle |\psi \rangle$.

Let $U$ be a unitary operator with eigenvector $|\psi \rangle$ such that $U|\psi \rangle =e^{2\pi i\theta }|\psi \rangle$. Thus,

$U^{2^{j}}|\psi \rangle =e^{2\pi i2^{j}\theta }|\psi \rangle$.

Overall, the transformation implemented on the two registers by the controlled gates applying $U,U^{2},U^{2^{2}},\ldots ,U^{2^{n-1}}$ is$$|k\rangle |\psi \rangle \mapsto |k\rangle U^{k}|\psi \rangle$$This can be seen by the decomposition of $k$ into its bitstring $k_{n-1}k_{n-2}\ldots k_{1}k_{0}$ and binary representation $2^{n-1}k_{n-1}+2^{n-2}k_{n-2}+\ldots +2k_{1}+k_{0}$, where $k_{n-1},\ldots ,k_{1},k_{0}\in \{0,1\}$. Clearly, $U^{k}$ becomes$$U^{2^{n-1}k_{n-1}+\ldots +2^{2}k_{2}+2k_{1}+k_{0}}=U^{2^{n-1}k_{n-1}}\ldots U^{2^{2}k_{2}}U^{2k_{1}}U^{k_{0}}$$Each $U^{2^{j}k_{j}}$ will only apply if the qubit $k_{j}$ is $1$, implying that it is controlled by that bit. Therefore the overall transformation to $|k\rangle U^{k}|\psi \rangle$ is equivalent to the controlled $U^{2^{j}}$ gates from each $j$-th qubit.

Therefore, the state will be transformed by the controlled $U^{2^{j}}$ gates like so:$${\frac {1}{\sqrt {2^{n}}}}\sum _{j=0}^{2^{n}-1}|j\rangle |\psi \rangle \mapsto {\frac {1}{\sqrt {2^{n}}}}\sum _{j=0}^{2^{n}-1}e^{2\pi ij\theta }|j\rangle |\psi \rangle$$At this point, the second register with the eigenvector is not needed. It can be reused again in another run of phase estimation. The state without $|\psi \rangle$ is

${\frac {1}{\sqrt {2^{n}}}}\sum _{j=0}^{2^{n}-1}e^{2\pi ij\theta }|j\rangle$

Apply inverse quantum Fourier transform

Applying the inverse quantum Fourier transform on

${\frac {1}{2^{\frac {n}{2}}}}\sum _{k=0}^{2^{n}-1}e^{2\pi i\theta k}|k\rangle$

yields

${\frac {1}{2^{\frac {n}{2}}}}\sum _{k=0}^{2^{n}-1}e^{2\pi i\theta k}\left({\frac {1}{2^{\frac {n}{2}}}}\sum _{x=0}^{2^{n}-1}e^{\frac {-2\pi ikx}{2^{n}}}|x\rangle \right)={\frac {1}{2^{n}}}\sum _{x=0}^{2^{n}-1}\sum _{k=0}^{2^{n}-1}e^{-{\frac {2\pi ik}{2^{n}}}\left(x-2^{n}\theta \right)}|x\rangle .$

We can approximate the value of $\theta \in [0,1]$ by rounding $2^{n}\theta$ to the nearest integer. This means that $2^{n}\theta =a+2^{n}\delta ,$ where $a$ is the nearest integer to $2^{n}\theta ,$ and the difference $2^{n}\delta$ satisfies $0\leqslant |2^{n}\delta |\leqslant {\tfrac {1}{2}}$.

Using this decomposition we can rewrite the state as ${\textstyle \sum _{x=0}^{2^{n}-1}c_{x}|x\rangle ,}$ where

$c_{x}\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 ik}{2^{n}}}\left(x-a\right)}e^{2\pi i\delta k}.$

Measurement

Performing a measurement in the computational basis on the first register yields the outcome $|y\rangle$ with probability$$\Pr(y)=|c_{y}|^{2}=\left|{\frac {1}{2^{n}}}\sum _{k=0}^{2^{n}-1}e^{{\frac {-2\pi ik}{2^{n}}}(y-a)}e^{2\pi i\delta k}\right|^{2}.$$It follows that $\operatorname {Pr} (a)=1$ if $\delta =0$, that is, when $\theta$ can be written as $\theta =a/2^{n}$, one always finds the outcome $y=a$. On the other hand, if $\delta \neq 0$, the probability reads$$\operatorname {Pr} (a)={\frac {1}{2^{2n}}}\left|\sum _{k=0}^{2^{n}-1}e^{2\pi i\delta k}\right|^{2}={\frac {1}{2^{2n}}}\left|{\frac {1-{e^{2\pi i2^{n}\delta }}}{1-{e^{2\pi i\delta }}}}\right|^{2}.$$From this expression we can see that $\Pr(a)\geqslant {\frac {4}{\pi ^{2}}}\approx 0.405$ when $\delta \neq 0$. To see this, we observe that from the definition of $\delta$ we have the inequality $|\delta |\leqslant {\tfrac {1}{2^{n+1}}}$, and thus:$${\begin{aligned}\Pr(a)&={\frac {1}{2^{2n}}}\left|{\frac {1-{e^{2\pi i2^{n}\delta }}}{1-{e^{2\pi i\delta }}}}\right|^{2}&&{\text{for }}\delta \neq 0\\[6pt]&={\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}\\[6pt]&={\frac {1}{2^{2n}}}{\frac {\left|\sin \left(\pi 2^{n}\delta \right)\right|^{2}}{|\sin(\pi \delta )|^{2}}}\\[6pt]&\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 |{\text{ for }}|\delta |\leqslant {\frac {1}{2^{n+1}}}\\[6pt]&\geqslant {\frac {1}{2^{2n}}}{\frac {|2\cdot 2^{n}\delta |^{2}}{|\pi \delta |^{2}}}&&|2\cdot 2^{n}\delta |\leqslant |\sin(\pi 2^{n}\delta )|{\text{ for }}|\delta |\leqslant {\frac {1}{2^{n+1}}}\\[6pt]&\geqslant {\frac {4}{\pi ^{2}}}.\end{aligned}}$$We conclude that the algorithm always provides the best $n$-bit estimate of $\theta$ with high probability. By increasing the number of qubits by $O(\log(1/\epsilon ))$ and ignoring those last qubits we can increase the probability to $1-\epsilon$.

Examples

Consider the simplest possible instance of the algorithm, where only $n=1$ qubit, on top of the qubits required to encode $|\psi \rangle$, is involved. Suppose the eigenvalue of $|\psi \rangle$ reads $\lambda =e^{2\pi i\theta }$. The first part of the algorithm generates the one-qubit state $|\phi \rangle \equiv {\frac {1}{\sqrt {2}}}(|0\rangle +\lambda |1\rangle )$. Applying the inverse QFT amounts in this case to applying a Hadamard gate. The final outcome probabilities are thus $p_{\pm }=|\langle \pm |\phi \rangle |^{2}$ where $|\pm \rangle \equiv {\frac {1}{\sqrt {2}}}(|0\rangle \pm |1\rangle )$, or more explicitly,$$p_{\pm }={\frac {|1\pm \lambda |^{2}}{4}}={\frac {1\pm \cos(2\pi \theta )}{2}}.$$It is clear that in this simple example, if $\lambda =\pm 1$, then $|\phi \rangle =|\pm \rangle$ and thus we deterministically recover the precise eigenvalue from the measurement outcome.

If on the other hand $\lambda =e^{2\pi i/3}$, then $p_{\pm }=[1\pm \cos(2\pi /3)]/2$, that is, $p_{+}=1/4$ and $p_{-}=3/4$. This is compatible with our general discussion because $2^{1}\theta =2/3$.

See also

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