Repository: PennyLaneAI/pennylane
Pull request #1214 (2021-04-14 18:46:57)

Net flow constraint
For the max weighted cycle QAOA problem, the unconstrained approach requires constraints to be included in the cost Hamiltonian. A net flow constraint is introduced to the cost Hamiltonian to help ensure it's minimised by selecting edges such that each node has a net flow of zero edges entering and leaving. 

Add a net flow constraint function
Add a private function to calculate quadratic terms of the constraint.

Allows a user to easily introduce constraints to cost Hamiltonian.

It relies on private functions that may be redundant when changes to `qml.Hamiltonian` are introduced


github-actions[bot]: Hello. You may have forgotten to update the changelog!
Please edit [.github/CHANGELOG.md](/PennyLaneAI/pennylane/blob/master/.github/CHANGELOG.md) with:
* A one-to-two sentence description of the change. You may include a small working example for new features.
* A link back to this PR.
* Your name (or GitHub username) in the contributors section.
codecov[bot]: # [Codecov](https://codecov.io/gh/PennyLaneAI/pennylane/pull/1214?src=pr&el=h1&utm_medium=referral&utm_source=github&utm_content=comment&utm_campaign=pr+comments&utm_term=PennyLaneAI) Report
> Merging [#1214](https://codecov.io/gh/PennyLaneAI/pennylane/pull/1214?src=pr&el=desc&utm_medium=referral&utm_source=github&utm_content=comment&utm_campaign=pr+comments&utm_term=PennyLaneAI) (2379f99) into [qaoa_cycles_module](https://codecov.io/gh/PennyLaneAI/pennylane/commit/a4548bf25e1a0530f790d7eec9078260a4950ac7?el=desc&utm_medium=referral&utm_source=github&utm_content=comment&utm_campaign=pr+comments&utm_term=PennyLaneAI) (a4548bf) will **decrease** coverage by `0.04%`.
> The diff coverage is `90.62%`.

[![Impacted file tree graph](https://codecov.io/gh/PennyLaneAI/pennylane/pull/1214/graphs/tree.svg?width=650&height=150&src=pr&token=9S3YzlUgGk&utm_medium=referral&utm_source=github&utm_content=comment&utm_campaign=pr+comments&utm_term=PennyLaneAI)](https://codecov.io/gh/PennyLaneAI/pennylane/pull/1214?src=pr&el=tree&utm_medium=referral&utm_source=github&utm_content=comment&utm_campaign=pr+comments&utm_term=PennyLaneAI)

```diff
@@                  Coverage Diff                   @@
##           qaoa_cycles_module    #1214      +/-   ##
======================================================
- Coverage               98.12%   98.08%   -0.05%     
======================================================
  Files                     146      146              
  Lines                   10992    11055      +63     
======================================================
+ Hits                    10786    10843      +57     
- Misses                    206      212       +6     
```


| [Impacted Files](https://codecov.io/gh/PennyLaneAI/pennylane/pull/1214?src=pr&el=tree&utm_medium=referral&utm_source=github&utm_content=comment&utm_campaign=pr+comments&utm_term=PennyLaneAI) | Coverage Δ | |
|---|---|---|
| [pennylane/qaoa/cycle.py](https://codecov.io/gh/PennyLaneAI/pennylane/pull/1214/diff?src=pr&el=tree&utm_medium=referral&utm_source=github&utm_content=comment&utm_campaign=pr+comments&utm_term=PennyLaneAI#diff-cGVubnlsYW5lL3Fhb2EvY3ljbGUucHk=) | `91.42% <90.62%> (-8.58%)` | :arrow_down: |

------

[Continue to review full report at Codecov](https://codecov.io/gh/PennyLaneAI/pennylane/pull/1214?src=pr&el=continue&utm_medium=referral&utm_source=github&utm_content=comment&utm_campaign=pr+comments&utm_term=PennyLaneAI).
> **Legend** - [Click here to learn more](https://docs.codecov.io/docs/codecov-delta?utm_medium=referral&utm_source=github&utm_content=comment&utm_campaign=pr+comments&utm_term=PennyLaneAI)
> `Δ = absolute <relative> (impact)`, `ø = not affected`, `? = missing data`
> Powered by [Codecov](https://codecov.io/gh/PennyLaneAI/pennylane/pull/1214?src=pr&el=footer&utm_medium=referral&utm_source=github&utm_content=comment&utm_campaign=pr+comments&utm_term=PennyLaneAI). Last update [a4548bf...2379f99](https://codecov.io/gh/PennyLaneAI/pennylane/pull/1214?src=pr&el=lastupdated&utm_medium=referral&utm_source=github&utm_content=comment&utm_campaign=pr+comments&utm_term=PennyLaneAI). Read the [comment docs](https://docs.codecov.io/docs/pull-request-comments?utm_medium=referral&utm_source=github&utm_content=comment&utm_campaign=pr+comments&utm_term=PennyLaneAI).

anthayes92: Applying `black --line-length 100 ./tests/test_qaoa.py` loacllay leaves file unformatted :thinking: .

Patch:
diff --git a/.github/CHANGELOG.md b/.github/CHANGELOG.md
index 94f4359f1..e79c28699 100644
--- a/.github/CHANGELOG.md
+++ b/.github/CHANGELOG.md
@@ -61,6 +61,7 @@
   [(#1209)](https://github.com/PennyLaneAI/pennylane/pull/1209)
   [(#1251)](https://github.com/PennyLaneAI/pennylane/pull/1251)
   [(#1213)](https://github.com/PennyLaneAI/pennylane/pull/1213)
+  [(#1214)](https://github.com/PennyLaneAI/pennylane/pull/1214)
 
 * Adds `QubitCarry` and `QubitSum` operations for basic arithmetic.
   [(#1169)](https://github.com/PennyLaneAI/pennylane/pull/1169)
diff --git a/pennylane/qaoa/cycle.py b/pennylane/qaoa/cycle.py
index 333197f29..fbedd0d12 100644
--- a/pennylane/qaoa/cycle.py
+++ b/pennylane/qaoa/cycle.py
@@ -306,3 +306,92 @@ def _square_hamiltonian_terms(
             squared_ops.append(op1 @ op2)
 
     return squared_coeffs, squared_ops
+
+
+def net_flow_constraint(graph: nx.DiGraph) -> qml.Hamiltonian:
+    r"""Calculates the `net flow constraint <https://doi.org/10.1080/0020739X.2010.526248>`__
+    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.,
+
+    .. math:: \sum_{j, (i, j) \in E} x_{ij} = \sum_{j, (j, i) \in E} x_{ji},
+
+    for all nodes :math:`i`, where :math:`E` are the edges of the graph and :math:`x_{ij}` is a
+    binary number that selects whether to include the edge :math:`(i, j)`.
+
+    A set of edges has zero net flow whenever the following Hamiltonian is minimized:
+
+    .. math::
+
+        \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 :math:`V` are the graph vertices, :math:`d_{i}^{\rm out}` and :math:`d_{i}^{\rm in}` are
+    the outdegree and indegree, respectively, of node :math:`i` and :math:`Z_{ij}` is a qubit
+    Pauli-Z matrix acting upon the wire specified by the pair :math:`(i, j)`. Mapping from edges to
+    wires can be achieved using :func:`~.edges_to_wires`.
+
+    Args:
+        graph (nx.DiGraph): the directed graph specifying possible edges
+
+    Returns:
+        qml.Hamiltonian: the net-flow constraint Hamiltonian
+
+    Raises:
+        ValueError: if the input graph is not directed
+    """
+    if not hasattr(graph, "in_edges") or not hasattr(graph, "out_edges"):
+        raise ValueError("Input graph must be directed")
+
+    hamiltonian = qml.Hamiltonian([], [])
+
+    for node in graph.nodes:
+        hamiltonian += _inner_net_flow_constraint_hamiltonian(graph, node)
+
+    return hamiltonian
+
+
+def _inner_net_flow_constraint_hamiltonian(graph: nx.DiGraph, node) -> qml.Hamiltonian:
+    r"""Calculates the squared inner portion of the Hamiltonian in :func:`net_flow_constraint`.
+
+    For a given :math:`i`, this function returns:
+
+    .. math::
+
+        \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}.
+
+    Args:
+        graph (nx.DiGraph): the directed graph specifying possible edges
+        node: a fixed node
+
+    Returns:
+        qml.Hamiltonian: The inner part of the net-flow constraint Hamiltonian.
+    """
+    edges_to_qubits = edges_to_wires(graph)
+
+    coeffs = []
+    ops = []
+
+    out_edges = graph.out_edges(node)
+    in_edges = graph.in_edges(node)
+
+    coeffs.append(len(out_edges) - len(in_edges))
+    ops.append(qml.Identity(0))
+
+    for edge in out_edges:
+        wires = (edges_to_qubits[edge],)
+        coeffs.append(-1)
+        ops.append(qml.PauliZ(wires))
+
+    for edge in in_edges:
+        wires = (edges_to_qubits[edge],)
+        coeffs.append(1)
+        ops.append(qml.PauliZ(wires))
+
+    coeffs, ops = _square_hamiltonian_terms(coeffs, ops)
+    H = qml.Hamiltonian(coeffs, ops)
+    H.simplify()
+
+    return H


Test patch:
diff --git a/tests/test_qaoa.py b/tests/test_qaoa.py
index c2daf9c4f..6a854ced8 100644
--- a/tests/test_qaoa.py
+++ b/tests/test_qaoa.py
@@ -25,6 +25,8 @@ from pennylane.wires import Wires
 from pennylane.qaoa.cycle import (
     edges_to_wires,
     wires_to_edges,
+    _inner_net_flow_constraint_hamiltonian,
+    net_flow_constraint,
     loss_hamiltonian,
     _square_hamiltonian_terms,
     cycle_mixer,
@@ -1061,3 +1063,102 @@ class TestCycles:
                 for op1, op2 in zip(expected_ops, squared_ops)
             ]
         )
+
+    def test_inner_net_flow_constraint_hamiltonian(self):
+        """Test if the _inner_net_flow_constraint_hamiltonian function returns the expected result on a manually-calculated
+        example of a 3-node complete digraph relative to the 0 node"""
+        g = nx.complete_graph(3).to_directed()
+        h = _inner_net_flow_constraint_hamiltonian(g, 0)
+
+        expected_ops = [
+            qml.Identity(0),
+            qml.PauliZ(0) @ qml.PauliZ(1),
+            qml.PauliZ(0) @ qml.PauliZ(2),
+            qml.PauliZ(0) @ qml.PauliZ(4),
+            qml.PauliZ(1) @ qml.PauliZ(2),
+            qml.PauliZ(1) @ qml.PauliZ(4),
+            qml.PauliZ(2) @ qml.PauliZ(4),
+        ]
+        expected_coeffs = [4, 2, -2, -2, -2, -2, 2]
+
+        assert expected_coeffs == h.coeffs
+        for i, expected_op in enumerate(expected_ops):
+            assert str(h.ops[i]) == str(expected_op)
+        assert all([op.wires == exp.wires for op, exp in zip(h.ops, expected_ops)])
+
+    def test_inner_net_flow_constraint_hamiltonian_non_complete(self):
+        """Test if the _inner_net_flow_constraint_hamiltonian function returns the expected result on a manually-calculated
+        example of a 3-node complete digraph relative to the 0 node, with the (1, 0) edge removed"""
+        g = nx.complete_graph(3).to_directed()
+        g.remove_edge(1, 0)
+        h = _inner_net_flow_constraint_hamiltonian(g, 0)
+
+        expected_ops = [
+            qml.Identity(0),
+            qml.PauliZ(0),
+            qml.PauliZ(1),
+            qml.PauliZ(3),
+            qml.PauliZ(0) @ qml.PauliZ(1),
+            qml.PauliZ(0) @ qml.PauliZ(3),
+            qml.PauliZ(1) @ qml.PauliZ(3),
+        ]
+        expected_coeffs = [4, -2, -2, 2, 2, -2, -2]
+
+        assert expected_coeffs == h.coeffs
+        for i, expected_op in enumerate(expected_ops):
+            assert str(h.ops[i]) == str(expected_op)
+        assert all([op.wires == exp.wires for op, exp in zip(h.ops, expected_ops)])
+
+    def test_net_flow_constraint(self):
+        """Test if the net_flow_constraint Hamiltonian is minimized by states that correspond to a
+        collection of edges with zero flow"""
+        g = nx.complete_graph(3).to_directed()
+        h = net_flow_constraint(g)
+        m = wires_to_edges(g)
+        wires = len(g.edges)
+
+        # We use PL to find the energies corresponding to each possible bitstring
+        dev = qml.device("default.qubit", wires=wires)
+
+        def energy(basis_state, **kwargs):
+            qml.BasisState(basis_state, wires=range(wires))
+
+        cost = qml.ExpvalCost(energy, h, dev, optimize=True)
+
+        # Calculate the set of all bitstrings
+        states = itertools.product([0, 1], repeat=wires)
+
+        # Calculate the corresponding energies
+        energies_states = ((cost(state).numpy(), state) for state in states)
+
+        # We now have the energies of each bitstring/state. We also want to calculate the net flow of
+        # the corresponding edges
+        for energy, state in energies_states:
+
+            # This part converts from a binary string of wires selected to graph edges
+            wires_ = tuple(i for i, s in enumerate(state) if s != 0)
+            edges = tuple(m[w] for w in wires_)
+
+            # Calculates the number of edges entering and leaving a given node
+            in_flows = np.zeros(len(g.nodes))
+            out_flows = np.zeros(len(g.nodes))
+
+            for e in edges:
+                in_flows[e[0]] += 1
+                out_flows[e[1]] += 1
+
+            net_flow = np.sum(np.abs(in_flows - out_flows))
+
+            # The test requires that a set of edges with zero net flow must have a corresponding
+            # bitstring that minimized the energy of the Hamiltonian
+            if net_flow == 0:
+                assert energy == min(energies_states)[0]
+            else:
+                assert energy > min(energies_states)[0]
+
+    def test_net_flow_constraint_undirected_raises_error(self):
+        """Test `net_flow_constraint` raises ValueError if input graph is not directed"""
+        g = nx.complete_graph(3)  # undirected graph
+
+        with pytest.raises(ValueError):
+            h = net_flow_constraint(g)