Estimation

Quantum Phase Estimation

Estimating eigenvalues of unitary operators with quantum precision

Quantum Phase Estimation (QPE) is a fundamental quantum algorithm that determines the eigenvalue phase of a unitary operator given access to one of its eigenvectors. It serves as a critical subroutine in quantum counting, the HHL algorithm for linear systems, and quantum chemistry simulations where molecular energy levels must be computed. By combining controlled unitary operations with the inverse Quantum Fourier Transform, QPE achieves an exponential advantage in precision over any classical sampling-based approach.

Problem Statement and Theory

Consider a unitary operator U with an eigenvector |ψ⟩ satisfying U|ψ⟩ = e^{2πiφ}|ψ⟩, where φ ∈ [0, 1) is the unknown phase we wish to estimate. In quantum mechanics, eigenvalues of unitary operators are complex numbers of unit modulus, so they can always be written in this exponential form. The goal of QPE is to determine φ to t bits of precision, meaning we want an estimate φ̃ such that |φ - φ̃| < 2^{-t}.

Classically, if we can only apply U and measure in the computational basis, estimating φ requires exponentially many samples because each measurement provides only a single random bit of information. The quantum approach encodes the phase into the amplitudes of an auxiliary register through repeated controlled applications of U, then uses the inverse QFT to convert these amplitudes into a computational basis state that directly reveals the binary digits of φ.

\hat{U}|\psi\rangle = e^{2\pi i \varphi} |\psi\rangle

Eigenvalue equation

\frac{1}{\sqrt{2^t}} \sum_{k=0}^{2^t-1} e^{2\pi i \varphi k} |k\rangle \otimes |\psi\rangle

Phase encoding

P\left(|\tilde{\varphi} - \varphi| < \frac{1}{2^t}\right) > \frac{4}{\pi^2}

Precision bound

•Eigenvalue Problem: Given U and its eigenvector |ψ⟩, find φ such that U|ψ⟩ = e^{2πiφ}|ψ⟩.
•Precision Scaling: Using t counting qubits, QPE estimates φ to t bits of precision with high probability.
•Success Probability: Without extra ancilla qubits, the success probability exceeds 4/π² ≈ 40.5%. With one additional qubit, it exceeds 81%.
•Query Complexity: QPE requires O(2^t) controlled applications of U, or equivalently O(1/ε) queries for precision ε.

The QPE Circuit

The QPE algorithm uses two quantum registers: a counting register of t qubits initialized to |0⟩^⊗t, and an eigenstate register initialized to the eigenvector |ψ⟩. The circuit proceeds in three stages. First, Hadamard gates are applied to the counting register to create a uniform superposition over all 2^t basis states. Second, controlled-U^{2^k} operations are applied for k = 0, 1, ..., t-1, with the k-th counting qubit controlling U raised to the power 2^k.

These controlled operations encode the phase into the amplitudes of the counting register. Specifically, the state becomes (1/sqrt(2^t)) * sum_{k=0}^{2^t-1} e^{2πiφk} |k⟩ ⊗ |ψ⟩. In the third stage, the inverse QFT is applied to the counting register, transforming this phase-encoded superposition into a state that peaks around the binary representation of φ. Measuring the counting register then yields an estimate of φ with high probability.

|\psi_1\rangle = \frac{1}{\sqrt{2^t}} \sum_{k=0}^{2^t-1} |k\rangle \otimes |\psi\rangle

After Hadamards

|\psi_2\rangle = \frac{1}{\sqrt{2^t}} \sum_{k=0}^{2^t-1} e^{2\pi i \varphi k} |k\rangle \otimes |\psi\rangle

After controlled-U

|\psi_3\rangle = \sum_{j=0}^{2^t-1} \alpha_j |j\rangle \otimes |\psi\rangle, \quad \alpha_j \approx \delta_{j, \lfloor 2^t \varphi \rfloor}

After inverse QFT

•Register Initialization: The counting register starts in |0⟩^⊗t and the eigenstate register holds |ψ⟩.
•Controlled Unitaries: Each counting qubit k controls U^{2^k}, encoding progressively higher bits of the phase into amplitudes.
•Inverse QFT: The inverse QFT converts the phase-encoded amplitudes into a computational basis state |2^t φ⟩.
•Measurement: Measuring the counting register yields an integer j; the phase estimate is φ̃ = j / 2^t.

Error Analysis and Resources

