Quantum Phase Estimation

Algorithm Overview

Quantum Phase Estimation is a quantum circuit that solves the phase estimation problem in a quantum circuit.

QPE can be used to find the spectral decomposition of a unitary matrix, encoding its eigenvalues into binary format.

Phase estimation problem

We are given, as input, a description of a unitary quantum operation that operates on qubits, and an -qubit quantum state . We are promised that is an eigenvector of .

The output is an approximation of satisfying . That is, is an eigenvalue of corresponding to the eigenvector .

Circuit Explanation and Proof

In the following, consider an unitary matrix .

Spectral theorem

By the Spectral theorem, which applies to all normal matrices (a superset of unitary matrices), can be represented by its eigenvalues and eigenvectors:

where are eigenvectors of , with corresponding eigenvalues .

Additionally, all eigenvalues are complex numbers with magnitude 1:

where .

can be approximated by a fraction:

where and is a positive integer.

Phase kickback

Phase kickback is the primary mechanism making QPE work, allowing some information about to be encoded into the state of a control qubit. [1] [2]

Consider a circuit with a controlled-unitary operation, , where a Hadamard gate is first applied to the control qubit, then the controlled-unitary operation is applied, then another Hadamard gate is applied to the control qubit before it is measured.

Additionally, the input state of all the qubits except for the control qubit is an eigenvector, , of .

[Future: Insert Phase kickback circuit]

The initial state of the circuit is:

After the first Hadamard gate, the state becomes:

After the controlled-U operation is performed, the state becomes:

Since we know that is an eigenvector of with eigenvalue , we can express as:

After the second Hadamard gate is performed, the final state is:

In the case of phase kickback, the control qubit is the only qubit whose state is changed — the eigenvector register remains unchanged. This means that the eigenvector state can be reused.

If the control qubit is measured, the probability of each outcome is as follows:

Hence, by measuring this control qubit, we gain some information about the value of without changing the state of the qubits in the state register.

If we apply the controlled gate twice, the probabilities become and .

Repeating it four times changes the coefficient of to , and so on.

Hence, by using multiple () instances of phase kickback, a binary approximation of can be found.

Looking at the central section of the QPE circuit, you can see how phase kickback is performed with different numbers of controlled operations.

Quantum Fourier Transform

Finally, the inverse QFT is performed on the clock register to convert the frequency information about into the amplitudes of the clock qubits, allowing the binary representation of to be measured.

Literature

Use Cases

Quantum Phase Estimation is used as a subcircuit in Shor's Algorithm, the Harrow-Hassidim-Lloyd algorithm, and others.

Extra Information

Initialising the state register to an arbitrary vector

Theoretical problems

Implementation problems