QAOA – Quantum Approximate Optimization Algorithm: A NISQ-Era Solution for Discrete Problems

Table of Contents

1. Introduction
2. What Is QAOA?
3. Why Use QAOA for Optimization?
4. Problem Formulation: QUBO and Ising Models
5. The QAOA Circuit Architecture
6. Cost and Mixer Hamiltonians
7. Parameterized QAOA Steps
8. Classical Optimization of Parameters
9. QAOA Objective Function
10. Choosing Depth (p) and Circuit Scaling
11. Example: MaxCut with QAOA
12. Performance in Noisy Environments
13. Implementation in Qiskit
14. Implementation in PennyLane
15. Optimizer Strategies: COBYLA, SPSA, Adam
16. Barren Plateaus and Parameter Initialization
17. Extensions: Warm Start QAOA and Layer-wise Training
18. Applications in Graph Theory, Logistics, and ML
19. Limitations and Current Research
20. Conclusion

1. Introduction

The Quantum Approximate Optimization Algorithm (QAOA) is a hybrid algorithm designed to solve combinatorial optimization problems. It uses a shallow quantum circuit and classical optimizer to iteratively improve candidate solutions.

2. What Is QAOA?

QAOA is based on alternating applications of two Hamiltonians — a problem-specific cost Hamiltonian and a mixing Hamiltonian — to evolve the quantum state toward an optimal solution.

3. Why Use QAOA for Optimization?

• Suitable for NISQ devices (shallow circuits)
• Applies to discrete binary problems (e.g., MaxCut, SAT, scheduling)
• Combines quantum exploration with classical optimization

4. Problem Formulation: QUBO and Ising Models

Optimization problems are reformulated as:

• QUBO: Quadratic Unconstrained Binary Optimization
  \[
  \min_x x^T Q x
  \]
• Ising:
  \[
  H_C = \sum_i h_i Z_i + \sum_{i<j} J_{ij} Z_i Z_j
  \]

5. The QAOA Circuit Architecture

The algorithm constructs:
\[
|\gamma, eta
angle = e^{-ieta_p H_M} e^{-i\gamma_p H_C} \cdots e^{-ieta_1 H_M} e^{-i\gamma_1 H_C} |+
angle^{\otimes n}
\]
Where:

• \( H_C \): cost Hamiltonian
• \( H_M \): mixing Hamiltonian (e.g., \( \sum_i X_i \))
• \( \gamma, eta \): variational parameters

6. Cost and Mixer Hamiltonians

• Cost Hamiltonian depends on the problem graph
• Mixer is often \( H_M = \sum_i X_i \)

7. Parameterized QAOA Steps

Each layer applies \( U_C(\gamma) \) and \( U_M(eta) \), controlled by p parameters (or 2p for layer-wise).

8. Classical Optimization of Parameters

The output state is measured and evaluated with a classical optimizer to minimize the cost function.

9. QAOA Objective Function

\[
F(ec{\gamma}, ec{eta}) = \langle \psi(ec{\gamma}, ec{eta}) | H_C | \psi(ec{\gamma}, ec{eta})
angle
\]

10. Choosing Depth (p) and Circuit Scaling

• Larger p improves approximation but increases depth and noise
• Trade-off between accuracy and circuit feasibility

11. Example: MaxCut with QAOA

MaxCut Hamiltonian:
\[
H_C = \sum_{(i,j) \in E} rac{1}{2}(I – Z_i Z_j)
\]
Maps to qubit pairs and Z operators.

12. Performance in Noisy Environments

QAOA is more noise-resilient than other deep circuits. Shallow depths help limit decoherence effects.

13. Implementation in Qiskit

from qiskit.algorithms import QAOA
from qiskit_optimization.applications import Maxcut

14. Implementation in PennyLane

import pennylane as qml
@qml.qnode(dev)
def circuit(params):
    qaoa_layer(params, G)

15. Optimizer Strategies: COBYLA, SPSA, Adam

• SPSA: best for noisy environments
• COBYLA: fast convergence, no gradients
• Adam: used in ML-style training

16. Barren Plateaus and Parameter Initialization

Use:

• Layer-wise training
• Parameter interpolation
• Warm-start from classical approximations

17. Extensions: Warm Start QAOA and Layer-wise Training

• Start with good classical guess
• Add layers one-by-one while refining previous parameters

18. Applications in Graph Theory, Logistics, and ML

• MaxCut, TSP, graph coloring
• Scheduling and portfolio optimization
• Feature selection in ML

19. Limitations and Current Research

• Scalability beyond 30 qubits is limited
• Convergence issues for poorly chosen ansatz
• Research ongoing into adaptive and problem-specific versions

20. Conclusion

QAOA represents a promising hybrid quantum-classical algorithm well-suited for near-term quantum devices. With practical applications and strong performance on structured problems, it continues to be a central focus of quantum algorithm research and real-world experimentation.