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