Repository: PennyLaneAI/pennylane
Pull request #1553 (2021-08-18 13:17:39)

[Code together] Add matrix form to Grover Operator
Issue #1514

Add matrix attribute to Grover template.

antalszava: Hi @ingstra, thank you for the submission! :slightly_smiling_face: No clear preference for the approach, other than it producing the correct matrix representation. Overall, the more performant approach would be preferable, though this is not required for us to accept the solution. It could be nice to go with one of them and add further parts of the PR (e.g., testing). Also, don't forget to update the changelog with an entry about the addition and by adding yourself to the list of contributors. :slightly_smiling_face: 
codecov[bot]: # [Codecov](https://codecov.io/gh/PennyLaneAI/pennylane/pull/1553?src=pr&el=h1&utm_medium=referral&utm_source=github&utm_content=comment&utm_campaign=pr+comments&utm_term=PennyLaneAI) Report
> Merging [#1553](https://codecov.io/gh/PennyLaneAI/pennylane/pull/1553?src=pr&el=desc&utm_medium=referral&utm_source=github&utm_content=comment&utm_campaign=pr+comments&utm_term=PennyLaneAI) (ec1418a) into [master](https://codecov.io/gh/PennyLaneAI/pennylane/commit/2cae58d13df401024e24b10bf72d357559182803?el=desc&utm_medium=referral&utm_source=github&utm_content=comment&utm_campaign=pr+comments&utm_term=PennyLaneAI) (2cae58d) will **decrease** coverage by `0.47%`.
> The diff coverage is `39.13%`.

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

```diff
@@            Coverage Diff             @@
##           master    #1553      +/-   ##
==========================================
- Coverage   98.79%   98.31%   -0.48%     
==========================================
  Files         187      187              
  Lines       13395    13417      +22     
==========================================
- Hits        13233    13191      -42     
- Misses        162      226      +64     
```


| [Impacted Files](https://codecov.io/gh/PennyLaneAI/pennylane/pull/1553?src=pr&el=tree&utm_medium=referral&utm_source=github&utm_content=comment&utm_campaign=pr+comments&utm_term=PennyLaneAI) | Coverage Δ | |
|---|---|---|
| [pennylane/templates/subroutines/grover.py](https://codecov.io/gh/PennyLaneAI/pennylane/pull/1553/diff?src=pr&el=tree&utm_medium=referral&utm_source=github&utm_content=comment&utm_campaign=pr+comments&utm_term=PennyLaneAI#diff-cGVubnlsYW5lL3RlbXBsYXRlcy9zdWJyb3V0aW5lcy9ncm92ZXIucHk=) | `69.56% <39.13%> (-30.44%)` | :arrow_down: |
| [pennylane/beta/devices/numpy\_ops.py](https://codecov.io/gh/PennyLaneAI/pennylane/pull/1553/diff?src=pr&el=tree&utm_medium=referral&utm_source=github&utm_content=comment&utm_campaign=pr+comments&utm_term=PennyLaneAI#diff-cGVubnlsYW5lL2JldGEvZGV2aWNlcy9udW1weV9vcHMucHk=) | `67.79% <0.00%> (-32.21%)` | :arrow_down: |
| [pennylane/beta/devices/default\_tensor.py](https://codecov.io/gh/PennyLaneAI/pennylane/pull/1553/diff?src=pr&el=tree&utm_medium=referral&utm_source=github&utm_content=comment&utm_campaign=pr+comments&utm_term=PennyLaneAI#diff-cGVubnlsYW5lL2JldGEvZGV2aWNlcy9kZWZhdWx0X3RlbnNvci5weQ==) | `86.39% <0.00%> (-10.55%)` | :arrow_down: |

------

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

ingstra: > Hi @ingstra, thank you for the submission! slightly_smiling_face No clear preference for the approach, other than it producing the correct matrix representation. Overall, the more performant approach would be preferable, though this is not required for us to accept the solution. It could be nice to go with one of them and add further parts of the PR (e.g., testing). Also, don't forget to update the changelog with an entry about the addition and by adding yourself to the list of contributors. slightly_smiling_face

Ok! Where in the changelog should I write? Top? Bottom?
ingstra: Sorry for the billion commits, it's my first time...
antalszava: Hi @ingstra, no problem! We'll be taking a look at this, thank you! :)

Patch:
diff --git a/.github/CHANGELOG.md b/.github/CHANGELOG.md
index c342217bd..0970bb66d 100644
--- a/.github/CHANGELOG.md
+++ b/.github/CHANGELOG.md
@@ -84,6 +84,9 @@
 
 <h3>Improvements</h3>
 
+* Added the matrix attribute to `qml.templates.subroutines.GroverOperator`
+  [(#1553)](https://github.com/PennyLaneAI/pennylane/pull/1553)
+
 * The `tape.to_openqasm()` method now has a `measure_all` argument that specifies whether the
   serialized OpenQASM script includes computational basis measurements on all of the qubits or
   just those specified by the tape.
diff --git a/pennylane/templates/subroutines/grover.py b/pennylane/templates/subroutines/grover.py
index f3ae13494..ff5975259 100644
--- a/pennylane/templates/subroutines/grover.py
+++ b/pennylane/templates/subroutines/grover.py
@@ -14,6 +14,9 @@
 """
 Contains the Grover Operation template.
 """
+import itertools
+import functools
+import numpy as np
 import pennylane as qml
 from pennylane.operation import AnyWires, Operation
 from pennylane.ops import Hadamard, PauliZ, MultiControlledX
@@ -121,9 +124,30 @@ class GroverOperator(Operation):
                 wires=self.wires[-1],
                 work_wires=self.work_wires,
             )
+
             PauliZ(self.wires[-1])
 
             for wire in self.wires[:-1]:
                 Hadamard(wire)
 
         return tape
+
+    @property
+    def matrix(self):
+        # Redefine the property here to allow for a custom _matrix signature
+        mat = self._matrix(len(self.wires))
+        return mat
+
+    @classmethod
+    def _matrix(cls, *params):
+        num_wires = params[0]
+
+        # s1 = H|0>, Hadamard on a single qubit in the ground state
+        s1 = np.array([1, 1]) / np.sqrt(2)
+
+        # uniform superposition state |s>
+        s = functools.reduce(np.kron, list(itertools.repeat(s1, num_wires)))
+
+        # Grover diffusion operator
+        G = 2 * np.outer(s, s) - np.identity(2 ** num_wires)
+        return G


Test patch:
diff --git a/tests/templates/test_subroutines/test_grover.py b/tests/templates/test_subroutines/test_grover.py
index 8216d9959..1197174b5 100644
--- a/tests/templates/test_subroutines/test_grover.py
+++ b/tests/templates/test_subroutines/test_grover.py
@@ -17,6 +17,9 @@ Tests for the Grover Diffusion Operator template
 import pytest
 import numpy as np
 import pennylane as qml
+from pennylane.ops import Hadamard, PauliZ, MultiControlledX
+import functools
+import itertools
 
 
 def test_work_wires():
@@ -82,6 +85,91 @@ def decomposition_wires(wires):
     return wire_order
 
 
+@pytest.mark.parametrize("n_wires", [2, 4, 7])
+def test_grover_diffusion_matrix(n_wires):
+    """Test that the Grover diffusion matrix is the same as when constructed in a different way"""
+    wires = list(range(n_wires))
+
+    # Test-oracle
+    oracle = np.identity(2 ** n_wires)
+    oracle[0, 0] = -1
+
+    # s1 = H|0>, Hadamard on a single qubit in the ground state
+    s1 = np.array([1, 1]) / np.sqrt(2)
+
+    # uniform superposition state
+    s = functools.reduce(np.kron, list(itertools.repeat(s1, n_wires)))
+    # Grover matrix
+    G_matrix = qml.templates.GroverOperator(wires=wires).matrix
+
+    amplitudes = G_matrix @ oracle @ s
+    probs = amplitudes ** 2
+
+    # Create Grover diffusion matrix G in alternative way
+    oplist = list(itertools.repeat(Hadamard.matrix, n_wires - 1))
+    oplist.append(PauliZ.matrix)
+
+    ctrl_str = "0" * (n_wires - 1)
+    CX = MultiControlledX(
+        control_values=ctrl_str,
+        control_wires=wires[:-1],
+        wires=wires[-1],
+        work_wires=None,
+    ).matrix
+
+    M = functools.reduce(np.kron, oplist)
+    G = M @ CX @ M
+
+    amplitudes2 = G @ oracle @ s
+    probs2 = amplitudes2 ** 2
+
+    assert np.allclose(probs, probs2)
+
+
+def test_grover_diffusion_matrix_results():
+    """Test that the matrix gives the same result as when running the example in the documentation `here <https://pennylane.readthedocs.io/en/stable/code/api/pennylane.templates.subroutines.GroverOperator.html>`_"""
+    n_wires = 3
+    wires = list(range(n_wires))
+
+    def oracle():
+        qml.Hadamard(wires[-1])
+        qml.Toffoli(wires=wires)
+        qml.Hadamard(wires[-1])
+
+    dev = qml.device("default.qubit", wires=wires)
+
+    @qml.qnode(dev)
+    def GroverSearch(num_iterations=1):
+        for wire in wires:
+            qml.Hadamard(wire)
+
+        for _ in range(num_iterations):
+            oracle()
+            qml.templates.GroverOperator(wires=wires)
+        return qml.probs(wires)
+
+    # Get probabilities from example
+    probs_example = GroverSearch(num_iterations=1)
+
+    # Grover diffusion matrix
+    G_matrix = qml.templates.GroverOperator(wires=wires).matrix
+
+    oracle_matrix = np.identity(2 ** n_wires)
+    oracle_matrix[-1, -1] = -1
+
+    # s1 = H|0>, Hadamard on a single qubit in the ground state
+    s1 = np.array([1, 1]) / np.sqrt(2)
+
+    # uniform superposition state
+    s = functools.reduce(np.kron, list(itertools.repeat(s1, n_wires)))
+
+    amplitudes = G_matrix @ oracle_matrix @ s
+    # Check that the probabilities are the same
+    probs_matrix = amplitudes ** 2
+
+    assert np.allclose(probs_example, probs_matrix)
+
+
 @pytest.mark.parametrize("wires", ((0, 1, 2), ("a", "c", "b")))
 def test_expand(wires):
     """Asserts decomposition uses expected operations and wires"""