Quantum phase estimation algorithm

Short description: Quantum algorithm for eigenvalue estimation

In quantum computing, the quantum phase estimation algorithm (also referred to as quantum eigenvalue estimation algorithm), is a quantum algorithm to estimate the phase (or eigenvalue) of an eigenvector of a unitary operator. More precisely, given a unitary matrix [math]\displaystyle{ U }[/math] and a quantum state [math]\displaystyle{ |\psi\rangle }[/math] such that [math]\displaystyle{ U|\psi\rangle=e^{2\pi i\theta}|\psi\rangle }[/math], the algorithm estimates the value of [math]\displaystyle{ \theta }[/math] with high probability within additive error [math]\displaystyle{ \varepsilon }[/math], using [math]\displaystyle{ O(\log(1/\varepsilon)) }[/math] qubits (without counting the ones used to encode the eigenvector state) and [math]\displaystyle{ O(1/\varepsilon) }[/math] controlled-U operations. The algorithm was initially introduced by Alexei Kitaev in 1995.

Phase estimation is frequently used as a subroutine in other quantum algorithms, such as Shor's algorithm and the quantum algorithm for linear systems of equations.

The problem

Let U be a unitary operator that operates on m qubits with an eigenvector[math]\displaystyle{ | \psi \rangle, }[/math] such that [math]\displaystyle{ U| \psi\rangle = e^{ 2\pi i \theta}\left|\psi \right\rangle , 0 \leq \theta \lt 1 }[/math].

We would like to find the eigenvalue [math]\displaystyle{ e^{2 \pi i \theta} }[/math]of [math]\displaystyle{ |\psi\rangle }[/math], which in this case is equivalent to estimating the phase [math]\displaystyle{ \theta }[/math], to a finite level of precision. We can write the eigenvalue in the form [math]\displaystyle{ e^{2 \pi i \theta} }[/math] because U is a unitary operator over a complex vector space, so its eigenvalues must be complex numbers with absolute value 1.

The algorithm

Quantum phase estimation circuit

Setup

The input consists of two registers (namely, two parts): the upper [math]\displaystyle{ n }[/math] qubits comprise the first register, and the lower [math]\displaystyle{ m }[/math] qubits are the second register.

Create superposition

The initial state of the system is:

[math]\displaystyle{ |0\rangle^{\otimes n}|\psi\rangle . }[/math]

After applying n-bit Hadamard gate operation [math]\displaystyle{ H^{\otimes n} }[/math] on the first register, the state becomes:

[math]\displaystyle{ \frac{1}{2^{\frac{n}{2}}}(|0\rangle + |1\rangle)^{\otimes n}|\psi\rangle }[/math].

Apply controlled unitary operations

Let [math]\displaystyle{ U }[/math] be a unitary operator with eigenvector [math]\displaystyle{ |\psi\rangle }[/math] such that [math]\displaystyle{ U| \psi \rangle = e^{ 2\pi i \theta}|\psi \rangle, }[/math] thus by exponentiation by squaring,

[math]\displaystyle{ U^{2^{j}}| \psi\rangle = U^{2^{j-1}} U^{2^{j-1}} |\psi\rangle = U^{2^{j -1}} e^{ 2\pi i 2^{j-1} \theta}|\psi \rangle = e^{ 2\pi i 2^{j}\theta}|\psi \rangle }[/math].

[math]\displaystyle{ C-U }[/math] is a controlled-U gate which applies the unitary operator [math]\displaystyle{ U }[/math] on the second register only if its corresponding control bit (from the first register) is [math]\displaystyle{ |1\rangle }[/math].

Assuming for the sake of clarity that the controlled gates are applied sequentially, after applying [math]\displaystyle{ C-U^{2^{0}} }[/math]to the [math]\displaystyle{ n^{th} }[/math] qubit of the first register and the second register, the state becomes

[math]\displaystyle{ \frac{1}{2^{\frac{1}{2}}} \underbrace{ \left (|0\rangle|\psi \rangle + |1\rangle e^{2\pi i 2^{0} \theta}|\psi\rangle \right )}_ {n^{th} \ qubit \ and \ second \ register} \otimes \frac{1}{2^{\frac{n-1}{2}}} \underbrace{ \left (|0\rangle + |1\rangle \right )^{\otimes^{n-1}}} _{qubits \ 1^{st} \ to \ n-1^{th}} = \frac{1}{2^{\frac{1}{2}}} \left (|0\rangle|\psi \rangle + e^{2\pi i 2^{0} \theta} |1\rangle |\psi\rangle \right ) \otimes \frac{1}{2^{\frac{n-1}{2}}} \left (|0\rangle + |1\rangle \right )^{\otimes^{n-1}} }[/math][math]\displaystyle{ = \frac{1}{2^{\frac{1}{2}}} \left (|0\rangle + e^{2\pi i 2^{0} \theta} |1\rangle \right ) |\psi\rangle \otimes \frac{1}{2^{\frac{n-1}{2}}} \left (|0\rangle + |1\rangle \right )^{\otimes^{n-1}} = \frac{1}{2^{\frac{n}{2}}} \underbrace{ \left (|0\rangle + e^{2\pi i 2^{0} \theta} |1\rangle \right )} _{n^{th} \ qubit} \otimes \left (|0\rangle + |1\rangle \right )^{\otimes^{n-1}} |\psi\rangle , }[/math]

