Quantum Phase Estimation

About

The phase estimation algorithm appears to be a very important subroutine in quantum computer computations. This algorithm is useful for measuring the eigenvalues of unitary matrices and is applied in algorithms such as HHL. When explaining this algorithm, it is often first described in terms of the Hadamard test. This is because phase estimation is understood as an extension of the Hadamard test.

Hamdard Test

The Hadamard test is a method for transferring the eigenvalues of a unitary matrix to an ancilla qubit through phase kickback. Since the information of the eigenvalues is transferred to a single ancilla qubit, multiple measurements are necessary to determine the eigenvalues with a certain degree of accuracy.

Quantum Phase Estimation

Quantum phase estimation can be considered an extension of the Hadamard test. Like the Hadamard test, it is a method for extracting eigenvalue information of a unitary matrix, but unlike the Hadamard test, it uses multiple ancilla bits. It is an algorithm that extracts the phase by decoding through the quantum inverse Fourier transform of these multiple ancilla bits.

0.j_l \cdots j_n = \frac{j_1}{2} + \frac{j_{2}}{2^2} + \cdots + \frac{j_n}{2^{n}}

Each of the n qubits, initialized to ( |0> ), is acted upon by a Hadamard gate and a controlled unitary operation, similar to the Hadamard test. However, for the k-th ancilla qubit (where ( k = 1, …, n )), we apply the controlled ( U^{2^{k-1}} ) operation. Since ( U|eigen> = e^{i2\pi\lambda}|eigen> ), the k -th ancilla qubit acquires a phase of ( e^{i\lambda 2^{k}} ) (this is called phase kickback), resulting in the state:

\bigg(\frac{|0\rangle + e^{i(2\pi)0.j_1\cdots j_n}|1\rangle}{\sqrt{2}}\bigg) \otimes \bigg(\frac{|0\rangle + e^{i(2\pi)0.j_2\cdots j_n}|1\rangle}{\sqrt{2}}\bigg) \otimes \cdots \otimes \bigg(\frac{|0\rangle + e^{i(2\pi)0.j_n}|1\rangle}{\sqrt{2}}\bigg) \otimes |eigen\rangle.

In other words, the phase of the eigenvalue expressed as a binary fraction is stored in the phase of each ancilla qubit, shifted by one bit.

Since the above expression has the same form as QFT (Quantum Fourier Transform), it can be decoded by performing the inverse quantum Fourier transform.

\left( \frac{|0\rangle + e^{i(2\pi)0.j_1\cdots j_n}|1\rangle}{\sqrt{2}} \right) \otimes \left( \frac{|0\rangle + e^{i(2\pi)0.j_2\cdots j_n}|1\rangle}{\sqrt{2}} \right) \otimes \cdots \otimes \left( \frac{|0\rangle + e^{i(2\pi)0.j_n}|1\rangle}{\sqrt{2}} \right) \rightarrow |j_1\ldots j_n\rangle

Reference

[1]https://dojo.qulacs.org/ja/latest/notebooks/2.3_quantum_Fourier_transform.html

[2]