## Wednesday, 11 September 2013

### Phase Estimation

The utility of the quantum Fourier transform $QFT$ may not be immediately obvious. In this section, it will be shown that the $QFT$ can be applied to some state containing unknown relative phase factors in order to determine information about the phase.  Let $\omega=x/2^n$ for some positive integer $x<2^n$ so that $\omega=0.x_1x_2\dots x_n$, and suppose some state of the form
$\left|\psi\right>=\displaystyle\frac{1}{\sqrt{2^n}}\displaystyle\sum\limits_{j=0}^{2^n-1}e^{i2\pi \omega j}\left|j\right>=\displaystyle\frac{1}{\sqrt{2^n}}\displaystyle\sum\limits_{j=0}^{2^n-1}e^{\frac{i2\pi xj}{2^n}}\left|j\right>$
is provided. Since the action of the $QFT$ on the basis state $\left|x\right>=\left|x_1x_2\dots x_n\right>\in\mathcal{H}^{2^n}$ is
$QFT\left|x\right>=\displaystyle\frac{1}{\sqrt{2^n}}\displaystyle\sum\limits_{j=0}^{2^n-1}e^{\frac{i2\pi xj}{2^n}}\left|j\right>=\displaystyle\frac{1}{\sqrt{2^n}}\displaystyle\sum\limits_{j=0}^{2^n-1}e^{i2\pi \omega j}\left|j\right>=\left|\psi\right>,$
then the inverse $QFT^{-1}$ will map the state $\left|\psi\right>$ to the basis state $\left|x\right>$:
$QFT^{-1}\left|\psi\right>=QFT\left(\displaystyle\frac{1}{\sqrt{2^n}}\displaystyle\sum\limits_{j=0}^{2^n-1}e^{i2\pi \omega j}\left|j\right>\right) =\left|x\right>.$
If the value of $\omega=x/2^n$ in the relative phases of $\left|\psi\right>$ was unknown, then by simply applying the $QFT$ to $\left|\psi\right>$ and measuring yields the state $\left|x\right>$, which can then be used to determine $\omega$. This consequence motivates the phase estimation problem.

Phase Estimation Problem

Input: A state $\left|\psi\right>=\displaystyle \frac{1}{\sqrt{2^n}}\displaystyle\sum\limits_{j=0}^{2^n-1}e^{i2\pi \omega j}\left|j\right>\in\mathcal{H}^{2^n}$, where the phase parameter $\omega \in [0,1)\in\mathbb{R}$ is unknown.

Problem:  Determine an estimate for the unknown  phase parameter $\omega$.

The reason why an estimate the phase parameter $\omega$ is desired in the phase estimation problem is because $\omega$ may not be a rational number. In the case where $\omega$ is an irrational number, the binary expansion $\omega=x_1x_2x_3\dots$ is infinite. To determine $\omega$ exactly would then require infinitely many bits of information. On the other hand, if $\omega$ is a rational number then the binary expansion $\omega=x_1x_2\dots x_n$ will eventually terminate after $n$ digits. Even in this case the number of digits $n$ in the expansion can be an arbitrary large number. Therefore, an estimate $\tilde{\omega}=x_1x_2\dots x_k$ of $\omega$ might still be necessary. In the phase estimation problem, how close an estimate $\tilde{\omega}$ is to the parameter $\omega$ is determined by the number of qubits used to express the state $\left|\psi\right>$. The more qubits used, the closer the estimate will be to $\omega$.

As previously shown, if $\omega=x/2^n$ for some integer $x<2^n$, then the inverse quantum Fourier transform $QFT^{-1}$ can be used to determine $x$ exactly. To solve the phase estimation problem for general $\omega$,  some number of qubits $n$ is chosen in advance that will determine the degree of accuracy in the estimate. Then when $QFT^{-1}$ acting on $n$ qubits is applied to the provided state $\left|\psi \right>$, a state $\left|x\right>$ is produced such that $x/2^n=\tilde{\omega}$  yields an estimate of $\omega$. Therefore, the circuit that implements $QFT^{-1}$ can be used to solve the phase estimation problem, which is shown in the figure below. Recall that the inverse of the circuit implementing some unitary operator like $QFT$ is simply the same circuit with the order of the gates reversed, and  each gate is replaced with its inverse operation.

(The circuit for the phase estimation algorithm. This circuit is the $QFT^{-1}$ circuit, which takes as input some state state $\left|\psi\right>$ with a phase factor $\omega$, and transforms it to the basis state $\left|x\right>\in\mathcal{H}^{2^n}$ such that $x/2^n=\tilde{\omega}$ is an estimate for the phase $\omega$ up to $n$ bits of accuracy. The $QFT^{-1}$ circuit is equivalent to the circuit  that results from reversing the order of the gates in the $QFT$ circuit, shown here, and replacing each gate with its inverse.)\label{fig:qftinverse}
\end{figure}

Since it, was already argued that the $QFT$ can be implemented efficiently with a number of gates in $O(n^2)$, and the $QFT^{-1}$ requires the exact same number of gates, it follows that the size or time complexity of implementing the $QFT^{-1}$ is also in $O(n^2)$. Thus, the phase estimation algorithm just described is a quantum algorithm that solves the phase estimation problem in polynomial time, placing the problem into the complexity class $\mathbf{BQP}$. Moreover, it can be justified further that the phase estimation algorithm will output $x$ corresponding to the state $\left|x\right>$ such that $x/2^n=\tilde{\omega}$ is the closest estimate to $\omega$ with a probability greater than $4/\pi^2$.\cite{mosca} This estimate is optimal for a given number $n$ of qubits used. That is $\tilde{\omega}=x/2^n$ will be the closest multiple of $1/2^n$ to $\omega$.

The phase estimation algorithm is an example of a problem that a quantum computer can solve more efficiently than any known classical algorithm. Recall, that it takes $O(n2^n)$ steps to implement the classical discrete Fourier transform. Therefore any classical algorithm that were to solve the phase estimation problem using the Fourier transform would take exponentially longer. The quantum phase estimation algorithm  can be said to provide  a superpolynomial speed-up when compared to the classical context.