qml.qaoa.cycle.out_flow_constraint¶

out_flow_constraint(graph: networkx.classes.digraph.DiGraph)pennylane.ops.qubit.hamiltonian.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