The probability of obtaining the best t-bit approximation to φ is bounded below by 4/π² when using exactly t counting qubits. This constant probability may seem low, but it can be boosted arbitrarily close to 1 by adding extra qubits to the counting register. Specifically, using t + s qubits yields a success probability of at least 1 - 1/(2^{2s} - 2). For example, with s = 2 extra qubits, the success probability exceeds 95%. Alternatively, one can repeat the algorithm a constant number of times and take the majority outcome.

The gate complexity of QPE is dominated by the controlled unitary operations. If U can be implemented with G gates, then controlled-U^{2^k} requires O(2^k G) gates in the worst case. Summing over k = 0 to t-1 gives a total gate count of O(2^t G) for the controlled-unitary stage, plus O(t²) gates for the inverse QFT. In terms of precision ε = 2^{-t}, the complexity is O(G/ε), which is exponentially better than classical Monte Carlo methods that require O(1/ε²) samples.

P\left(|\tilde{\varphi} - \varphi| < \frac{1}{2^t}\right) \geq 1 - \frac{1}{2^{2s} - 2}

Success probability with extra qubits

•Boosting Probability: Adding s extra counting qubits drives the success probability above 1 - 1/(2^{2s} - 2).
•Phase Approximation: When φ is not exactly representable with t bits, the output distribution peaks near the two closest t-bit approximations.
•Amplitude Amplification: Grover-like amplitude amplification can boost the probability of the correct phase estimate quadratically.
•Coherence Requirements: The algorithm requires coherent execution of O(2^t) controlled-U operations, demanding long coherence times on physical hardware.

Code in Action

Runnable implementations you can copy and experiment with.

Quantum Phase Estimation with Qiskit

A 3-qubit QPE circuit estimating the phase of a phase gate with φ = 1/4, which should yield the measurement |010⟩.

qpe_qiskit.py

from qiskit import QuantumCircuit
from qiskit.circuit.library import QFT
import numpy as np

n_count = 3
angle = np.pi / 2  # Phase = 1/4

qc = QuantumCircuit(n_count + 1, n_count)

# Prepare eigenstate |1>
qc.x(n_count)

# Hadamard on counting register
for q in range(n_count):
    qc.h(q)

# Controlled-U^{2^k} operations
for q in range(n_count):
    qc.cp(angle * (2 ** q), q, n_count)

# Inverse QFT
qc = qc.compose(QFT(num_qubits=n_count, inverse=True), range(n_count))

# Measure counting register
qc.measure(range(n_count), range(n_count))

print(qc.draw(output='text'))

Quantum Phase Estimation with PennyLane

A 3-qubit QPE implementation in PennyLane using ControlledPhaseShift and the adjoint QFT.

qpe_pennylane.py

import pennylane as qml
import numpy as np

n_count = 3
dev = qml.device('default.qubit', wires=n_count + 1)

@qml.qnode(dev)
def qpe():
    # Eigenstate |1>
    qml.PauliX(wires=n_count)
    # Hadamard on counting register
    for q in range(n_count):
        qml.Hadamard(wires=q)
    # Controlled-U^{2^k} for phase = 1/4
    for q in range(n_count):
        qml.ControlledPhaseShift(np.pi / 2 * (2 ** q), wires=[q, n_count])
    # Inverse QFT
    qml.adjoint(qml.QFT)(wires=range(n_count))
    return qml.probs(wires=range(n_count))

print(qpe())

Explore next

Quantum Counting

Explore next

HHL Algorithm

from qiskit import QuantumCircuit from qiskit.circuit.library import QFT import numpy as np n_count = 3 angle = np.pi / 2 # Phase = 1/4 qc = QuantumCircuit(n_count + 1, n_count) # Prepare eigenstate |1> qc.x(n_count) # Hadamard on counting register for q in range(n_count): qc.h(q) # Controlled-U^{2^k} operations for q in range(n_count): qc.cp(angle * (2 ** q), q, n_count) # Inverse QFT qc = qc.compose(QFT(num_qubits=n_count, inverse=True), range(n_count)) # Measure counting register qc.measure(range(n_count), range(n_count)) print(qc.draw(output='text'))

import pennylane as qml import numpy as np n_count = 3 dev = qml.device('default.qubit', wires=n_count + 1) @qml.qnode(dev) def qpe(): # Eigenstate |1> qml.PauliX(wires=n_count) # Hadamard on counting register for q in range(n_count): qml.Hadamard(wires=q) # Controlled-U^{2^k} for phase = 1/4 for q in range(n_count): qml.ControlledPhaseShift(np.pi / 2 * (2 ** q), wires=[q, n_count]) # Inverse QFT qml.adjoint(qml.QFT)(wires=range(n_count)) return qml.probs(wires=range(n_count)) print(qpe())