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