qml.qaoa.cycle.net_flow_constraint

net_flow_constraint(graph)

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

code/api/pennylane.qaoa.cycle.net_flow_constraint

 

Download Python script

 

Download Notebook

 

View on GitHub