qml.qaoa.cost.maxcut

maxcut(graph)[source]

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.

Note

Recommended initialization circuit:

Even superposition over all basis states

Parameters

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

Returns

The cost and mixer Hamiltonians

Return type

(Hamiltonian, Hamiltonian)

Example

>>> 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]