where we use:

[math]\displaystyle{ |0\rangle |\psi\rangle + |1\rangle \otimes e^{2\pi i 2^{j} \theta} |\psi\rangle =(|0\rangle + e^{2\pi i 2^{j} \theta} |1\rangle) |\psi\rangle, \ \forall j . }[/math]

After applying all the remaining [math]\displaystyle{ n-1 }[/math] controlled operations [math]\displaystyle{ C-U^{2^{j}} }[/math] with [math]\displaystyle{ 1 \leq j \leq n-1, }[/math] as seen in the figure, the state of the first register can be described as

[math]\displaystyle{ \frac{1}{2^{\frac{n}{2}}} \underbrace{ \left (|0\rangle + e^{2\pi i 2^{n-1} \theta}|1\rangle \right )}_{1^{st} \ qubit} \otimes \cdots \otimes \underbrace{\left (|0\rangle + e^{2\pi i 2^1 \theta}|1\rangle \right )}_{n-1^{th} \ qubit} \otimes\underbrace{\left (|0\rangle + e^{2\pi i 2^{0} \theta}|1\rangle \right )}_{n^{th} \ qubit} = \frac{1}{2^{\frac{n}{2}}}\sum_{k=0}^{2^n -1} e^{2\pi i \theta k} |k\rangle, }[/math]

where [math]\displaystyle{ |k\rangle }[/math] denotes the binary representation of [math]\displaystyle{ k }[/math], i.e. it's the [math]\displaystyle{ k^{th} }[/math] computational basis, and the state of the second register is left physically unchanged at [math]\displaystyle{ |\psi \rangle }[/math].

Apply inverse quantum Fourier transform

Applying inverse quantum Fourier transform on

[math]\displaystyle{ \frac{1}{2^{\frac{n}{2}}}\sum_{k=0}^{2^n - 1} e^{2\pi i \theta k} |k\rangle }[/math]

yields

[math]\displaystyle{ \frac{1}{2^{\frac{n}{2}}}\sum_{k=0}^{2^n - 1} e^{2\pi i \theta k} \frac{1}{2^{\frac{n}{2}}}\sum_{x=0}^{2^n - 1} e^{\frac{-2\pi i kx}{2^n}}|x\rangle = \frac{1}{2^{n}}\sum_{x=0}^{2^n - 1} \sum_{k=0}^{2^n - 1} e^{2\pi i \theta k} e^{\frac{-2\pi i kx}{2^n}}|x\rangle = \frac{1}{2^{n}}\sum_{x=0}^{2^n - 1} \sum_{k=0}^{2^n - 1}e^{-\frac{2\pi i k}{2^n} \left ( x - 2^n \theta \right )} |x\rangle. }[/math]

The state of both registers together is

[math]\displaystyle{ \frac{1}{2^{n}}\sum_{x=0}^{2^n - 1} \sum_{k=0}^{2^n - 1} e^{-\frac{2\pi i k}{2^n} \left ( x - 2^n \theta \right )} |x\rangle \otimes |\psi\rangle. }[/math]

Phase approximation representation

We can approximate the value of [math]\displaystyle{ \theta \in [0, 1] }[/math] by rounding [math]\displaystyle{ 2^n \theta }[/math] to the nearest integer. This means that [math]\displaystyle{ 2^n \theta = a + 2^n \delta, }[/math] where [math]\displaystyle{ a }[/math] is the nearest integer to [math]\displaystyle{ 2^n \theta, }[/math] and the difference [math]\displaystyle{ 2^n\delta }[/math] satisfies [math]\displaystyle{ 0 \leqslant |2^n\delta| \leqslant \tfrac{1}{2} }[/math].

We can now write the state of the first and second register in the following way:

[math]\displaystyle{ \frac{1}{2^{n}} \sum_{x=0}^{2^n - 1} \sum_{k=0}^{2^n - 1} e^{-\frac{2\pi i k}{2^n} \left ( x-a \right )} e^{2 \pi i \delta k} |x\rangle \otimes |\psi\rangle. }[/math]

Measurement

Performing a measurement in the computational basis on the first register yields the result [math]\displaystyle{ |a\rangle }[/math] with probability

