qml.qaoa.cycle.net_flow_constraint

net_flow_constraint(graph)[source]

Calculates the net flow constraint Hamiltonian for the maximum-weighted cycle problem.

Given a subset of edges in a directed graph, the net-flow constraint imposes that the number of edges leaving any given node is equal to the number of edges entering the node, i.e.,

\[\sum_{j, (i, j) \in E} x_{ij} = \sum_{j, (j, i) \in E} x_{ji},\]

for all nodes \(i\), where \(E\) are the edges of the graph and \(x_{ij}\) is a binary number that selects whether to include the edge \((i, j)\).

A set of edges has zero net flow whenever the following Hamiltonian is minimized:

\[\sum_{i \in V} \left((d_{i}^{\rm out} - d_{i}^{\rm in})\mathbb{I} - \sum_{j, (i, j) \in E} Z_{ij} + \sum_{j, (j, i) \in E} Z_{ji} \right)^{2},\]

where \(V\) are the graph vertices, \(d_{i}^{\rm out}\) and \(d_{i}^{\rm in}\) are the outdegree and indegree, respectively, of node \(i\) and \(Z_{ij}\) is a qubit Pauli-Z matrix acting upon the wire specified by the pair \((i, j)\). Mapping from edges to wires can be achieved using edges_to_wires().

Parameters

graph (nx.DiGraph or rx.PyDiGraph) – the directed graph specifying possible edges

Returns

the net-flow constraint Hamiltonian

Return type

qml.Hamiltonian

Raises

ValueError – if the input graph is not directed