Quantum Approximate Optimization Algorithm

Solve combinatorial optimization problems like MaxCut using a hybrid quantum-classical approach.

Number of nodes in the graph

int (min: 2)

Probability of edge creation

float (min: 0.1)

Number of QAOA layers

int (min: 1)

Noise probability

float (min: 0.0)

Number of samples

int (min: 10)

Navigation

Back to Home Quantum Computing Glossary

Simulation Results

Ready

Quantum Simulation

Configure parameters and run the simulation to see results.

Quantum Explanation

Understanding QAOA: The Optimization Problem

QAOA employs a series of parameterized quantum operations to encode optimization problems. By alternating between problem-specific cost operations and mixing operations, the algorithm uses classical optimization routines to fine-tune parameters, gradually improving the solution quality.

Key Quantum Principle: Combining quantum state exploration with classical feedback, QAOA efficiently navigates complex solution landscapes in search of near-optimal answers.

Quantum Phase Estimation: Eigenvalue Extraction

Quantum Phase Estimation (QPE) is a fundamental quantum algorithm that determines the eigenphase of a unitary operator's eigenvector with high precision. It serves as a critical subroutine in many quantum algorithms including Shor's factoring algorithm and HHL for solving linear systems.

Classical vs. Quantum Estimation: Classically, estimating eigenvalues with precision 2^-n typically requires O(2ⁿ) operations. QPE can achieve the same precision using only O(n) qubits and quantum operations, providing an exponential advantage.

How Quantum Phase Estimation Works

Initialization: Prepare a register of n phase qubits in |0⟩ state and a target register in the eigenvector state |ψ⟩.
Superposition: Apply Hadamard gates to all phase qubits to create superposition.
Controlled Operations: Apply controlled-U^{2^j} operations between each phase qubit j and the target register.
Inverse QFT: Apply inverse Quantum Fourier Transform to the phase register.
Measurement: Measure the phase register to obtain a binary approximation of the eigenphase φ.

QPE Circuit Visualization

Quantum circuit for phase estimation showing the phase register, controlled-U operations, and inverse QFT to extract the eigenphase.

Key Quantum Principles in QPE

Eigenvalue Extraction: QPE extracts the eigenvalue φ from a unitary operator U and its eigenvector |ψ⟩, where U|ψ⟩ = e^2πiφ|ψ⟩.
Phase Kickback: Using controlled-U operations to encode phase information in the control qubits.
Quantum Fourier Transform: The inverse QFT converts phase information into a binary representation.
Amplitude Amplification: The algorithm naturally amplifies the correct phase through quantum interference.

Applications of Quantum Phase Estimation

QPE enables numerous quantum algorithms with significant practical applications:

Shor's Algorithm: Uses QPE to find the period of a modular function, enabling integer factorization.
Quantum Chemistry: Determines molecular energy levels and electronic structure properties.
HHL Algorithm: Solves linear systems of equations for applications in simulation and machine learning.
Quantum Counting: Determines how many inputs satisfy a given property with quadratic speedup.
Hamiltonian Simulation: Enables efficient simulation of quantum systems for physics and chemistry.

QAOA: Quantum Optimization

The Quantum Approximate Optimization Algorithm (QAOA) is a hybrid quantum-classical algorithm for combinatorial optimization problems:

Problem Encoding: Map optimization problems to a cost Hamiltonian H_C that encodes the objective function.
Parameterized Circuit: Create a quantum circuit with parameters β and γ that alternates between problem and mixer Hamiltonians.
Variational Approach: Use classical optimization to find optimal parameters that minimize the cost function.
Depth Parameter p: Controls circuit depth and approximation quality, with higher p generally giving better results.
Applications: Solves problems like MaxCut, traveling salesman, and satisfiability with potential quantum advantage.

Beginner's Analogy: Understanding QPE and QAOA

For QPE: Imagine you have a mysterious clock with hands that rotate at an unknown but fixed rate. Classically, you'd need to watch the clock for a very long time to precisely determine this rate. Quantum phase estimation is like having a special device that can observe all possible rotations simultaneously and determine the exact rotation rate exponentially faster.

The "quantum magic" happens because quantum superposition allows the observation of all time periods at once, while quantum interference amplifies the true rotation rate.

For QAOA: Think of trying to find the highest peak in a mountain range while blindfolded. Classically, you'd need to check many locations randomly or systematically. QAOA is like having a special quantum compass that points increasingly toward higher ground as you adjust its parameters, helping you find the highest peak much faster.

Further Learning Resources

QPE on Wikipedia

QAOA Original Paper

Qiskit QPE Tutorial