QAOA for Max-Cut

QAOA for Max-Cut

The Quantum Approximate Optimization Algorithm (QAOA) is a hybrid quantum-classical method for finding approximate solutions to combinatorial optimization problems, and this Cirq example applies it to Max-Cut, the problem of partitioning a graph's vertices into two sets so as to maximize the number of edges crossing between them. QAOA encodes the problem's cost function into a sequence of alternating unitaries: a problem (cost) Hamiltonian that imprints phases according to the objective, and a mixer Hamiltonian that drives transitions between candidate solutions. Each layer is parameterized by two angles, and a classical optimizer tunes these angles to maximize the expected cut value measured from the quantum state. The example builds a random graph, constructs the corresponding parameterized QAOA circuit, sweeps or optimizes over the variational parameters, simulates the circuit to estimate the objective, and reports the best cut it finds along with the bitstring describing the partition. Because its shallow, parameterized structure suits noisy near-term hardware, QAOA is one of the most studied algorithms for demonstrating quantum optimization, and Max-Cut is its canonical benchmark problem.

Run it

pip install -r requirements.txt
python qaoa.py

Source and license

Imported from examples/qaoa.py in quantumlib/Cirq at v1.6.1, under the Apache License 2.0. Original authors: The Cirq Developers. The upstream LICENSE is included alongside this example.