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

Given a subset of edges in a directed graph, the out-flow constraint imposes that at most one edge can leave any given node, i.e., for all \(i\):

\[\sum_{j,(i,j)\in E}x_{ij} \leq 1,\]

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 satisfies the out-flow constraint whenever the following Hamiltonian is minimized:

\[\sum_{i\in V}\left(d_{i}^{out}(d_{i}^{out} - 2)\mathbb{I} - 2(d_{i}^{out}-1)\sum_{j,(i,j)\in E}\hat{Z}_{ij} + \left( \sum_{j,(i,j)\in E}\hat{Z}_{ij} \right)^{2}\right)\]

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


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


the out flow constraint Hamiltonian

Return type



ValueError – if the input graph is not directed