## Wednesday, 11 September 2013

### Eigenvalue Estimation

This section will combine the technique deployed in the phase kick-back algorithms, and the method of phase estimation to solve a problem of a similar nature. Here, the objective will be to determine the eigenvalue of the form $e^{i2\pi\omega}$ of a eigenvector $\left|\phi\right>$ associated to a particular unitary operator $U$. In the eigenvalue estimation problem, the details of the unitary operator $U$ and eigenvector $\left|\phi\right>$ are unknown and not of main concern. It is assumed that such a state is already provided as well as the means to operate on the state with a circuit that implements $U$.

Eigenvalue Estimation Problem

Input: A quantum circuit implementing a unitary operator $U$ with an eigenvector $\left|\phi\right>$ and associated eigenvalue $e^{i2\pi\omega}$.

Problem: Determine an estimate for the unknown parameter $\omega$ which determines the eigenvalue.

Since $\left|\phi\right>$ is an eigenvector of $U$ with eigenvalue $e^{i2\pi\omega}$, then by definition $U\left|\phi\right>=e^{i2\pi\omega}\left|\phi\right>$. Define a controlled$-U$ operation, $c-U$ where a single qubit is used as the control register.  Then if the target register is prepared in the state $\left|\phi\right>$, the action of $c-U$ is given by
$\begin{array}{r l} c-U\left|0\right>\left|\phi\right>=&\left|0\right>\left|\phi\right>, \\ c-U\left|1\right>\left|\phi\right>=&e^{i2\pi\omega}\left|1\right>\left|\phi\right>. \end{array}.$
Thus, the phase factor $e^{i2\pi\omega}$ can be associating to the control qubit as in the phase kick-back algorithms. Now, denote the action of applying $c-U$ $m$ times as $c-U^m$, and observe that $c-U^m$ acts as follows
$\begin{array}{r l} c-U^m\left|0\right>\left|\phi\right>=&\left|0\right>\left|\phi\right>, \\ c-U^m\left|1\right>\left|\phi\right>=&e^{i2\pi\omega m}\left|1\right>\left|\phi\right>. \end{array}.$
This follows straight from the definition $\left|\psi\right>$ being an eigenvector of $U$ with eigenvalue $e^{i2\pi\omega}$, and since a product of exponentials is equivalent to a single exponential whose argument is the sum of the arguments of the exponentials.

The ability to perform the action of $c-U^m$ for various values of $m$ is helpful in solving the eigenvalue estimation problem, because this will allow the value of $\omega$ to be encoded into the relative phases of states. If the 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>,$
can be prepared, then as done in the phase estimation algorithms the value of $\omega$ can be estimated by applying the $QFT^{-1}$ to the state $\left|\psi\right>$. However, since the value of $\omega$ is unknown this state cannot be prepared directly. Fortunately, the ability to perform $c-U^m$ operations on the state $\left|\phi\right>$, which is given, can be used to construct the state $\left|\psi\right>$. Therefore, once this state $\left|\psi\right>$ has been constructed and the phase estimation algorithm is performed by making use of $QFT^{-1}$, information about $\omega$ will be obtained enabling an estimate of the eigenvalue.

A circuit can be constructed using $c-U^m$ gates that takes some basis state, say $\left|\mathbf{0}\right>\in\mathcal{H}^{2^n}$, and produces the state
$\begin{array}{r l} \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> \\ = &\left( \displaystyle\frac{\left|0\right>+e^{i2\pi \omega2^{n-1}}\left|1\right>}{\sqrt{2}}\right)\otimes\left( \displaystyle\frac{\left|0\right>+e^{i2\pi \omega2^{n-2}}\left|1\right>}{\sqrt{2}}\right)\otimes\dots\otimes\left( \displaystyle\frac{\left|0\right>+e^{i2\pi \omega2^{0}}\left|1\right>}{\sqrt{2}}\right) \\ =&\left|\psi_1\right>\otimes\left|\psi_2\right>\otimes\dots\otimes\left|\psi_n\right>. \end{array}.$
To accomplish this, first observe the action of $c-U^m$ on a qubit in an equally weighted superposition in the control register, and the eigenstate $\left|\phi\right>$ in the target register
$c-U^m\left(\displaystyle\frac{\left|0\right>+\left|1\right>}{\sqrt{2}}\right)\left|\phi\right>=\left(\displaystyle\frac{\left|0\right>+e^{i2\pi\omega m}\left|1\right>}{\sqrt{2}}\right)\left|\phi\right>.$
Then by setting $m=2^n-k$ for integers $1\leq n\leq n$, it follows that
$c-U^{2^{n-k}}\left(\displaystyle\frac{\left|0\right>+\left|1\right>}{\sqrt{2}}\right)\left|\phi\right>=\left(\displaystyle\frac{\left|0\right>+e^{i2\pi\omega 2^{n-k}}\left|1\right>}{\sqrt{2}}\right)\left|\phi\right>=\left|\psi_k\right>,$
which is the state of the $k^{th}$ qubit in the register of the state $\left|\psi\right>$.

