Repository: PennyLaneAI/pennylane
Pull request #1209 (2021-04-13 16:57:49)

add product of edge weight Hamiltonian and test
This Hamiltonian holds the edge weight information that is used in the cost function during optimisation to find the max weighted cycle in the directed graph of interest.  

Add function to generate this Hamiltonian. 

In the unconstrained QAOA approach penalty terms are added to this Hamiltonian
In the constrained QAOA approach, the penalty complexity is added to the accompanying mixer Hamiltonian

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/1209?src=pr&el=h1&utm_medium=referral&utm_source=github&utm_content=comment&utm_campaign=pr+comments&utm_term=PennyLaneAI) Report
> Merging [#1209](https://codecov.io/gh/PennyLaneAI/pennylane/pull/1209?src=pr&el=desc&utm_medium=referral&utm_source=github&utm_content=comment&utm_campaign=pr+comments&utm_term=PennyLaneAI) (533e920) 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.03%`.
> The diff coverage is `81.81%`.

[![Impacted file tree graph](https://codecov.io/gh/PennyLaneAI/pennylane/pull/1209/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/1209?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    #1209      +/-   ##
======================================================
- Coverage               98.12%   98.09%   -0.04%     
======================================================
  Files                     146      146              
  Lines                   10992    11014      +22     
======================================================
+ Hits                    10786    10804      +18     
- Misses                    206      210       +4     
```


| [Impacted Files](https://codecov.io/gh/PennyLaneAI/pennylane/pull/1209?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/1209/diff?src=pr&el=tree&utm_medium=referral&utm_source=github&utm_content=comment&utm_campaign=pr+comments&utm_term=PennyLaneAI#diff-cGVubnlsYW5lL3Fhb2EvY3ljbGUucHk=) | `86.20% <81.81%> (-13.80%)` | :arrow_down: |

------

[Continue to review full report at Codecov](https://codecov.io/gh/PennyLaneAI/pennylane/pull/1209?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/1209?src=pr&el=footer&utm_medium=referral&utm_source=github&utm_content=comment&utm_campaign=pr+comments&utm_term=PennyLaneAI). Last update [a4548bf...533e920](https://codecov.io/gh/PennyLaneAI/pennylane/pull/1209?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).


Patch:
diff --git a/.github/CHANGELOG.md b/.github/CHANGELOG.md
index c516f4d34..da49896b1 100644
--- a/.github/CHANGELOG.md
+++ b/.github/CHANGELOG.md
@@ -4,6 +4,7 @@
 
 * TBD: Add `qml.qaoa.cycle` (when structure is finalised)
   [(#1207)](https://github.com/PennyLaneAI/pennylane/pull/1207)
+  [(#1209)](https://github.com/PennyLaneAI/pennylane/pull/1209)
 
 * 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 a4c033772..2b347b10a 100644
--- a/pennylane/qaoa/cycle.py
+++ b/pennylane/qaoa/cycle.py
@@ -17,6 +17,8 @@ Functionality for finding the maximum weighted cycle of directed graphs.
 
 from typing import Dict, Tuple
 import networkx as nx
+import numpy as np
+import pennylane as qml
 
 
 def edges_to_wires(graph: nx.Graph) -> Dict[Tuple, int]:
@@ -75,3 +77,90 @@ def wires_to_edges(graph: nx.Graph) -> Dict[int, Tuple]:
         Dict[Tuple, int]: a mapping from wires to graph edges
     """
     return {i: edge for i, edge in enumerate(graph.edges)}
+
+
+def loss_hamiltonian(graph: nx.Graph) -> qml.Hamiltonian:
+    r"""Calculates the loss Hamiltonian for the maximum-weighted cycle problem.
+
+    We consider the problem of selecting a cycle from a graph that has the greatest product of edge
+    weights, as outlined `here <https://1qbit.com/whitepaper/arbitrage/>`__. The product of weights
+    of a subset of edges in a graph is given by
+
+    .. math:: P = \prod_{(i, j) \in E} x_{ij} c_{ij}
+
+    where :math:`E` are the edges of the graph, :math:`x_{ij}` is a binary number that selects
+    whether to include the edge :math:`(i, j)` and :math:`c_{ij}` is the corresponding edge weight.
+    Our objective is to maximimize :math:`P`, subject to selecting the :math:`x_{ij}` so that
+    our subset of edges composes a cycle.
+
+    The product of edge weights is maximized by equivalently considering
+
+    .. math:: \sum_{(i, j) \in E} x_{ij}\log c_{ij},
+
+    assuming :math:`c_{ij} > 0`.
+
+    This can be restated as a minimization of the expectation value of the following qubit
+    Hamiltonian:
+
+    .. math::
+
+        H = \sum_{(i, j) \in E} Z_{ij}\log c_{ij}.
+
+    where :math:`Z_{ij}` is a qubit Pauli-Z matrix acting upon the wire specified by the edge
+    :math:`(i, j)`. Mapping from edges to wires can be achieved using :func:`~.edges_to_wires`.
+
+    .. note::
+        The expectation value of the returned Hamiltonian :math:`H` is not equal to :math:`P`, but
+        minimizing the expectation value of :math:`H` is equivalent to maximizing :math:`P`.
+
+        Also note that the returned Hamiltonian does not impose that the selected set of edges is
+        a cycle. This constraint can be enforced using a penalty term or by selecting a QAOA
+        mixer Hamiltonian that only transitions between states that correspond to cycles.
+
+    **Example**
+
+    >>> import networkx as nx
+    >>> g = nx.complete_graph(3).to_directed()
+    >>> edge_weight_data = {edge: (i + 1) * 0.5 for i, edge in enumerate(g.edges)}
+    >>> for k, v in edge_weight_data.items():
+            g[k[0]][k[1]]["weight"] = v
+    >>> h = loss_hamiltonian(g)
+    >>> print(h)
+      (-0.6931471805599453) [Z0]
+    + (0.0) [Z1]
+    + (0.4054651081081644) [Z2]
+    + (0.6931471805599453) [Z3]
+    + (0.9162907318741551) [Z4]
+    + (1.0986122886681098) [Z5]
+
+    Args:
+        graph (nx.Graph): the graph specifying possible edges
+
+    Returns:
+        qml.Hamiltonian: the loss Hamiltonian
+
+    Raises:
+        ValueError: if the graph contains self-loops
+        KeyError: if one or more edges do not contain weight data
+    """
+    edges_to_qubits = edges_to_wires(graph)
+    coeffs = []
+    ops = []
+
+    edges_data = graph.edges(data=True)
+
+    for edge_data in edges_data:
+        edge = edge_data[:2]
+
+        if edge[0] == edge[1]:
+            raise ValueError("Graph contains self-loops")
+
+        try:
+            weight = edge_data[2]["weight"]
+        except KeyError as e:
+            raise KeyError(f"Edge {edge} does not contain weight data") from e
+
+        coeffs.append(np.log(weight))
+        ops.append(qml.PauliZ(wires=edges_to_qubits[edge]))
+
+    return qml.Hamiltonian(coeffs, ops)


Test patch:
diff --git a/tests/test_qaoa.py b/tests/test_qaoa.py
index ab05c3043..de170044a 100644
--- a/tests/test_qaoa.py
+++ b/tests/test_qaoa.py
@@ -21,7 +21,7 @@ import pennylane as qml
 from pennylane import qaoa
 from networkx import Graph
 from pennylane.wires import Wires
-from pennylane.qaoa.cycle import edges_to_wires, wires_to_edges
+from pennylane.qaoa.cycle import edges_to_wires, wires_to_edges, loss_hamiltonian
 
 #####################################################
 
@@ -739,3 +739,91 @@ class TestCycles:
             12: (3, 4),
             13: (4, 3),
         }
+
+    def test_loss_hamiltonian_complete(self):
+        """Test if the loss_hamiltonian function returns the expected result on a
+        manually-calculated example of a 3-node complete digraph"""
+        g = nx.complete_graph(3).to_directed()
+        edge_weight_data = {edge: (i + 1) * 0.5 for i, edge in enumerate(g.edges)}
+        for k, v in edge_weight_data.items():
+            g[k[0]][k[1]]["weight"] = v
+        h = loss_hamiltonian(g)
+
+        expected_ops = [
+            qml.PauliZ(0),
+            qml.PauliZ(1),
+            qml.PauliZ(2),
+            qml.PauliZ(3),
+            qml.PauliZ(4),
+            qml.PauliZ(5),
+        ]
+        expected_coeffs = [np.log(0.5), np.log(1), np.log(1.5), np.log(2), np.log(2.5), np.log(3)]
+
+        assert expected_coeffs == h.coeffs
+        assert all([op.wires == exp.wires for op, exp in zip(h.ops, expected_ops)])
+        assert all([type(op) is type(exp) for op, exp in zip(h.ops, expected_ops)])
+
+    def test_loss_hamiltonian_incomplete(self):
+        """Test if the loss_hamiltonian function returns the expected result on a
+        manually-calculated example of a 4-node incomplete digraph"""
+        g = nx.lollipop_graph(4, 1).to_directed()
+        edge_weight_data = {edge: (i + 1) * 0.5 for i, edge in enumerate(g.edges)}
+        for k, v in edge_weight_data.items():
+            g[k[0]][k[1]]["weight"] = v
+        h = loss_hamiltonian(g)
+
+        expected_ops = [
+            qml.PauliZ(0),
+            qml.PauliZ(1),
+            qml.PauliZ(2),
+            qml.PauliZ(3),
+            qml.PauliZ(4),
+            qml.PauliZ(5),
+            qml.PauliZ(6),
+            qml.PauliZ(7),
+            qml.PauliZ(8),
+            qml.PauliZ(9),
+            qml.PauliZ(10),
+            qml.PauliZ(11),
+            qml.PauliZ(12),
+            qml.PauliZ(13),
+        ]
+        expected_coeffs = [
+            np.log(0.5),
+            np.log(1),
+            np.log(1.5),
+            np.log(2),
+            np.log(2.5),
+            np.log(3),
+            np.log(3.5),
+            np.log(4),
+            np.log(4.5),
+            np.log(5),
+            np.log(5.5),
+            np.log(6),
+            np.log(6.5),
+            np.log(7),
+        ]
+
+        assert expected_coeffs == h.coeffs
+        assert all([op.wires == exp.wires for op, exp in zip(h.ops, expected_ops)])
+        assert all([type(op) is type(exp) for op, exp in zip(h.ops, expected_ops)])
+
+    def test_self_loop_raises_error(self):
+        """Test graphs with self loop raises ValueError"""
+        g = nx.complete_graph(3).to_directed()
+        edge_weight_data = {edge: (i + 1) * 0.5 for i, edge in enumerate(g.edges)}
+        for k, v in edge_weight_data.items():
+            g[k[0]][k[1]]["weight"] = v
+
+        g.add_edge(1, 1)  # add self loop
+
+        with pytest.raises(ValueError, match="Graph contains self-loops"):
+            loss_hamiltonian(g)
+
+    def test_missing_edge_weight_data_raises_error(self):
+        """Test graphs with no edge weight data raises `KeyError`"""
+        g = nx.complete_graph(3).to_directed()
+
+        with pytest.raises(KeyError, match="does not contain weight data"):
+            loss_hamiltonian(g)