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^, \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 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^\left, \psi \right\rangle , 0 \leq \theta < 1$.

We would like to find the eigenvalue $e^$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^$ 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 $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^, \psi\rangle .$

After applying ''n-bit'' Hadamard gate operation $H^$ on the first register, the state becomes:
:$\frac(, 0\rangle + , 1\rangle)^, \psi\rangle$.

Apply controlled unitary operations

Let $U$ be a unitary operator with eigenvector $, \psi\rangle$ such that $U, \psi \rangle = e^, \psi \rangle,$ thus by exponentiation by squaring,

:$U^, \psi\rangle = U^ U^ , \psi\rangle = U^ e^, \psi \rangle = e^, \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^$to the $n^$ qubit of the first register and the second register, the state becomes

:$\frac \underbrace_ \otimes \frac \underbrace _ = \frac \left (, 0\rangle, \psi \rangle + e^ , 1\rangle , \psi\rangle \right ) \otimes \frac \left (, 0\rangle + , 1\rangle \right )^$$= \frac \left (, 0\rangle + e^ , 1\rangle \right ) , \psi\rangle \otimes \frac \left (, 0\rangle + , 1\rangle \right )^ = \frac \underbrace _ \otimes \left (, 0\rangle + , 1\rangle \right )^ , \psi\rangle ,$

where we use:
:$, 0\rangle , \psi\rangle + , 1\rangle \otimes e^ , \psi\rangle =(, 0\rangle + e^ , 1\rangle) , \psi\rangle, \ \forall j .$

After applying all the remaining $n-1$ controlled operations $C-U^$ with $1 \leq j \leq n-1,$ as seen in the figure, the state of the first register can be described as

:$\frac \underbrace_ \otimes \cdots \otimes \underbrace_ \otimes\underbrace_ = \frac\sum_^ e^ , k\rangle,$
where $, k\rangle$ denotes the binary representation of $k$, i.e. it's the $k^$ 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\sum_^ e^ , k\rangle$

yields

:$\frac\sum_^ e^ \frac\sum_^ e^, x\rangle = \frac\sum_^ \sum_^ e^ e^, x\rangle = \frac\sum_^ \sum_^e^ , x\rangle.$

The state of both registers together is

:$\frac\sum_^ \sum_^ e^ , x\rangle \otimes , \psi\rangle.$

Phase approximation representation

We can approximate the value of $\theta \in$, 1/math> 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$.

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

:$\frac \sum_^ \sum_^ e^ e^ , 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_ \right \rangle \right , ^2 = \frac \left , \sum_^ e^ \right , ^2 = \begin1 & \delta = 0\\ & \\ \frac \left , \frac \^2 & \delta \neq 0 \end$

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. The state of the system after the measurement is $, 2^n \theta\rangle \otimes , \psi\rangle$.

For $\delta \neq 0$ since $, \delta, \leqslant \tfrac$ the algorithm yields the correct result with probability $\Pr(a) \geqslant \frac \approx 0.405$. We prove this as follows:

:\begin
\Pr(a) &= \frac \left , \frac \right , ^2 && \text \delta \neq 0 \\ pt&= \frac \left , \frac \right , ^2 && \left, 1-e^\^2 = 4\left, \sin (x)\^2 \\ pt&= \frac \frac \\ pt&\geqslant \frac \frac && , \sin(\pi \delta) , \leqslant , \pi \delta , \text , \delta, \leqslant \frac \\ pt&\geqslant \frac \frac && , 2\cdot2^n \delta , \leqslant , \sin(\pi 2^n\delta) , \text , \delta, \leqslant \frac \\ pt&\geqslant \frac
\end

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

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^$. The first part of the algorithm generates the one-qubit state $, \phi\rangle\equiv \frac(, 0\rangle+\lambda , 1\rangle)$. Applying the inverse QFT amounts in this case to applying a Pauli-X gate. The final outcome probabilities are thus $p_\pm = , \langle\pm, \phi\rangle, ^2$ where $, \pm\rangle\equiv\frac(, 0\rangle\pm, 1\rangle)$, or more explicitly,$p_\pm = \frac =\frac.$It is clear that in this simple example, if $\lambda=\pm1$, then $, \phi\rangle=, \pm\rangle$ and thus we deterministically recover the precise eigenvalue from the measurement outcome.

If on the other hand $\lambda=e^$, then p_\pm = \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

References

{{DEFAULTSORT:Quantum Phase Estimation Algorithm
Quantum algorithms