Quantum Approximate Optimization Algorithm

The QAOA ansatz is constructed from two non-commuting Hamiltonians: a problem-dependent cost Hamiltonian \hat{H}_C that encodes the objective function to be minimized, and a transverse-field mixing Hamiltonian \hat{H}_M that enables exploration of the solution space. The algorithm prepares a variational state by alternately applying evolution operators generated by these Hamiltonians for p rounds, creating a 2p-parameter quantum circuit. The initial state is the uniform superposition |+\rangle^{\otimes n}, which is the ground state of the mixing Hamiltonian and an equally weighted sum over all computational basis states.

Each layer consists of a cost evolution e^{-i\gamma_k \hat{H}_C} followed by a mixing evolution e^{-i\beta_k \hat{H}_M}. The cost evolution applies a phase to each computational basis state proportional to its objective value, while the mixing evolution rotates amplitudes between states, creating interference patterns that amplify low-cost solutions. As the number of layers p increases, the QAOA state family becomes more expressive, eventually containing the adiabatic path as p \rightarrow \infty under appropriate parameter schedules.

The variational parameters \{\gamma, \beta\} are optimized classically to minimize the expectation value of the cost Hamiltonian with respect to the quantum state. This hybrid loop leverages quantum resources for state preparation and measurement while using classical optimizers to navigate the parameter landscape. The choice of classical optimizer, initialization strategy, and parameter constraints significantly impact the quality of solutions achievable at finite depth.

• •Cost Hamiltonian: \hat{H}_C is diagonal in the computational basis with eigenvalues equal to the optimization objective function values.
• •Mixing Hamiltonian: \hat{H}_M = \sum_i \hat{X}_i drives transitions between computational states and ensures the ansatz can explore the full Hilbert space.
• •Depth Parameter p: Increasing p enhances expressivity but also increases circuit depth, gate errors, and optimization difficulty.
• •Trotter Connection: For p \rightarrow \infty with infinitesimal parameters, QAOA reproduces adiabatic evolution, bridging variational and adiabatic paradigms.

The Max-Cut problem asks for a partition of a graph's vertices into two sets that maximizes the number of edges crossing between the sets. This NP-hard combinatorial problem maps naturally to an Ising Hamiltonian where each vertex is assigned a spin variable and each edge contributes an energy penalty when its endpoints share the same partition. The ground state of this Ising model corresponds to the optimal Max-Cut partition, making it an ideal target for QAOA.

The cost Hamiltonian for Max-Cut on an unweighted graph G = (V, E) takes the form of a sum over edges with ZZ interactions. Each term (\hat{I} - \hat{Z}_i \hat{Z}_j)/2 evaluates to 0 when vertices i and j are in different partitions and to 1 when they are in the same partition. The total cost Hamiltonian therefore counts the number of uncut edges, so minimizing its expectation value is equivalent to maximizing the cut size. For weighted graphs, each edge term is multiplied by its weight.

The classical Goemans-Williamson algorithm provides a semidefinite programming relaxation that achieves an approximation ratio of approximately 0.878 for general graphs, which serves as an important benchmark for QAOA. For specific graph families, such as bounded-degree graphs or those with particular symmetries, QAOA at fixed depth can sometimes match or exceed this bound. However, for general graphs, the achievable approximation ratio at finite p and the scaling behavior with graph size remain active areas of theoretical research.

• •Ising Mapping: Max-Cut is mapped to an Ising model with ZZ interactions, where spin configurations correspond to graph bipartitions.
• •Unweighted vs Weighted: Edge weights enter the cost Hamiltonian as coefficients, allowing QAOA to handle arbitrary weighted Max-Cut instances.
• •Goemans-Williamson Bound: The classical SDP achieves ratio approximately 0.878; QAOA must exceed this to demonstrate quantum advantage for general graphs.
• •Symmetry Exploitation: Graph automorphisms can reduce the effective parameter space and simplify classical optimization.