Phase Estimation Algorithm

Table of Contents

1. Introduction
2. Motivation and Applications
3. Problem Statement
4. Mathematical Background
5. Quantum Phase Estimation: Goal
6. Overview of the Algorithm
7. Unitary Operators and Eigenstates
8. Phase Encoding via Controlled Operations
9. Quantum Fourier Transform in Phase Estimation
10. Register Initialization
11. Applying Hadamards
12. Controlled-\(U^{2^j}\) Operations
13. Inverse Quantum Fourier Transform
14. Measurement and Phase Extraction
15. Precision and Error Bounds
16. Example with 3 Qubits
17. Geometric Interpretation
18. Relationship to Eigenvalue Estimation
19. Phase Estimation in Shor’s Algorithm
20. Applications in Quantum Chemistry
21. Hamiltonian Simulation Use Case
22. Variants of the Algorithm
23. Circuit Construction in Qiskit
24. Limitations and Practical Considerations
25. 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:

1. Prepare \( t \) qubit control register and target eigenstate \( |\psi\rangle \)
2. Apply Hadamard gates to control register
3. Apply controlled-\(U^{2^j}\) gates
4. Apply inverse QFT
5. 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.

---