Repository: PennyLaneAI/pennylane
Pull request #1207 (2021-04-13 15:50:43)

QAOA cycle module
Begin module to enable users to find max weighted cycle of directed graphs using QAOA.

Add initial helper functions to translate edges of directed graph to a corresponding wire and vice versa.


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/1207?src=pr&el=h1&utm_medium=referral&utm_source=github&utm_content=comment&utm_campaign=pr+comments&utm_term=PennyLaneAI) Report
> Merging [#1207](https://codecov.io/gh/PennyLaneAI/pennylane/pull/1207?src=pr&el=desc&utm_medium=referral&utm_source=github&utm_content=comment&utm_campaign=pr+comments&utm_term=PennyLaneAI) (a4548bf) into [master](https://codecov.io/gh/PennyLaneAI/pennylane/commit/e17dc373c32530dfb2fdba8d90f584f314e23cc0?el=desc&utm_medium=referral&utm_source=github&utm_content=comment&utm_campaign=pr+comments&utm_term=PennyLaneAI) (e17dc37) will **increase** coverage by `0.00%`.
> The diff coverage is `100.00%`.

[![Impacted file tree graph](https://codecov.io/gh/PennyLaneAI/pennylane/pull/1207/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/1207?src=pr&el=tree&utm_medium=referral&utm_source=github&utm_content=comment&utm_campaign=pr+comments&utm_term=PennyLaneAI)

```diff
@@           Coverage Diff           @@
##           master    #1207   +/-   ##
=======================================
  Coverage   98.12%   98.12%           
=======================================
  Files         145      146    +1     
  Lines       10985    10992    +7     
=======================================
+ Hits        10779    10786    +7     
  Misses        206      206           
```


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

------

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

josh146: @anthayes92 don't forget to update the changelog before merging this in!
josh146: > @josh146, we've got a few PRs coming in for this feature and were thinking to update the changelog once a few more have come in.

No worries, worth having a 'TBD' section in the changelog, just so this PR isn't forgotten?

Patch:
diff --git a/.github/CHANGELOG.md b/.github/CHANGELOG.md
index 261fdfc3f..c516f4d34 100644
--- a/.github/CHANGELOG.md
+++ b/.github/CHANGELOG.md
@@ -2,6 +2,9 @@
 
 <h3>New features since last release</h3>
 
+* TBD: Add `qml.qaoa.cycle` (when structure is finalised)
+  [(#1207)](https://github.com/PennyLaneAI/pennylane/pull/1207)
+
 * Adds `QubitCarry` and `QubitSum` operations for basic arithmetic.
   [(#1169)](https://github.com/PennyLaneAI/pennylane/pull/1169)
 
@@ -46,7 +49,8 @@
 
 This release contains contributions from:
 
-Thomas Bromley, Diego Guala 
+Thomas Bromley, Diego Guala, Anthony Hayes
+
 
 # Release 0.15.0 (current release)
 
@@ -127,7 +131,7 @@ Thomas Bromley, Diego Guala
 
 - The number of shots can now be specified on a per-call basis when evaluating a QNode.
   [(#1075)](https://github.com/PennyLaneAI/pennylane/pull/1075).
-  
+
   For this, the qnode should be called with an additional `shots` keyword argument:
 
   ```pycon
@@ -152,7 +156,7 @@ which contains *differentiable quantum transforms*. These are functions that act
 on QNodes, quantum functions, devices, and tapes, transforming them while remaining
 fully differentiable.
 
-* A new adjoint transform has been added. 
+* A new adjoint transform has been added.
   [(#1111)](https://github.com/PennyLaneAI/pennylane/pull/1111)
   [(#1135)](https://github.com/PennyLaneAI/pennylane/pull/1135)
 
@@ -250,15 +254,15 @@ fully differentiable.
 
 <h4>More operations and templates</h4>
 
-* Added the `SingleExcitation` two-qubit operation, which is useful for quantum 
+* Added the `SingleExcitation` two-qubit operation, which is useful for quantum
   chemistry applications.
   [(#1121)](https://github.com/PennyLaneAI/pennylane/pull/1121)
-  
-  It can be used to perform an SO(2) rotation in the subspace 
-  spanned by the states :math:`|01\rangle` and :math:`|10\rangle`. 
+
+  It can be used to perform an SO(2) rotation in the subspace
+  spanned by the states :math:`|01\rangle` and :math:`|10\rangle`.
   For example, the following circuit performs the transformation
   :math:`|10\rangle \rightarrow \cos(\phi/2)|10\rangle - \sin(\phi/2)|01\rangle`:    
-  
+
   ```python
   dev = qml.device('default.qubit', wires=2)
 
@@ -267,17 +271,17 @@ fully differentiable.
       qml.PauliX(wires=0)
       qml.SingleExcitation(phi, wires=[0, 1])
   ```
-  
+
   The `SingleExcitation` operation supports analytic gradients on hardware
   using only four expectation value calculations, following results from
-  [Kottmann et al.](https://arxiv.org/abs/2011.05938) 
-  
+  [Kottmann et al.](https://arxiv.org/abs/2011.05938)
+
 * Added the `DoubleExcitation` four-qubit operation, which is useful for quantum
   chemistry applications.
   [(#1123)](https://github.com/PennyLaneAI/pennylane/pull/1123)
 
-  It can be used to perform an SO(2) rotation in the subspace 
-  spanned by the states :math:`|1100\rangle` and :math:`|0011\rangle`. 
+  It can be used to perform an SO(2) rotation in the subspace
+  spanned by the states :math:`|1100\rangle` and :math:`|0011\rangle`.
   For example, the following circuit performs the transformation
   :math:`|1100\rangle\rightarrow \cos(\phi/2)|1100\rangle - \sin(\phi/2)|0011\rangle`:   
 
@@ -290,7 +294,7 @@ fully differentiable.
       qml.PauliX(wires=1)
       qml.DoubleExcitation(phi, wires=[0, 1, 2, 3])
   ```
-  
+
   The `DoubleExcitation` operation supports analytic gradients on hardware using only
   four expectation value calculations, following results from
   [Kottmann et al.](https://arxiv.org/abs/2011.05938).
@@ -301,7 +305,7 @@ fully differentiable.
 
   The following example shows how the expectation value of sine squared over a standard normal
   distribution can be approximated:
-  
+
   ```python
   from scipy.stats import norm
 
@@ -339,18 +343,18 @@ fully differentiable.
 * Added the `QuantumPhaseEstimation` template for performing quantum phase estimation for an input
   unitary matrix.
   [(#1095)](https://github.com/PennyLaneAI/pennylane/pull/1095)
-  
+
   Consider the matrix corresponding to a rotation from an `RX` gate:
-  
+
   ```pycon
   >>> phase = 5
   >>> target_wires = [0]
   >>> unitary = qml.RX(phase, wires=0).matrix
   ```
-  
+
   The ``phase`` parameter can be estimated using ``QuantumPhaseEstimation``. For example, using five
   phase-estimation qubits:
-  
+
   ```python
   n_estimation_wires = 5
   estimation_wires = range(1, n_estimation_wires + 1)
@@ -395,7 +399,7 @@ fully differentiable.
   mixed-polarity multi-controlled operation).
   [(#1069)](https://github.com/PennyLaneAI/pennylane/pull/1069)
   [(#1104)](https://github.com/PennyLaneAI/pennylane/pull/1104)
-  
+
   For example, we can  create a multi-controlled T gate using:
 
   ```python
@@ -414,13 +418,13 @@ fully differentiable.
   control qubits.
   [(#1104)](https://github.com/PennyLaneAI/pennylane/pull/1104)
 
-<h4>Support for higher-order derivatives on hardware</h4> 
+<h4>Support for higher-order derivatives on hardware</h4>
 
 * Computing second derivatives and Hessians of QNodes is now supported with
   the parameter-shift differentiation method, on all machine learning interfaces.
   [(#1130)](https://github.com/PennyLaneAI/pennylane/pull/1130)
   [(#1129)](https://github.com/PennyLaneAI/pennylane/pull/1129)
-  [(#1110)](https://github.com/PennyLaneAI/pennylane/pull/1110) 
+  [(#1110)](https://github.com/PennyLaneAI/pennylane/pull/1110)
 
   Hessians are computed using the parameter-shift rule, and can be
   evaluated on both hardware and simulator devices.
@@ -495,9 +499,9 @@ fully differentiable.
 
   ```python
   dev = qml.device("default.qubit", wires=2)
-  
+
   inputstate = [np.sqrt(0.2), np.sqrt(0.3), np.sqrt(0.4), np.sqrt(0.1)]
-  
+
   @qml.qnode(dev)
   def circuit():
       mottonen.MottonenStatePreparation(inputstate,wires=[0, 1])
@@ -508,7 +512,7 @@ fully differentiable.
 
   ```pycon
   >>> print(qml.draw(circuit)())
-  0: ──RY(1.57)──╭C─────────────╭C──╭C──╭C──┤ ⟨Z⟩ 
+  0: ──RY(1.57)──╭C─────────────╭C──╭C──╭C──┤ ⟨Z⟩
   1: ──RY(1.35)──╰X──RY(0.422)──╰X──╰X──╰X──┤   
   ```
 
@@ -516,22 +520,22 @@ fully differentiable.
 
   ```pycon
   >>> print(qml.draw(circuit)())
-  0: ──RY(1.57)──╭C─────────────╭C──┤ ⟨Z⟩ 
+  0: ──RY(1.57)──╭C─────────────╭C──┤ ⟨Z⟩
   1: ──RY(1.35)──╰X──RY(0.422)──╰X──┤   
   ```
 
 - The templates are now classes inheriting
-  from `Operation`, and define the ansatz in their `expand()` method. This 
-  change does not affect the user interface. 
+  from `Operation`, and define the ansatz in their `expand()` method. This
+  change does not affect the user interface.
   [(#1138)](https://github.com/PennyLaneAI/pennylane/pull/1138)
   [(#1156)](https://github.com/PennyLaneAI/pennylane/pull/1156)
   [(#1163)](https://github.com/PennyLaneAI/pennylane/pull/1163)
   [(#1192)](https://github.com/PennyLaneAI/pennylane/pull/1192)
 
   For convenience, some templates have a new method that returns the expected
-  shape of the trainable parameter tensor, which can be used to create 
+  shape of the trainable parameter tensor, which can be used to create
   random tensors.
-  
+
   ```python
   shape = qml.templates.BasicEntanglerLayers.shape(n_layers=2, n_wires=4)
   weights = np.random.random(shape)
@@ -606,7 +610,7 @@ fully differentiable.
 
 * When printing `qml.Hamiltonian` objects, the terms are sorted by number of wires followed by coefficients.
   [(#981)](https://github.com/PennyLaneAI/pennylane/pull/981)
-  
+
 * Adds `qml.math.conj` to the PennyLane math module.
   [(#1143)](https://github.com/PennyLaneAI/pennylane/pull/1143)
 
@@ -631,34 +635,34 @@ fully differentiable.
 
 <h3>Breaking changes</h3>
 
-* Devices do not have an `analytic` argument or attribute anymore. 
-  Instead, `shots` is the source of truth for whether a simulator 
-  estimates return values from a finite number of shots, or whether 
+* Devices do not have an `analytic` argument or attribute anymore.
+  Instead, `shots` is the source of truth for whether a simulator
+  estimates return values from a finite number of shots, or whether
   it returns analytic results (`shots=None`).
   [(#1079)](https://github.com/PennyLaneAI/pennylane/pull/1079)
   [(#1196)](https://github.com/PennyLaneAI/pennylane/pull/1196)
-  
+
   ```python  
   dev_analytic = qml.device('default.qubit', wires=1, shots=None)
   dev_finite_shots = qml.device('default.qubit', wires=1, shots=1000)
-  
+
   def circuit():
       qml.Hadamard(wires=0)
       return qml.expval(qml.PauliZ(wires=0))
-  
+
   circuit_analytic = qml.QNode(circuit, dev_analytic)
   circuit_finite_shots = qml.QNode(circuit, dev_finite_shots)
   ```
-  
+
   Devices with `shots=None` return deterministic, exact results:
-  
+
   ```pycon
   >>> circuit_analytic()
   0.0
   >>> circuit_analytic()
   0.0
   ```
-  Devices with `shots > 0` return stochastic results estimated from 
+  Devices with `shots > 0` return stochastic results estimated from
   samples in each run:
 
   ```pycon
@@ -667,9 +671,9 @@ fully differentiable.
   >>> circuit_finite_shots()
   0.034
   ```
-  
-  The `qml.sample()` measurement can only be used on devices on which the number 
-  of shots is set explicitly. 
+
+  The `qml.sample()` measurement can only be used on devices on which the number
+  of shots is set explicitly.
 
 * If creating a QNode from a quantum function with an argument named `shots`,
   a `DeprecationWarning` is raised, warning the user that this is a reserved
@@ -743,8 +747,8 @@ fully differentiable.
   being updated.
   [(#1126)](https://github.com/PennyLaneAI/pennylane/pull/1126)
 
-* Fixes a bug where `BasisEmbedding` would not accept inputs whose bits are all ones 
-  or all zeros. 
+* Fixes a bug where `BasisEmbedding` would not accept inputs whose bits are all ones
+  or all zeros.
   [(#1114)](https://github.com/PennyLaneAI/pennylane/pull/1114)
 
 * The `ExpvalCost` class raises an error if instantiated
diff --git a/doc/code/qml_qaoa.rst b/doc/code/qml_qaoa.rst
index 9a0a50888..dd4f7abc1 100644
--- a/doc/code/qml_qaoa.rst
+++ b/doc/code/qml_qaoa.rst
@@ -92,3 +92,11 @@ QAOA Layers
     :no-heading:
     :no-inheritance-diagram:
     :no-inherited-members:
+
+Cycle Optimization
+------------------
+
+.. automodapi:: pennylane.qaoa.cycle
+    :no-heading:
+    :no-inheritance-diagram:
+    :no-inherited-members:
diff --git a/pennylane/qaoa/cycle.py b/pennylane/qaoa/cycle.py
new file mode 100644
index 000000000..a4c033772
--- /dev/null
+++ b/pennylane/qaoa/cycle.py
@@ -0,0 +1,77 @@
+# Copyright 2021 Xanadu Quantum Technologies Inc.
+
+# Licensed under the Apache License, Version 2.0 (the "License");
+# you may not use this file except in compliance with the License.
+# You may obtain a copy of the License at
+
+#     http://www.apache.org/licenses/LICENSE-2.0
+
+# Unless required by applicable law or agreed to in writing, software
+# distributed under the License is distributed on an "AS IS" BASIS,
+# WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
+# See the License for the specific language governing permissions and
+# limitations under the License.
+r"""
+Functionality for finding the maximum weighted cycle of directed graphs.
+"""
+
+from typing import Dict, Tuple
+import networkx as nx
+
+
+def edges_to_wires(graph: nx.Graph) -> Dict[Tuple, int]:
+    r"""Maps the edges of a graph to corresponding wires.
+
+    **Example**
+
+    >>> g = nx.complete_graph(4).to_directed()
+    >>> edges_to_wires(g)
+    {(0, 1): 0,
+     (0, 2): 1,
+     (0, 3): 2,
+     (1, 0): 3,
+     (1, 2): 4,
+     (1, 3): 5,
+     (2, 0): 6,
+     (2, 1): 7,
+     (2, 3): 8,
+     (3, 0): 9,
+     (3, 1): 10,
+     (3, 2): 11}
+
+    Args:
+        graph (nx.Graph): the graph specifying possible edges
+
+    Returns:
+        Dict[Tuple, int]: a mapping from graph edges to wires
+    """
+    return {edge: i for i, edge in enumerate(graph.edges)}
+
+
+def wires_to_edges(graph: nx.Graph) -> Dict[int, Tuple]:
+    r"""Maps the wires of a register of qubits to corresponding edges.
+
+    **Example**
+
+    >>> g = nx.complete_graph(4).to_directed()
+    >>> wires_to_edges(g)
+    {0: (0, 1),
+     1: (0, 2),
+     2: (0, 3),
+     3: (1, 0),
+     4: (1, 2),
+     5: (1, 3),
+     6: (2, 0),
+     7: (2, 1),
+     8: (2, 3),
+     9: (3, 0),
+     10: (3, 1),
+     11: (3, 2)}
+
+    Args:
+        graph (nx.Graph): the graph specifying possible edges
+
+    Returns:
+        Dict[Tuple, int]: a mapping from wires to graph edges
+    """
+    return {i: edge for i, edge in enumerate(graph.edges)}


Test patch:
diff --git a/tests/test_qaoa.py b/tests/test_qaoa.py
index 7e3ea2ff5..ab05c3043 100644
--- a/tests/test_qaoa.py
+++ b/tests/test_qaoa.py
@@ -16,11 +16,12 @@ Unit tests for the :mod:`pennylane.qaoa` submodule.
 """
 import pytest
 import numpy as np
+import networkx as nx
 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
 
 #####################################################
 
@@ -676,3 +677,65 @@ class TestIntegration:
         expected = -1.8260274380964299
 
         assert np.allclose(res, expected, atol=tol, rtol=0)
+
+
+class TestCycles:
+    """Tests that ``cycle`` module functions are behaving correctly"""
+
+    def test_edges_to_wires(self):
+        """Test that edges_to_wires returns the correct mapping"""
+        g = nx.lollipop_graph(4, 1)
+        r = edges_to_wires(g)
+
+        assert r == {(0, 1): 0, (0, 2): 1, (0, 3): 2, (1, 2): 3, (1, 3): 4, (2, 3): 5, (3, 4): 6}
+
+    def test_wires_to_edges(self):
+        """Test that wires_to_edges returns the correct mapping"""
+        g = nx.lollipop_graph(4, 1)
+        r = wires_to_edges(g)
+
+        assert r == {0: (0, 1), 1: (0, 2), 2: (0, 3), 3: (1, 2), 4: (1, 3), 5: (2, 3), 6: (3, 4)}
+
+    def test_edges_to_wires_directed(self):
+        """Test that edges_to_wires returns the correct mapping on a directed graph"""
+        g = nx.lollipop_graph(4, 1).to_directed()
+        r = edges_to_wires(g)
+
+        assert r == {
+            (0, 1): 0,
+            (0, 2): 1,
+            (0, 3): 2,
+            (1, 0): 3,
+            (1, 2): 4,
+            (1, 3): 5,
+            (2, 0): 6,
+            (2, 1): 7,
+            (2, 3): 8,
+            (3, 0): 9,
+            (3, 1): 10,
+            (3, 2): 11,
+            (3, 4): 12,
+            (4, 3): 13,
+        }
+
+    def test_wires_to_edges_directed(self):
+        """Test that wires_to_edges returns the correct mapping on a directed graph"""
+        g = nx.lollipop_graph(4, 1).to_directed()
+        r = wires_to_edges(g)
+
+        assert r == {
+            0: (0, 1),
+            1: (0, 2),
+            2: (0, 3),
+            3: (1, 0),
+            4: (1, 2),
+            5: (1, 3),
+            6: (2, 0),
+            7: (2, 1),
+            8: (2, 3),
+            9: (3, 0),
+            10: (3, 1),
+            11: (3, 2),
+            12: (3, 4),
+            13: (4, 3),
+        }