Quantum phase estimation

Quantum phase estimation is one of the most important subroutines in quantum computation. It serves as a central building block for many quantum algorithms and implements a measurement for essentially any Hermitian operator. Recall that a quantum computer initially only permits us to measure individual qubits. If we want to measure a more complex observable, such as the energy described by a Hamiltonian H , we resort to quantum phase estimation. The routine prepares an eigenstate of the Hermitian operator in one register and stores the corresponding eigenvalue in a second register.

John von Neumann’s measurement scheme

Quantum phase estimation is a discretization of von Neumann’s prescription to measure a Hermitian observable H = \sum_j E_j|\psi_j \rangle \langle \psi_j| . The scheme that von Neumann envisioned is the following. We consider a quantum system that supports the observable H , which we want to measure. We assume that we are only able to measure simpler observables, in our case single qubits, or as in the original setting, the location of a single particle. It is therefore our goal to reduce the measurement of the complex observable H to a measurement of the simpler observable, such as the location. This simple observable is then referred to as the pointer. To map the complex observable onto the simpler one, we’ll make use of a convenient observation from quantum mechanics. It is known that the momentum operator \hat{p} generates shifts in position for single particles.

image0

That is, if we apply the unitary \exp(- i \hat{p} \lambda) to some wave packet \psi(x) , then this wave packet will be shifted by \lambda in the positive direction.

The scheme now assumes that we can apply the unitary evolution \exp(-i H \otimes \hat{p} t ) to both the system and the pointer register, as illustrated in the following image:

image1

This image describes von Neumann’s measurement scheme. We now follow the steps and first adjoin an auxiliary qubit – the pointer – which is a continuous quantum variable initialized in the state |0\rangle (the origin), so that the system + pointer is initialized in the state |\psi\rangle|0\rangle , where |\psi\rangle is the initial state of the system. Then we evolve according to the new Hamiltonian K = H\otimes\hat{p} for a time t , so the evolution is given by e^{-it H\otimes \hat{p}} = \sum_{j=1}^{2^N} |\psi_{j}\rangle\langle \psi_{j}|\otimes e^{-itE_j \hat{p}}.

We now observe the action of this measurement apparatus. Supposing that |\psi\rangle is an eigenstate |\psi_{j}\rangle of H , we find that the system evolves to e^{-it H\otimes \hat{p}}|\psi_{j}\rangle|0\rangle = |\psi_{j}\rangle |x = tE_j\rangle. A measurement of the position of the pointer with sufficiently high accuracy will provide an approximation to E_j .

The quantum algorithm

To carry out the above operation efficiently on a quantum computer, we discretize the pointer using r qubits, replacing the continuous quantum variable with a 2^r -dimensional space, where the computational basis states |z\rangle of the pointer represent the basis of momentum eigenstates of the original continuous quantum variable. The label z is the binary representation of the integers 0 through 2^r-1 . In this representation, the discretization of the momentum operator becomes \hat{p} = \sum_{j=1}^r 2^{-j}\frac{\mathbb{I}-\sigma^z_j}{2}. With this normalization, \hat{p}|z\rangle =\frac{z}{2^r}|z\rangle .

Now the discretized Hamiltonian K = H\otimes \hat{p} is a sum of terms involving at most k+1 qubits, if H is a Hamiltonian involving terms of at most k qubits. We can thus simulate the dynamics of K using standard methods. In terms of the momentum eigenbasis, the initial (discretized) state of the pointer is written | x=0\rangle = \frac{1}{2^{r/2}}\sum_{z=0}^{2^r-1} |z\rangle . This state can be prepared efficiently on a quantum computer by first initializing the qubits of the pointer in the state |0\rangle \cdots|0\rangle and applying an (inverse) quantum Fourier transform. Since we have a very simple initial state, the Fourier transform can be represented by a product of Hadamard matrices. The discretized evolution of the system + pointer now can be written e^{-it  H\otimes \hat{p}}|\psi_{j}\rangle|x=0\rangle = \frac{1}{2^{r/2}}\sum_{z=0}^{2^r-1} e^{-iE_j zt/2^r}|\psi_{j}\rangle z\rangle.

Performing an inverse quantum Fourier transform on the pointer leaves the system in the state |\psi_{j}\rangle\otimes|\phi\rangle , where | \phi\rangle  = \sum_{x=0}^{2^r-1} \left(\frac{1}{2^{r}}\sum_{z=0}^{2^r-1}e^{\frac{2\pi i}{2^r}\left(x-\frac{E_j t}{2\pi}\right)z} \right)|x\rangle, which is strongly peaked near the location x = \lfloor\frac{E_jt}{2\pi} \rfloor . To ensure that there are no overflow errors, we need to choose t < \frac{2\pi}{\|H\|} . (We assume here, for simplicity, that H\geq 0 .) It is easy to see that actually performing the simulation of K for t=1 is a product of r simulations of the evolution according to \frac{1}{2^{r}} H\otimes \frac{\mathbb{I}-\sigma^z_k}{2} for 1, 2, 2^2, \ldots, 2^{r-1} units of time. This results in the general circuit for quantum phase estimation:

image2

In order to implement the full circuit on a quantum computer, we still need to decompose the controlled unitaries e^{-i H  \frac{t}{2^k}}, as well as the inverse quantum Fourier transform denoted by QFT^{-1}, into our elementary gates.

Example circuit

The example below demonstrates quantum phase estimation for a toy single-qubit Hamiltonian \sigma^x acting on qubit Q_0 . Qubit Q_1 serves as a pointer system. In this example, the quantum Fourier transform on the pointer system is equivalent to the Hadamard gate H on Q_1 . The discretized evolution of the system + pointer system is described by the CNOT gate. The final measurement outcome on the pointer qubit Q_1 is 0 or 1 depending on whether Q_0 is prepared in the +1 or -1 eigenstate of \sigma^x .

Phase Estimation Circuit (+)

Here, qubit Q_0 is initialized in a state H|0\rangle , which is the +1 eigenvector of \sigma^x. Accordingly, the measurement outcome for Q_1 is 0 .

image3

Open in IBM Quantum Composer

Phase Estimation Circuit (-)

In this example, qubit Q_0 is initialized with Z H|0\rangle , giving the -1 eigenvector of \sigma^x. The measurement outcome for Q_1 is therefore 1 .

image4

Open in IBM Quantum Composer

Previous: Deutsch-Jozsa algorithm Next: Shor’s algorithm