Therefore, first take a control register in the basis state $\left|\mathbf{0}\right>\in\mathcal{H}^{2^n}$ and apply the Hadamard gate to each qubit putting putting the register in an equally weighted superposition
$H^{\otimes n}\left|\mathbf{0}\right>=\displaystyle\bigotimes\limits_{k=1}^{n}\left(\displaystyle\frac{\left|0\right>+\left|1\right>}{\sqrt{2}}\right).$ Then by applying a $c-U^{2^{n-k}}$ multiple times, for $1\leq k\leq n$, each time controlled by the $k^{th}$ qubit in the control register the state $\left|\psi\right>$ is produced:
$\displaystyle\bigotimes\limits_{k=1}^{n}\left[\left(\displaystyle\frac{\left|0\right>+\left|1\right>}{\sqrt{2}}\right)\left|\phi\right>\right]=\displaystyle\bigotimes\limits_{k=1}^{n}\left|\psi_k\right>\left|\phi\right>=\left|\psi\right>.$

(The circuit on the left implements the series of $c-U^{2^{n-k}}$ gates controlled by the $n$ qubits in the control register, where each is in the superposition $\frac{1}{\sqrt{2}}\left(\left|0\right>+\left|1\right>\right)$ and the target register in the eigenstate $\left|\phi\right>$, producing the state $\left|\psi\right>$ as output in the control register. The controlled gate labelled by $U^x$ in the circuit shown below is the shorthand symbol that represents the circuit above.)

Before giving a complete construction of a circuit that solves the eigenvalue estimation problem, consider the circuit shown that represents just the sequence of $c-U^m$ gates acting on the states described above. As a notational convenience, this entire circuit will be represented in shorthand by the controlled$-U^x$ gate also shown above. Then the output $\left|\psi\right>$ provided in the control register after the controlled$-U^x$ is applied to $H^{\otimes n}\left|\mathbf{0}\right>\left|\phi\right>$ can be used as the input to the phase estimation algorithm. This is done by applying $QFT^{-1}$ to the control register, which produces some state $\left|x\right>$ such that $x/2^m=\tilde{\omega}$ is an estimate of the phase parameter  $\omega$ in the state $\left|\psi\right>$. This estimate can then be used to determine an estimate $e^{i2\pi\tilde{\omega}}$ of the eigenvalue. The circuit solving the eigenvalue estimation problem is shown in the figure below. Notice that the first gate is given by a $QFT$ acting on the control register, since this gate's action is equivalent to the action of $H^{\otimes n}$ on a control register where every qubit is in the state $\left|0\right>$. By doing this, a certain symmetry in the circuit and algorithm is highlighted that is similar to many of the previously introduced algorithms. In this case, it is seen that the $QFT$ plays an analogous role of the Hadamard gate $H^{\otimes n}$ in its use to encode and decode information after some controlled gate is applied.

(A circuit for the eigenvalue estimation algorithm. The $n$ qubit control register begins in the state $\left|\mathbf{0}\right>$ and the target register in the eigenstate $\left|\phi\right>$. First, the $QFT$ is applied to the control register, followed by the controlled$-U^x$ gate, and then the $QFT^{-1}$ is applied to the control register. This produces some basis state $\left|x\right>$ in the control register, which can then be used to estimate the eigenvalue through the phase parameter $\tilde{\omega}=x/2^n$.)

Since the $QFT$ and $QFT^{-1}$ can be implemented efficiently on a quantum computer, then provided with an eigenstate $\left|\phi\right>$ and an efficient means to implement the controlled$-U^x$, the eigenvalue estimation algorithm can solve the problem of estimating an eigenvalue efficiently.  The eigenvalue estimation problem is of a very general nature. After all, every unitary operator  acting on qubits has at least two eigenvalue/eigenvector pairs. Although this problem may still seem  of a somewhat contrived variety, the next section will reveal a remarkable application of the eigenvalue estimation algorithm to the problem of factoring integers efficiently.