qml.qaoa.cost.maxcut

maxcut(graph)

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 or rx.PyGraph) – 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

>>> import networkx as nx
>>> graph = nx.Graph([(0, 1), (1, 2)])
>>> cost_h, mixer_h = qml.qaoa.maxcut(graph)
>>> print(cost_h)
0.5 * (Z(0) @ Z(1)) + 0.5 * (Z(1) @ Z(2)) + -0.5 * (I(0) @ I(1)) + -0.5 * (I(1) @ I(2))
>>> print(mixer_h)
1 * X(0) + 1 * X(1) + 1 * X(2)

>>> import rustworkx as rx
>>> graph = rx.PyGraph()
>>> graph.add_nodes_from([0, 1, 2])
>>> graph.add_edges_from([(0, 1,""), (1,2,"")])
>>> cost_h, mixer_h = qml.qaoa.maxcut(graph)
>>> print(cost_h)
0.5 * (Z(0) @ Z(1)) + 0.5 * (Z(1) @ Z(2)) + -0.5 * (I(0) @ I(1)) + -0.5 * (I(1) @ I(2))
>>> print(mixer_h)
1 * X(0) + 1 * X(1) + 1 * X(2)

code/api/pennylane.qaoa.cost.maxcut

 

Download Python script

 

Download Notebook

 

View on GitHub