qml.qaoa.cycle.out_flow_constraint

out_flow_constraint(graph: networkx.classes.digraph.DiGraph)pennylane.vqe.vqe.Hamiltonian[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) – 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