# QAOA (Quantum Approximate Optimization Algorithm)

**QAOA** solves combinatorial optimization problems via alternating cost and mixer Hamiltonians. The ansatz is a parameterized circuit; optimize parameters to maximize objective.

```cpp
#include "cudaq.h"
#include "cudaq/algorithm/qaoa.h"
#include "cudaq/optimizer.h"

// Cost Hamiltonian: encodes problem (e.g., MaxCut)
// For MaxCut on edge (0,1): H_C = 0.5*(Z_0*Z_1 - 1)
cudaq::spin_op cost_hamiltonian = 0.5 * (cudaq::spin::z(0) * cudaq::spin::z(1) - 
                                          cudaq::spin::i(0) * cudaq::spin::i(1));

// Mixer: drives exploration
cudaq::spin_op mixer = cudaq::spin::x(0) + cudaq::spin::x(1);

// QAOA ansatz: parametrized cost and mixer layers
struct QAOAAnsatz {
  void operator()(std::vector<double> params, int depth) __qpu__ {
    cudaq::qvector q(2);
    
    // Initial superposition
    for (int i = 0; i < 2; i++) {
      h(q[i]);
    }
    
    // QAOA layers
    for (int layer = 0; layer < depth; layer++) {
      // Cost Hamiltonian: exp(-i*gamma*H_C)
      auto gamma = params[2*layer];
      auto zz_angle = 2.0 * gamma;
      cx(q[0], q[1]);
      rz(zz_angle, q[1]);
      cx(q[0], q[1]);
      
      // Mixer Hamiltonian: exp(-i*beta*H_M)
      auto beta = params[2*layer + 1];
      rx(2.0 * beta, q[0]);
      rx(2.0 * beta, q[1]);
    }
    
    mz(q);
  }
};

int main() {
  int depth = 2;
  std::vector<double> params(2 * depth, 0.1);
  
  cudaq::optimizers::COBYLA optimizer;
  
  // Cost function: evaluate objective
  auto cost_func = [](std::vector<double> params) {
    auto result = cudaq::sample<QAOAAnsatz>(1000, params, depth);
    // Return negative expected objective (to minimize)
    return -result.probability("11");
  };
  
  // Optimize QAOA parameters
  auto [opt_params, opt_cost] = optimizer.optimize(params, cost_func);
  
  printf("Optimal cost: %.6f\n", opt_cost);
  
  return 0;
}
```

QAOA is a practical algorithm for near-term devices—shallow circuits, modest parameter count. Performance depends on ansatz depth and problem structure.