Returns the QAOA cost Hamiltonian and the recommended mixer corresponding to the MaxCut problem, for a given graph.

The goal of the MaxCut problem for a particular graph is to find a partition of nodes into two sets, such that the number of edges in the graph with endpoints in different sets is maximized. Formally, we wish to find the cut of the graph such that the number of edges crossing the cut is maximized.

The MaxCut cost Hamiltonian is defined as:

\[H_C \ = \ \frac{1}{2} \displaystyle\sum_{(i, j) \in E(G)} \big( Z_i Z_j \ - \ \mathbb{I} \big),\]

where \(G\) is a graph, \(\mathbb{I}\) is the identity, and \(Z_i\) and \(Z_j\) are the Pauli-Z operators on the \(i\)-th and \(j\)-th wire respectively.

The mixer Hamiltonian returned from maxcut() is x_mixer() applied to all wires.


Recommended initialization circuit:

Even superposition over all basis states


graph (nx.Graph) – a graph defining the pairs of wires on which each term of the Hamiltonian acts


The cost and mixer Hamiltonians

Return type

(Hamiltonian, Hamiltonian)


>>> graph = nx.Graph([(0, 1), (1, 2)])
>>> cost_h, mixer_h = qml.qaoa.maxcut(graph)
>>> print(cost_h)
(0.5) [Z0 Z1] + (0.5) [Z1 Z2] + (-1.0) [I0]
>>> print(mixer_h)
(1.0) [X0] + (1.0) [X1] + (1.0) [X2]