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.: 246

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

## 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 Quantum phase estimation circuit

### 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.

### Create superposition

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

### Apply controlled unitary operations

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

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

$C-U$ is a controlled-U gate which applies the unitary operator $U$ on the second register only if its corresponding control bit (from the first register) is $|1\rangle$ .

Assuming for the sake of clarity that the controlled gates are applied sequentially, after applying $C-U^{2^{0))$ to the $n^{th)$ qubit of the first register and the second register, the state becomes

${\frac {1}{2^{\frac {1}{2))))\underbrace {\left(|0\rangle |\psi \rangle +|1\rangle e^{2\pi i2^{0}\theta }|\psi \rangle \right)} _{n^{th}\ qubit\ and\ second\ register}\otimes {\frac {1}{2^{\frac {n-1}{2))))\underbrace {\left(|0\rangle +|1\rangle \right)^{\otimes ^{n-1))} _{qubits\ 1^{st}\ to\ n-1^{th))={\frac {1}{2^{\frac {1}{2))))\left(|0\rangle |\psi \rangle +e^{2\pi i2^{0}\theta }|1\rangle |\psi \rangle \right)\otimes {\frac {1}{2^{\frac {n-1}{2))))\left(|0\rangle +|1\rangle \right)^{\otimes ^{n-1))$ $={\frac {1}{2^{\frac {1}{2))))\left(|0\rangle +e^{2\pi i2^{0}\theta }|1\rangle \right)|\psi \rangle \otimes {\frac {1}{2^{\frac {n-1}{2))))\left(|0\rangle +|1\rangle \right)^{\otimes ^{n-1))={\frac {1}{2^{\frac {n}{2))))\underbrace {\left(|0\rangle +e^{2\pi i2^{0}\theta }|1\rangle \right)} _{n^{th}\ qubit}\otimes \left(|0\rangle +|1\rangle \right)^{\otimes ^{n-1))|\psi \rangle ,$ where we use:

$|0\rangle |\psi \rangle +|1\rangle \otimes e^{2\pi i2^{j}\theta }|\psi \rangle =(|0\rangle +e^{2\pi i2^{j}\theta }|1\rangle )|\psi \rangle ,\ \forall j.$ After applying all the remaining $n-1$ controlled operations $C-U^{2^{j))$ with $1\leq j\leq n-1,$ as seen in the figure, the state of the first register can be described as

${\frac {1}{2^{\frac {n}{2))))\underbrace {\left(|0\rangle +e^{2\pi i2^{n-1}\theta }|1\rangle \right)} _{1^{st}\ qubit}\otimes \cdots \otimes \underbrace {\left(|0\rangle +e^{2\pi i2^{1}\theta }|1\rangle \right)} _{n-1^{th}\ qubit}\otimes \underbrace {\left(|0\rangle +e^{2\pi i2^{0}\theta }|1\rangle \right)} _{n^{th}\ qubit}={\frac {1}{2^{\frac {n}{2))))\sum _{k=0}^{2^{n}-1}e^{2\pi i\theta k}|k\rangle ,$ where $|k\rangle$ denotes the binary representation of $k$ , i.e. it's the $k^{th)$ computational basis, and the state of the second register is left physically unchanged at $|\psi \rangle$ .

### Apply inverse quantum Fourier transform

Applying 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}{\frac {1}{2^{\frac {n}{2))))\sum _{x=0}^{2^{n}-1}e^{\frac {-2\pi ikx}{2^{n))}|x\rangle ={\frac {1}{2^{n))}\sum _{x=0}^{2^{n}-1}\sum _{k=0}^{2^{n}-1}e^{2\pi i\theta k}e^{\frac {-2\pi ikx}{2^{n))}|x\rangle ={\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 .$ The state of both registers together is

${\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 \otimes |\psi \rangle .$ ### Phase approximation representation

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))$ .

We can now write the state of the first and second register in the following way:

${\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-a\right)}e^{2\pi i\delta k}|x\rangle \otimes |\psi \rangle .$ ### Measurement

Performing a measurement in the computational basis on the first register yields the result $|a\rangle$ with probability

$\Pr(a)=\left|\left\langle a\underbrace {\left|{\frac {1}{2^{n))}\sum _{x=0}^{2^{n}-1}\sum _{k=0}^{2^{n}-1}e^((\frac {-2\pi ik}{2^{n))}(x-a)}e^{2\pi i\delta k}\right|x} _{\text{State of the first register))\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 i2^{n}\delta ))}{1-{e^{2\pi i\delta ))))\right|^{2}&\delta \neq 0\end{cases))$ For $\delta =0$ the approximation is precise, thus $a=2^{n}\theta$ and $\Pr(a)=1.$ In this case, we always measure the accurate value of the phase.: 157 : 347  The state of the system after the measurement is $|2^{n}\theta \rangle \otimes |\psi \rangle$ .: 223

For $\delta \neq 0$ since $|\delta |\leqslant {\tfrac {1}{2^{n+1)))$ the algorithm yields the correct result with probability $\Pr(a)\geqslant {\frac {4}{\pi ^{2))}\approx 0.405$ . We prove this as follows:: 157 : 348

{\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)) This result shows that we will measure 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$ .