qml.qaoa.cycle.out_flow_constraint¶
- out_flow_constraint(graph)[source]¶
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().- Parameters
graph (nx.DiGraph or rx.PyDiGraph) – the directed graph specifying possible edges
- Returns
the out flow constraint Hamiltonian
- Return type
qml.Hamiltonian
- Raises
ValueError – if the input graph is not directed