[math]\displaystyle{ \Pr(a) = \left | \left \langle a \underbrace{ \left | \frac{1}{2^{n}} \sum_{x=0}^{2^n-1} \sum_{k=0}^{2^n-1} e^{\frac{-2\pi i k}{2^n}(x-a)} e^{2 \pi i \delta k} \right | x }_{\text{State of the first register}} \right \rangle \right |^2 = \frac{1}{2^{2n}} \left | \sum_{k=0}^{2^n-1} e^{2 \pi i \delta k} \right |^2 = \begin{cases}1 & \delta = 0\\ & \\ \frac{1}{2^{2n}} \left | \frac{1- {e^{2 \pi i 2^n \delta}}}{1-{e^{2 \pi i \delta}}} \right|^2 & \delta \neq 0 \end{cases} }[/math]

For [math]\displaystyle{ \delta = 0 }[/math] the approximation is precise, thus [math]\displaystyle{ a = 2^n \theta }[/math] and [math]\displaystyle{ \Pr(a) = 1. }[/math] In this case, we always measure the accurate value of the phase. The state of the system after the measurement is [math]\displaystyle{ |2^n \theta\rangle \otimes |\psi\rangle }[/math].

For [math]\displaystyle{ \delta \neq 0 }[/math] since [math]\displaystyle{ |\delta| \leqslant \tfrac{1}{2^{n+1}} }[/math] the algorithm yields the correct result with probability [math]\displaystyle{ \Pr(a) \geqslant \frac{4}{\pi^2} \approx 0.405 }[/math]. We prove this as follows:

[math]\displaystyle{ \begin{align} \Pr(a) &= \frac{1}{2^{2n}} \left | \frac{1- {e^{2 \pi i 2^n \delta}}}{1-{e^{2 \pi i \delta}}} \right |^2 && \text{for } \delta \neq 0 \\ [6pt] &= \frac{1}{2^{2n}} \left | \frac{2 \sin \left ( \pi 2^n \delta\right)}{ 2\sin( \pi \delta)} \right |^2 && \left| 1-e^{2ix}\right|^2 = 4\left| \sin (x)\right|^2 \\ [6pt] &= \frac{1}{2^{2n}} \frac {\left | \sin\left(\pi 2^n \delta\right) \right |^2}{| \sin( \pi \delta) |^2} \\ [6pt] &\geqslant \frac{1}{2^{2n}} \frac {\left | \sin\left(\pi 2^n \delta\right) \right |^2}{| \pi \delta |^2} && | \sin(\pi \delta) | \leqslant | \pi \delta | \text{ for } |\delta| \leqslant \frac{1}{2^{n+1}} \\ [6pt] &\geqslant \frac{1}{2^{2n}} \frac {|2 \cdot 2^n \delta|^2}{| \pi \delta |^2} && | 2\cdot2^n \delta | \leqslant | \sin(\pi 2^n\delta) | \text{ for } |\delta| \leqslant \frac{1}{2^{n+1}} \\ [6pt] &\geqslant \frac {4}{\pi^2} \end{align} }[/math]

This result shows that we will measure the best n-bit estimate of [math]\displaystyle{ \theta }[/math] with high probability. By increasing the number of qubits by [math]\displaystyle{ O(\log(1/\epsilon)) }[/math] and ignoring those last qubits we can increase the probability to [math]\displaystyle{ 1 - \epsilon }[/math].

Examples

Consider the simplest possible instance of the algorithm, where only [math]\displaystyle{ n=1 }[/math] qubit, on top of the qubits required to encode [math]\displaystyle{ |\psi\rangle }[/math], is involved. Suppose the eigenvalue of [math]\displaystyle{ |\psi\rangle }[/math] reads [math]\displaystyle{ \lambda=e^{2\pi i \theta} }[/math]. The first part of the algorithm generates the one-qubit state [math]\displaystyle{ |\phi\rangle\equiv \frac{1}{\sqrt2}(|0\rangle+\lambda |1\rangle) }[/math]. Applying the inverse QFT amounts in this case to applying a Pauli-X gate. The final outcome probabilities are thus [math]\displaystyle{ p_\pm = |\langle\pm|\phi\rangle|^2 }[/math] where [math]\displaystyle{ |\pm\rangle\equiv\frac{1}{\sqrt2}(|0\rangle\pm|1\rangle) }[/math], or more explicitly,[math]\displaystyle{ p_\pm = \frac{|1\pm\lambda|^2}{4} =\frac{1 \pm \cos(2\pi \theta)}{2}. }[/math]It is clear that in this simple example, if [math]\displaystyle{ \lambda=\pm1 }[/math], then [math]\displaystyle{ |\phi\rangle=|\pm\rangle }[/math] and thus we deterministically recover the precise eigenvalue from the measurement outcome.

If on the other hand [math]\displaystyle{ \lambda=e^{2\pi i/3} }[/math], then [math]\displaystyle{ p_\pm = [1 \pm \cos(2\pi/3)]/2 }[/math], that is, [math]\displaystyle{ p_+=1/4 }[/math] and [math]\displaystyle{ p_-=3/4 }[/math]. This is compatible with our general discussion because [math]\displaystyle{ 2^1 \theta=2/3 }[/math].

See also

• Shor's algorithm
• Quantum counting algorithm
• Parity measurement