Repository: PennyLaneAI/pennylane

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.

Discussion:
josh146: Thanks for the contribution @tgag17! Someone from the team will be on hand shortly to provide a review. If you have any questions, feel free to let us know via comments within the PR.
tgag17: Hi! I have made the required formatting changes. Regarding the tests, I read in one of the issues that some of the tests are failing due to some of the existing test cases. Could you please confirm if the same thing is happening in this PR too?
Thanks!
josh146: Thanks @tgag17! I've updated this PR to include the fix for those failing tests, to see if it enables them to pass.
tgag17: Hi! I have made the required changes. Thank you @antalszava for the review. 
I think the PR is ready for a review
antalszava: Hi @tgag17 thank you for the update! It seems that the multi-controlled x rotations are depending on Toffoli and that seems to cause some tests failing. Will check and get back shortly.
antalszava: Hi @tgag17, could you:
1. change the following line:

https://github.com/PennyLaneAI/pennylane/blob/9777f09ca265074531dde26e38c1322c72381c39/tests/ops/test_qubit_ops.py#L2438

such that `depth=1` is used that is

```python
tape = tape.expand(depth=1)
```
--------
2. change the following line:

https://github.com/PennyLaneAI/pennylane/blob/9777f09ca265074531dde26e38c1322c72381c39/tests/transforms/test_control.py#L90
such that `expand_tape(tape, 2)` is used here
```python
new_tape = expand_tape(tape, 2) # We applied ctrl twice
```
--------
3. change the following line:
 https://github.com/PennyLaneAI/pennylane/blob/9777f09ca265074531dde26e38c1322c72381c39/tests/transforms/test_control.py#L102

such that `expand_tape(tape, 1)` is used, that is:
```python
new_tape = expand_tape(tape, 1) # We applied ctrl once
```
 These changes should help with passing the tests. These test cases depended on the Toffoli operation not having a decomposition, that's why they are failing now.
codecov[bot]: # [Codecov](https://codecov.io/gh/PennyLaneAI/pennylane/pull/1320?src=pr&el=h1&utm_medium=referral&utm_source=github&utm_content=comment&utm_campaign=pr+comments&utm_term=PennyLaneAI) Report
> Merging [#1320](https://codecov.io/gh/PennyLaneAI/pennylane/pull/1320?src=pr&el=desc&utm_medium=referral&utm_source=github&utm_content=comment&utm_campaign=pr+comments&utm_term=PennyLaneAI) (4136a85) into [master](https://codecov.io/gh/PennyLaneAI/pennylane/commit/6a2cf0a72303718b78abe4426822655b5db79b93?el=desc&utm_medium=referral&utm_source=github&utm_content=comment&utm_campaign=pr+comments&utm_term=PennyLaneAI) (6a2cf0a) will **increase** coverage by `0.00%`.
> The diff coverage is `100.00%`.

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

```diff
@@           Coverage Diff           @@
##           master    #1320   +/-   ##
=======================================
  Coverage   98.16%   98.16%           
=======================================
  Files         148      148           
  Lines       11452    11456    +4     
=======================================
+ Hits        11242    11246    +4     
  Misses        210      210           
```


| [Impacted Files](https://codecov.io/gh/PennyLaneAI/pennylane/pull/1320?src=pr&el=tree&utm_medium=referral&utm_source=github&utm_content=comment&utm_campaign=pr+comments&utm_term=PennyLaneAI) | Coverage Δ | |
|---|---|---|
| [pennylane/ops/qubit.py](https://codecov.io/gh/PennyLaneAI/pennylane/pull/1320/diff?src=pr&el=tree&utm_medium=referral&utm_source=github&utm_content=comment&utm_campaign=pr+comments&utm_term=PennyLaneAI#diff-cGVubnlsYW5lL29wcy9xdWJpdC5weQ==) | `98.51% <100.00%> (+<0.01%)` | :arrow_up: |

------

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

tgag17: Thank you for the review and all the help @antalszava!

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])])