7.3 Phase estimation

Phase estimation is a crucial quantum algorithm that determines eigenvalues of unitary operators. It's a key component in many quantum algorithms, enabling the extraction of important information encoded in eigenvalues.

The algorithm uses two registers and involves initializing, applying controlled operations, and using the quantum Fourier transform. It has wide-ranging applications, from Shor's factoring algorithm to estimating ground state energies in quantum chemistry.

Phase Estimation in Quantum Algorithms

Concept of phase estimation

• Quantum algorithm estimates eigenvalue (phase) of eigenvector of unitary operator
  • Eigenvalue $\lambda$ satisfies equation $U|\psi\rangle = \lambda|\psi\rangle$ where $U$ is unitary operator and $|\psi\rangle$ is eigenvector
  • Unitary operator is linear transformation that preserves inner product of vectors and satisfies $U^\dagger U = UU^\dagger = I$
• Key component in many quantum algorithms (Shor's algorithm for factoring, HHL algorithm for solving linear systems of equations)
• Enables extraction of eigenvalues which often encode important information about problem being solved
• Can estimate ground state energy of quantum system important in quantum chemistry and optimization problems

Implementation of phase estimation

• Requires two registers:
  • Control register with $n$ qubits determines precision of phase estimate
  • Target register with $m$ qubits initialized to eigenvector $|\psi\rangle$ of unitary operator $U$
• Algorithm steps:
  1. Initialize control register to $|0\rangle^{\otimes n}$ and target register to $|\psi\rangle$
  2. Apply Hadamard gates to each qubit in control register creating uniform superposition of all basis states
  3. Apply controlled-$U$ operations between control and target registers with number of applications of $U$ determined by corresponding basis state of control register
     • If control register in state $|k\rangle$, apply $U^k$ to target register
  4. Apply inverse quantum Fourier transform (QFT) to control register
  5. Measure control register to obtain estimate of phase $\phi$ where eigenvalue is $e^{2\pi i\phi}$

Phase estimation vs quantum Fourier transform

• Quantum Fourier transform (QFT) is key component of phase estimation algorithm
  • QFT is linear transformation that maps quantum state to its Fourier representation
  • Quantum analog of discrete Fourier transform (DFT)
• In phase estimation algorithm, inverse QFT applied to control register before measurement
  • Inverse QFT transforms phase information encoded in amplitudes of control register into binary representation of phase
  • Allows for estimation of phase by measuring control register in computational basis
• Precision of phase estimate depends on number of qubits in control register
  • Larger number of qubits in control register results in more precise estimate of phase
  • Number of qubits required scales logarithmically with desired precision

Applications of phase estimation

• Shor's algorithm for factoring large numbers:
  • Estimates period of modular exponentiation function
  • Period then used to factor large number
• HHL algorithm for solving linear systems of equations:
  • Estimates eigenvalues of matrix associated with linear system
  • Estimated eigenvalues then used to construct solution to linear system
• Ground state energy estimation in quantum chemistry:
  • Estimates ground state energy of molecular Hamiltonian
  • Estimated ground state energy helps understand chemical properties and reactivity
• Quantum walk algorithms:
  • Analyzes properties of quantum walks (mixing time, hitting time)
  • Information used to design efficient quantum algorithms for various graph problems