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 ${\displaystyle U}$ and a quantum state ${\displaystyle |\psi \rangle }$ such that ${\displaystyle U|\psi \rangle =e^{2\pi i\theta }|\psi \rangle }$, the algorithm estimates the value of ${\displaystyle \theta }$ with high probability within additive error ${\displaystyle \varepsilon }$, using ${\displaystyle O(\log(1/\varepsilon ))}$ qubits (without counting the ones used to encode the eigenvector state) and ${\displaystyle O(1/\varepsilon )}$ controlled-U operations. The algorithm was initially introduced by Alexei Kitaev in 1995.^{[1][2]: 246}

Phase estimation is frequently used as a subroutine in other quantum algorithms, such as Shor's algorithm^[2]: 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 ${\displaystyle |\psi \rangle ,}$ such that ${\displaystyle U|\psi \rangle =e^{2\pi i\theta }\left|\psi \right\rangle ,0\leq \theta <1}$.

We would like to find the eigenvalue ${\displaystyle e^{2\pi i\theta }}$of ${\displaystyle |\psi \rangle }$, which in this case is equivalent to estimating the phase ${\displaystyle \theta }$, to a finite level of precision. We can write the eigenvalue in the form ${\displaystyle 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[]

Setup[]

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

Create superposition[]

The initial state of the system is:

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

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

${\displaystyle {\frac {1}{2^{\frac {n}{2}}}}(|0\rangle +|1\rangle )^{\otimes n}|\psi \rangle }$.

Apply controlled unitary operations[]

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

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

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

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

${\displaystyle {\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}}}$${\displaystyle ={\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:

${\displaystyle |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 ${\displaystyle n-1}$ controlled operations ${\displaystyle C-U^{2^{j}}}$ with ${\displaystyle 1\leq j\leq n-1,}$ as seen in the figure, the state of the first register can be described as

${\displaystyle {\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 ${\displaystyle |k\rangle }$ denotes the binary representation of ${\displaystyle k}$, i.e. it's the ${\displaystyle k^{th}}$ computational basis, and the state of the second register is left physically unchanged at ${\displaystyle |\psi \rangle }$.

Apply inverse quantum Fourier transform[]

Applying inverse quantum Fourier transform on

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

yields

${\displaystyle {\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

${\displaystyle {\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 ${\displaystyle \theta \in [0,1]}$ by rounding ${\displaystyle 2^{n}\theta }$ to the nearest integer. This means that ${\displaystyle 2^{n}\theta =a+2^{n}\delta ,}$ where ${\displaystyle a}$ is the nearest integer to ${\displaystyle 2^{n}\theta ,}$ and the difference ${\displaystyle 2^{n}\delta }$ satisfies ${\displaystyle 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:

${\displaystyle {\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 ${\displaystyle |a\rangle }$ with probability

${\displaystyle \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 ${\displaystyle \delta =0}$ the approximation is precise, thus ${\displaystyle a=2^{n}\theta }$ and ${\displaystyle \Pr(a)=1.}$ In this case, we always measure the accurate value of the phase.^{[3]: 157 [4]: 347} The state of the system after the measurement is ${\displaystyle |2^{n}\theta \rangle \otimes |\psi \rangle }$.^[2]: 223

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

${\displaystyle {\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 ${\displaystyle \theta }$ with high probability. By increasing the number of qubits by ${\displaystyle O(\log(1/\epsilon ))}$ and ignoring those last qubits we can increase the probability to ${\displaystyle 1-\epsilon }$.^[4]

See also[]

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

References[]