qml.qaoa.cycle.out_flow_constraint

out_flow_constraint(graph)

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

code/api/pennylane.qaoa.cycle.out_flow_constraint

 

Download Python script

 

Download Notebook

 

View on GitHub