Table of Contents
- Introduction
- Motivation and Applications
- Problem Statement
- Mathematical Background
- Quantum Phase Estimation: Goal
- Overview of the Algorithm
- Unitary Operators and Eigenstates
- Phase Encoding via Controlled Operations
- Quantum Fourier Transform in Phase Estimation
- Register Initialization
- Applying Hadamards
- Controlled-\(U^{2^j}\) Operations
- Inverse Quantum Fourier Transform
- Measurement and Phase Extraction
- Precision and Error Bounds
- Example with 3 Qubits
- Geometric Interpretation
- Relationship to Eigenvalue Estimation
- Phase Estimation in Shor’s Algorithm
- Applications in Quantum Chemistry
- Hamiltonian Simulation Use Case
- Variants of the Algorithm
- Circuit Construction in Qiskit
- Limitations and Practical Considerations
- Conclusion
1. Introduction
The Phase Estimation Algorithm (PEA) is one of the most powerful quantum algorithms, allowing for the extraction of eigenvalues of a unitary operator. It underlies several other algorithms including Shor’s factoring and quantum simulation techniques.
2. Motivation and Applications
Phase estimation is essential in:
- Shor’s Algorithm (order finding)
- Quantum chemistry (eigenvalue problems)
- Hamiltonian simulation
- Quantum machine learning
3. Problem Statement
Given:
- A unitary operator \( U \)
- An eigenstate \( |\psi\rangle \) such that \( U|\psi\rangle = e^{2\pi i \phi}|\psi\rangle \)
The goal is to estimate the unknown phase \( \phi \in [0,1) \).
4. Mathematical Background
Any unitary matrix \( U \) has eigenvalues on the complex unit circle. The goal is to extract \( \phi \) from \( e^{2\pi i \phi} \).
5. Quantum Phase Estimation: Goal
Prepare a quantum system in which \( \phi \) is encoded in the amplitudes of a state. Then, use quantum interference (QFT) to reveal \( \phi \) through measurement.
6. Overview of the Algorithm
Steps:
- Prepare \( t \) qubit control register and target eigenstate \( |\psi\rangle \)
- Apply Hadamard gates to control register
- Apply controlled-\(U^{2^j}\) gates
- Apply inverse QFT
- Measure control register
7. Unitary Operators and Eigenstates
We assume that:
\[
U|\psi\rangle = e^{2\pi i \phi}|\psi\rangle
\]
We don’t know \( \phi \), but we want to estimate it to precision \( 1/2^t \).
8. Phase Encoding via Controlled Operations
Apply controlled operations \( CU^{2^j} \) for each qubit in the control register. This encodes \( \phi \) as a phase:
\[
|j\rangle \rightarrow e^{2\pi i 2^j \phi}|j\rangle
\]
9. Quantum Fourier Transform in Phase Estimation
Apply inverse QFT on control register to decode the phase into the computational basis:
\[
\text{QFT}^{-1}\left( \sum_k e^{2\pi i k \phi}|k\rangle \right) \rightarrow |\phi\rangle
\]
10. Register Initialization
Initial state:
\[
|0\rangle^{\otimes t} \otimes |\psi\rangle
\]
After Hadamards:
\[
\frac{1}{\sqrt{2^t}} \sum_{k=0}^{2^t – 1} |k\rangle \otimes |\psi\rangle
\]
11. Applying Hadamards
Each control qubit is placed in superposition via Hadamard:
\[
H|0\rangle = \frac{1}{\sqrt{2}}(|0\rangle + |1\rangle)
\]
Entire control register becomes:
\[
\frac{1}{\sqrt{2^t}} \sum_{k=0}^{2^t-1} |k\rangle
\]
12. Controlled-\(U^{2^j}\) Operations
Each control qubit \( j \) controls the operation \( U^{2^j} \):
\[
\sum_{k=0}^{2^t-1} |k\rangle U^k|\psi\rangle
\Rightarrow
\sum_{k=0}^{2^t-1} e^{2\pi i k \phi}|k\rangle |\psi\rangle
\]
13. Inverse Quantum Fourier Transform
Applying \( QFT^{-1} \) to the control register transforms the relative phases into measurable probability peaks around \( \phi \).
14. Measurement and Phase Extraction
Measuring the control register gives a binary approximation of \( \phi \). If \( \phi \) has a binary expansion with \( t \) digits, the algorithm recovers it exactly.
15. Precision and Error Bounds
The probability of success increases with more qubits. For \( t \) qubits, the algorithm approximates \( \phi \) to \( t \) bits of precision with high probability.
16. Example with 3 Qubits
Let \( \phi = 0.625 = 101_2/8 \)
- The QFT circuit transforms the control register
- Measurement yields \( 101 \), or 0.625 with high probability
17. Geometric Interpretation
The amplitudes rotate based on \( \phi \), and QFT aligns these rotations to reveal the phase through constructive interference.
18. Relationship to Eigenvalue Estimation
PEA is equivalent to estimating eigenvalues \( e^{2\pi i \phi} \) of \( U \), giving access to eigenenergies and dynamics of physical systems.
19. Phase Estimation in Shor’s Algorithm
In Shor’s algorithm, phase estimation is used to find the period \( r \) of \( a^x \mod N \), where the phase is \( \phi = k/r \).
20. Applications in Quantum Chemistry
Used to compute eigenvalues of molecular Hamiltonians, giving accurate energy levels — a key application in quantum simulation.
21. Hamiltonian Simulation Use Case
In combination with Trotterization and Hamiltonian exponentiation, PEA can extract energy levels of quantum systems.
22. Variants of the Algorithm
- Iterative Phase Estimation (IPEA): requires fewer qubits
- Kitaev’s algorithm: early approach using entanglement
- Robust PEA: improves fault tolerance and precision
23. Circuit Construction in Qiskit
from qiskit import QuantumCircuit, Aer, execute
from qiskit.circuit.library import QFT
n = 3
qc = QuantumCircuit(n+1, n)
# Hadamard on control register
qc.h(range(n))
# Simulated U = Z gate, controlled-U^2^j
for j in range(n):
qc.cp(2 * 3.1415 / (2**(j+1)), j, n)
# Inverse QFT
qc.append(QFT(num_qubits=n, inverse=True, do_swaps=True), range(n))
# Measure
qc.measure(range(n), range(n))24. Limitations and Practical Considerations
- Requires controlled-\(U^{2^j}\) implementations
- Needs large depth for high precision
- Sensitive to noise and decoherence
25. Conclusion
The Phase Estimation Algorithm is a foundational quantum algorithm with wide-ranging applications, from factoring to simulating quantum systems. It leverages quantum superposition, interference, and Fourier transforms to extract hidden phase information with exponential precision.