Repository: PennyLaneAI/pennylane (python)

Issue:
[unitaryhack] Define decomposition for `qml.Toffoli`
*This issue has been tagged for contributions during [unitaryHACK](https://unitaryfund.github.io/unitaryhack/participating-projects.html)*

Each PennyLane operation defines a decomposition. The decomposition of an operation is an ordered list of other operations. Applying this list of operations evolves quantum states the same way as applying the operation itself does. In most cases, this list includes elementary gates that are often supported by most quantum devices.

We would like to add the decomposition of the `qml.Toffoli` operation by:
1. Defining the decomposition method for [the `qml.Toffoli` operation](https://github.com/PennyLaneAI/pennylane/blob/1930230dde60112ad90af0951fa9295d374e1adf/pennylane/ops/qubit.py#L630) that has the following signature:
```python
    @staticmethod
    def decomposition(wires):
```
Other operations in the `pennylane/ops/qubit.py` file can serve as an example for defining this method (e.g., [see `qml.Hadamard`](https://github.com/PennyLaneAI/pennylane/blob/1930230dde60112ad90af0951fa9295d374e1adf/pennylane/ops/qubit.py#L87)).
2. Including a test case for the decomposition of `qml.Toffoli` in the `tests/ops/test_qubit_ops.py` file to verify its correctness.

Pull request:
[unitaryHACK] Toffoli Decomposition
**Context:**
Added Toffoli decomposition along with tests

**Description of the Change:**
The Toffoli decomposition is done by using Hadamard, CNOT, T and T.inv() gates according to the following circuit
![image](https://user-images.githubusercontent.com/62295887/118373479-b1771e00-b5d4-11eb-989d-1fc31d168464.png)

Made changes in `pennylane/ops/qubit.py` and `tests/ops/test_qubit_ops.py`

*Note*: the tape expansion in some test files (`tests/ops/test_qubit_ops.py` and `tests/transforms/test_control.py`) were adjusted. This was required because the test cases assumed that Toffoli had no decomposition, yielded incorrect results and failed the tests.

**Benefits:**
The user can now see the decomposition of the Toffoli gate into simpler gates

**Related GitHub Issues:**
Fixes #1305 

Patch:
diff --git a/.github/CHANGELOG.md b/.github/CHANGELOG.md
index b15e59151..3aafaae7c 100644
--- a/.github/CHANGELOG.md
+++ b/.github/CHANGELOG.md
@@ -2,6 +2,9 @@
 
 <h3>New features since last release</h3>
 
+* The `qml.Toffoli` operation now has a decomposition over elementary gates. 
+  [(#1320)](https://github.com/PennyLaneAI/pennylane/pull/1320)
+
 * The `qml.SWAP`  operation now has a decomposition over elementary gates. [(#1329)](https://github.com/PennyLaneAI/pennylane/pull/1329)
 
 * Added functionality for constructing and manipulating the Pauli group
diff --git a/pennylane/ops/qubit.py b/pennylane/ops/qubit.py
index 8ae55f07b..f770a9f79 100644
--- a/pennylane/ops/qubit.py
+++ b/pennylane/ops/qubit.py
@@ -684,6 +684,27 @@ class Toffoli(Operation):
     def _matrix(cls, *params):
         return cls.matrix
 
+    @staticmethod
+    def decomposition(wires):
+        decomp_ops = [
+            Hadamard(wires=wires[2]),
+            CNOT(wires=[wires[1], wires[2]]),
+            T(wires=wires[2]).inv(),
+            CNOT(wires=[wires[0], wires[2]]),
+            T(wires=wires[2]),
+            CNOT(wires=[wires[1], wires[2]]),
+            T(wires=wires[2]).inv(),
+            CNOT(wires=[wires[0], wires[2]]),
+            T(wires=wires[2]),
+            T(wires=wires[1]),
+            CNOT(wires=[wires[0], wires[1]]),
+            Hadamard(wires=wires[2]),
+            T(wires=wires[0]),
+            T(wires=wires[1]).inv(),
+            CNOT(wires=[wires[0], wires[1]]),
+        ]
+        return decomp_ops
+
     def adjoint(self):
         return Toffoli(wires=self.wires)
 


Test patch:
diff --git a/tests/ops/test_qubit_ops.py b/tests/ops/test_qubit_ops.py
index 57a967032..a9f38626e 100644
--- a/tests/ops/test_qubit_ops.py
+++ b/tests/ops/test_qubit_ops.py
@@ -685,6 +685,46 @@ class TestOperations:
 
         assert np.allclose(decomposed_matrix, op.matrix, atol=tol, rtol=0)
 
+    def test_toffoli_decomposition(self, tol):
+        """Tests that the decomposition of the Toffoli gate is correct"""
+        op = qml.Toffoli(wires=[0, 1, 2])
+        res = op.decomposition(op.wires)
+
+        assert len(res) == 15
+
+        mats = []
+
+        for i in reversed(res):
+            if i.wires == Wires([2]):
+                mats.append(np.kron(np.eye(4), i.matrix))
+            elif i.wires == Wires([1]):
+                mats.append(np.kron(np.eye(2), np.kron(i.matrix, np.eye(2))))
+            elif i.wires == Wires([0]):
+                mats.append(np.kron(i.matrix, np.eye(4)))
+            elif i.wires == Wires([0, 1]) and i.name == "CNOT":
+                mats.append(np.kron(i.matrix, np.eye(2)))
+            elif i.wires == Wires([1, 2]) and i.name == "CNOT":
+                mats.append(np.kron(np.eye(2), i.matrix))
+            elif i.wires == Wires([0, 2]) and i.name == "CNOT":
+                mats.append(
+                    np.array(
+                        [
+                            [1, 0, 0, 0, 0, 0, 0, 0],
+                            [0, 1, 0, 0, 0, 0, 0, 0],
+                            [0, 0, 1, 0, 0, 0, 0, 0],
+                            [0, 0, 0, 1, 0, 0, 0, 0],
+                            [0, 0, 0, 0, 0, 1, 0, 0],
+                            [0, 0, 0, 0, 1, 0, 0, 0],
+                            [0, 0, 0, 0, 0, 0, 0, 1],
+                            [0, 0, 0, 0, 0, 0, 1, 0],
+                        ]
+                    )
+                )
+
+        decomposed_matrix = np.linalg.multi_dot(mats)
+
+        assert np.allclose(decomposed_matrix, op.matrix, atol=tol, rtol=0)
+
     def test_phase_shift(self, tol):
         """Test phase shift is correct"""
 
@@ -2401,7 +2441,7 @@ class TestMultiControlledX:
                 work_wires=work_wires,
                 control_values=control_values,
             )
-        tape = tape.expand(depth=2)
+        tape = tape.expand(depth=1)
         assert all(not isinstance(op, qml.MultiControlledX) for op in tape.operations)
 
         @qml.qnode(dev)
diff --git a/tests/transforms/test_control.py b/tests/transforms/test_control.py
index 73b3b1ea7..641d108c8 100644
--- a/tests/transforms/test_control.py
+++ b/tests/transforms/test_control.py
@@ -87,7 +87,7 @@ def test_nested_control():
     assert len(tape.operations) == 1
     op = tape.operations[0]
     assert isinstance(op, ControlledOperation)
-    new_tape = expand_tape(tape, 3)
+    new_tape = expand_tape(tape, 2)
     assert_equal_operations(new_tape.operations, [qml.Toffoli(wires=[7, 3, 0])])
 
 
@@ -99,7 +99,7 @@ def test_multi_control():
     assert len(tape.operations) == 1
     op = tape.operations[0]
     assert isinstance(op, ControlledOperation)
-    new_tape = expand_tape(tape, 3)
+    new_tape = expand_tape(tape, 1)
     assert_equal_operations(new_tape.operations, [qml.Toffoli(wires=[7, 3, 0])])