Repository: PennyLaneAI/pennylane
Pull request #1960 (2021-12-01 10:52:39)

undo_swaps 
**Context:** The `Permute` operation uses many SWAP gates to be implemented. In [(#1324)](https://github.com/PennyLaneAI/pennylane/issues/1324) a study was proposed to make this operator native to `default_qubit` in order to make the circuit more efficient. Instead, I have created a transformation that removes all the SWAP gates from the circuit by playing with the wires of the operations. I think it is a more efficient and flexible solution. 

**Description of the Change:** 
With a single reading of the circuit from right to left, all SWAPS in the circuit can be eliminated.

**Example**:

Without `undo_swaps`:

```python
import pennylane as qml
dev = qml.device('default.qubit', wires=3)

@qml.qnode(dev)
def qfunc():
    qml.Hadamard(wires=0)
    qml.PauliX(wires=1)
    qml.SWAP(wires=[0,1])
    qml.SWAP(wires=[0,2])
    qml.PauliY(wires=0)
    return qml.expval(qml.PauliZ(0))

print(qml.draw(qfunc)())
```
 0: ──H──╭SWAP──╭SWAP──Y──┤ ⟨Z⟩ 
 1: ──X──╰SWAP──│────────┤     
 2: ──────────╰SWAP─────┤  

With `undo_swaps`:

```python
@qml.qnode(dev)
@qml.transforms.undo_swaps
def qfunc():
    qml.Hadamard(wires=0)
    qml.PauliX(wires=1)
    qml.SWAP(wires=[0,1])
    qml.SWAP(wires=[0,2])
    qml.PauliY(wires=0)
    return qml.expval(qml.PauliZ(0))

print(qml.draw(qfunc)())
```

 0: ──Y──┤ ⟨Z⟩ 
 1: ──H──┤     
 2: ──X──┤


**Benefits:** 
The computational cost of the circuit calculation is reduced.

**Related GitHub Issues:**
[(#1324)](https://github.com/PennyLaneAI/pennylane/issues/1324) 


codecov[bot]: # [Codecov](https://codecov.io/gh/PennyLaneAI/pennylane/pull/1960?src=pr&el=h1&utm_medium=referral&utm_source=github&utm_content=comment&utm_campaign=pr+comments&utm_term=PennyLaneAI) Report
> Merging [#1960](https://codecov.io/gh/PennyLaneAI/pennylane/pull/1960?src=pr&el=desc&utm_medium=referral&utm_source=github&utm_content=comment&utm_campaign=pr+comments&utm_term=PennyLaneAI) (74d021c) into [master](https://codecov.io/gh/PennyLaneAI/pennylane/commit/42482b1dc2d93a5ce1b8aea4d1c6dd39713d6547?el=desc&utm_medium=referral&utm_source=github&utm_content=comment&utm_campaign=pr+comments&utm_term=PennyLaneAI) (42482b1) will **increase** coverage by `0.00%`.
> The diff coverage is `100.00%`.

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

```diff
@@           Coverage Diff           @@
##           master    #1960   +/-   ##
=======================================
  Coverage   98.81%   98.81%           
=======================================
  Files         225      226    +1     
  Lines       17187    17222   +35     
=======================================
+ Hits        16983    17018   +35     
  Misses        204      204           
```


| [Impacted Files](https://codecov.io/gh/PennyLaneAI/pennylane/pull/1960?src=pr&el=tree&utm_medium=referral&utm_source=github&utm_content=comment&utm_campaign=pr+comments&utm_term=PennyLaneAI) | Coverage Δ | |
|---|---|---|
| [pennylane/transforms/\_\_init\_\_.py](https://codecov.io/gh/PennyLaneAI/pennylane/pull/1960/diff?src=pr&el=tree&utm_medium=referral&utm_source=github&utm_content=comment&utm_campaign=pr+comments&utm_term=PennyLaneAI#diff-cGVubnlsYW5lL3RyYW5zZm9ybXMvX19pbml0X18ucHk=) | `100.00% <ø> (ø)` | |
| [pennylane/transforms/optimization/\_\_init\_\_.py](https://codecov.io/gh/PennyLaneAI/pennylane/pull/1960/diff?src=pr&el=tree&utm_medium=referral&utm_source=github&utm_content=comment&utm_campaign=pr+comments&utm_term=PennyLaneAI#diff-cGVubnlsYW5lL3RyYW5zZm9ybXMvb3B0aW1pemF0aW9uL19faW5pdF9fLnB5) | `100.00% <100.00%> (ø)` | |
| [pennylane/transforms/optimization/undo\_swaps.py](https://codecov.io/gh/PennyLaneAI/pennylane/pull/1960/diff?src=pr&el=tree&utm_medium=referral&utm_source=github&utm_content=comment&utm_campaign=pr+comments&utm_term=PennyLaneAI#diff-cGVubnlsYW5lL3RyYW5zZm9ybXMvb3B0aW1pemF0aW9uL3VuZG9fc3dhcHMucHk=) | `100.00% <100.00%> (ø)` | |

------

[Continue to review full report at Codecov](https://codecov.io/gh/PennyLaneAI/pennylane/pull/1960?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/1960?src=pr&el=footer&utm_medium=referral&utm_source=github&utm_content=comment&utm_campaign=pr+comments&utm_term=PennyLaneAI). Last update [42482b1...74d021c](https://codecov.io/gh/PennyLaneAI/pennylane/pull/1960?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: very nice solution!
KetpuntoG: > very nice solution!

Thanks @josh146 😊
KetpuntoG: [sc-11831]

Patch:
diff --git a/doc/releases/changelog-dev.md b/doc/releases/changelog-dev.md
index 2d1e06fa9..c9d330dd2 100644
--- a/doc/releases/changelog-dev.md
+++ b/doc/releases/changelog-dev.md
@@ -350,6 +350,9 @@
 * The `merge_amplitude_embedding` transformation has been created to automatically merge all gates of this type into one.
   [(#1933)](https://github.com/PennyLaneAI/pennylane/pull/1933)
 
+* The `undo_swaps` transformation has been created to automatically remove all swaps of a circuit.
+  [(#1960)](https://github.com/PennyLaneAI/pennylane/pull/1960)
+
 <h3>Improvements</h3>
 
 * Change all instances of `"{}".format(..)` to `f"{..}"`.
diff --git a/pennylane/transforms/__init__.py b/pennylane/transforms/__init__.py
index b3908df52..5b810f613 100644
--- a/pennylane/transforms/__init__.py
+++ b/pennylane/transforms/__init__.py
@@ -67,6 +67,9 @@ This set of transforms accept quantum functions, and perform basic circuit compi
     ~transforms.merge_rotations
     ~transforms.single_qubit_fusion
     ~transforms.unitary_to_rot
+    ~transforms.merge_amplitude_embedding
+    ~transforms.remove_barrier
+    ~transforms.undo_swaps
 
 There are also utility functions and decompositions available that assist with
 both transforms, and decompositions within the larger PennyLane codebase.
@@ -131,6 +134,7 @@ from .optimization import (
     single_qubit_fusion,
     merge_amplitude_embedding,
     remove_barrier,
+    undo_swaps,
 )
 from .specs import specs
 from .qmc import apply_controlled_Q, quantum_monte_carlo
diff --git a/pennylane/transforms/optimization/__init__.py b/pennylane/transforms/optimization/__init__.py
index d1d5a93be..f5714cd74 100644
--- a/pennylane/transforms/optimization/__init__.py
+++ b/pennylane/transforms/optimization/__init__.py
@@ -21,3 +21,4 @@ from .commute_controlled import commute_controlled
 from .merge_rotations import merge_rotations
 from .merge_amplitude_embedding import merge_amplitude_embedding
 from .single_qubit_fusion import single_qubit_fusion
+from .undo_swaps import undo_swaps
diff --git a/pennylane/transforms/optimization/undo_swaps.py b/pennylane/transforms/optimization/undo_swaps.py
new file mode 100644
index 000000000..50891fdc6
--- /dev/null
+++ b/pennylane/transforms/optimization/undo_swaps.py
@@ -0,0 +1,108 @@
+# Copyright 2018-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.
+
+"""Transform that eliminates the swap operators by reordering the wires."""
+# pylint: disable=too-many-branches
+from pennylane import apply
+from pennylane.transforms import qfunc_transform
+from pennylane.wires import Wires
+from pennylane.tape import stop_recording
+
+
+@qfunc_transform
+def undo_swaps(tape):
+    """Quantum function transform to remove SWAP gates by running from right
+    to left through the circuit changing the position of the qubits accordingly.
+
+    Args:
+        qfunc (function): A quantum function.
+
+    Returns:
+        function: the transformed quantum function
+
+    **Example**
+
+    Consider the following quantum function:
+
+    .. code-block:: python
+
+        def qfunc():
+            qml.Hadamard(wires=0)
+            qml.PauliX(wires=1)
+            qml.SWAP(wires=[0,1])
+            qml.SWAP(wires=[0,2])
+            qml.PauliY(wires=0)
+            return qml.expval(qml.PauliZ(0))
+
+    The circuit before optimization:
+
+    >>> dev = qml.device('default.qubit', wires=3)
+    >>> qnode = qml.QNode(qfunc, dev)
+    >>> print(qml.draw(qnode)())
+        0: ──H──╭SWAP──╭SWAP──Y──┤ ⟨Z⟩
+        1: ──X──╰SWAP──│─────────┤
+        2: ────────────╰SWAP─────┤
+
+
+    We can remove the SWAP gates by running the ``undo_swap`` transform:
+
+    >>> optimized_qfunc = undo_swaps(qfunc)
+    >>> optimized_qnode = qml.QNode(optimized_qfunc, dev)
+    >>> print(qml.draw(optimized_qnode)(1, 2))
+        0: ──Y──┤ ⟨Z⟩
+        1: ──H──┤
+        2: ──X──┤
+
+    """
+    # Make a working copy of the list to traverse
+    list_copy = tape.operations.copy()
+    list_copy.reverse()
+
+    map_wires = {wire: wire for wire in tape.wires}
+    gates = []
+
+    def _change_wires(wires):
+        change_wires = Wires([])
+        wires = wires.toarray()
+        for wire in wires:
+            change_wires += map_wires[wire]
+        return change_wires
+
+    with stop_recording():
+        while len(list_copy) > 0:
+            current_gate = list_copy[0]
+            params = current_gate.parameters
+            if current_gate.name != "SWAP":
+                if len(params) == 0:
+                    gates.append(type(current_gate)(wires=_change_wires(current_gate.wires)))
+                else:
+                    gates.append(
+                        type(current_gate)(*params, wires=_change_wires(current_gate.wires))
+                    )
+
+            else:
+                swap_wires_0, swap_wires_1 = current_gate.wires
+                map_wires[swap_wires_0], map_wires[swap_wires_1] = (
+                    map_wires[swap_wires_1],
+                    map_wires[swap_wires_0],
+                )
+            list_copy.pop(0)
+
+        gates.reverse()
+
+        for m in tape.measurements:
+            gates.append(m)
+
+    for gate in gates:
+        apply(gate)


Test patch:
diff --git a/tests/transforms/test_optimization/test_undo_swaps.py b/tests/transforms/test_optimization/test_undo_swaps.py
new file mode 100644
index 000000000..64606dc04
--- /dev/null
+++ b/tests/transforms/test_optimization/test_undo_swaps.py
@@ -0,0 +1,258 @@
+# Copyright 2018-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.
+
+import pytest
+from pennylane import numpy as np
+
+import pennylane as qml
+from pennylane.wires import Wires
+from pennylane.transforms.optimization import undo_swaps
+from utils import compare_operation_lists
+
+
+class TestUndoSwaps:
+    """Test that check the main functionalities of the `undo_swaps` transform"""
+
+    def test_one_qubit_gates_transform(self):
+        """Test that a single-qubit gate changes correctly with a SWAP."""
+
+        def qfunc():
+            qml.Hadamard(wires=0)
+            qml.PauliX(wires=1)
+            qml.SWAP(wires=[0, 1])
+            return qml.probs(1)
+
+        transformed_qfunc = undo_swaps(qfunc)
+
+        tape = qml.transforms.make_tape(transformed_qfunc)()
+        res = tape.execute(qml.device("default.qubit", wires=2))
+        assert len(tape.operations) == 2
+        assert np.allclose(res[0][0], 0.5)
+
+    def test_two_qubits_gates_transform(self):
+        """Test that a two-qubit gate changes correctly with a SWAP."""
+
+        def qfunc():
+            qml.PauliX(wires=1)
+            qml.CNOT(wires=[0, 1])
+            qml.SWAP(wires=[0, 1])
+            return qml.state()
+
+        transformed_qfunc = undo_swaps(qfunc)
+
+        tape = qml.transforms.make_tape(transformed_qfunc)()
+        res = tape.execute(qml.device("default.qubit", wires=2))
+        assert len(tape.operations) == 2
+        assert np.allclose(res[0][2], 1.0)
+
+    def test_templates_transform(self):
+        """Test that a template changes correctly with a SWAP."""
+
+        def qfunc1():
+            qml.RX(2, wires=0)
+            qml.RY(-3, wires=1)
+            qml.QFT(wires=[0, 1, 2])
+            qml.SWAP(wires=[1, 2])
+            return qml.state()
+
+        def qfunc2():
+            qml.RX(2, wires=0)
+            qml.RY(-3, wires=2)
+            qml.QFT(wires=[0, 2, 1])
+            return qml.state()
+
+        transformed_qfunc = undo_swaps(qfunc1)
+
+        tape1 = qml.transforms.make_tape(transformed_qfunc)()
+        res1 = tape1.execute(qml.device("default.qubit", wires=3))
+
+        tape2 = qml.transforms.make_tape(qfunc2)()
+        res2 = tape2.execute(qml.device("default.qubit", wires=3))
+
+        assert np.allclose(res1, res2)
+
+    def test_multi_swaps(self):
+        """Test that transform works with several SWAPs."""
+
+        def qfunc1():
+            qml.Hadamard(wires=0)
+            qml.PauliX(wires=1)
+            qml.SWAP(wires=[0, 1])
+            qml.SWAP(wires=[0, 2])
+            qml.PauliY(wires=0)
+            return qml.expval(qml.PauliZ(0))
+
+        def qfunc2():
+            qml.Hadamard(wires=1)
+            qml.PauliX(wires=2)
+            qml.PauliY(wires=0)
+            return qml.expval(qml.PauliZ(0))
+
+        transformed_qfunc = undo_swaps(qfunc1)
+
+        tape1 = qml.transforms.make_tape(transformed_qfunc)()
+        res1 = tape1.execute(qml.device("default.qubit", wires=3))
+
+        tape2 = qml.transforms.make_tape(qfunc2)()
+        res2 = tape2.execute(qml.device("default.qubit", wires=3))
+
+        assert np.allclose(res1, res2)
+
+    def test_decorator(self):
+
+        dev = qml.device("default.qubit", wires=3)
+
+        @qml.qnode(dev)
+        @undo_swaps
+        def qfunc():
+            qml.Hadamard(wires=0)
+            qml.PauliX(wires=1)
+            qml.SWAP(wires=[0, 1])
+            qml.SWAP(wires=[0, 2])
+            qml.PauliY(wires=0)
+            return qml.expval(qml.PauliZ(0))
+
+        qfunc()
+        assert len(qfunc.qtape.operations) == 3
+
+
+# Example QNode and device for interface testing
+dev = qml.device("default.qubit", wires=3)
+
+# Test each of single-qubit, two-qubit, and Rot gates
+def qfunc(theta):
+    qml.Hadamard(wires=0)
+    qml.RX(theta[0], wires=1)
+    qml.SWAP(wires=[0, 1])
+    qml.SWAP(wires=[0, 2])
+    qml.RY(theta[1], wires=0)
+    return qml.expval(qml.PauliZ(0))
+
+
+transformed_qfunc = undo_swaps(qfunc)
+
+expected_op_list = ["Hadamard", "RX", "RY"]
+expected_wires_list = [
+    Wires(1),
+    Wires(2),
+    Wires(0),
+]
+
+
+class TestUndoSwapsInterfaces:
+    """Test that `undo_swaps` transform works in all interfaces."""
+
+    def test_undo_swaps_autograd(self):
+        """Test QNode and gradient in autograd interface."""
+
+        original_qnode = qml.QNode(qfunc, dev)
+        transformed_qnode = qml.QNode(transformed_qfunc, dev)
+
+        input = np.array([0.1, 0.2], requires_grad=True)
+
+        # Check that the numerical output is the same
+        assert qml.math.allclose(original_qnode(input), transformed_qnode(input))
+
+        # Check that the gradient is the same
+        assert qml.math.allclose(
+            qml.grad(original_qnode)(input), qml.grad(transformed_qnode)(input)
+        )
+
+        # Check operation list
+        ops = transformed_qnode.qtape.operations
+        compare_operation_lists(ops, expected_op_list, expected_wires_list)
+
+    def test_undo_swaps_torch(self):
+        """Test QNode and gradient in torch interface."""
+        torch = pytest.importorskip("torch", minversion="1.8")
+
+        original_qnode = qml.QNode(qfunc, dev, interface="torch")
+        transformed_qnode = qml.QNode(transformed_qfunc, dev, interface="torch")
+
+        original_input = torch.tensor([0.1, 0.2], requires_grad=True)
+        transformed_input = torch.tensor([0.1, 0.2], requires_grad=True)
+
+        original_result = original_qnode(original_input)
+        transformed_result = transformed_qnode(transformed_input)
+
+        # Check that the numerical output is the same
+        assert qml.math.allclose(original_result, transformed_result.detach().numpy())
+
+        # Check that the gradient is the same
+        original_result.backward()
+        transformed_result.backward()
+
+        assert qml.math.allclose(original_input.grad, transformed_input.grad)
+
+        # Check operation list
+        ops = transformed_qnode.qtape.operations
+        compare_operation_lists(ops, expected_op_list, expected_wires_list)
+
+    def test_undo_swaps_tf(self):
+        """Test QNode and gradient in tensorflow interface."""
+        tf = pytest.importorskip("tensorflow")
+
+        original_qnode = qml.QNode(qfunc, dev, interface="tf")
+        transformed_qnode = qml.QNode(transformed_qfunc, dev, interface="tf")
+
+        original_input = tf.Variable([0.1, 0.2])
+        transformed_input = tf.Variable([0.1, 0.2])
+
+        original_result = original_qnode(original_input)
+        transformed_result = transformed_qnode(transformed_input)
+
+        # Check that the numerical output is the same
+        assert qml.math.allclose(original_result, transformed_result)
+
+        # Check that the gradient is the same
+        with tf.GradientTape() as tape:
+            loss = original_qnode(original_input)
+        original_grad = tape.gradient(loss, original_input)
+
+        with tf.GradientTape() as tape:
+            loss = transformed_qnode(transformed_input)
+        transformed_grad = tape.gradient(loss, transformed_input)
+
+        assert qml.math.allclose(original_grad, transformed_grad)
+
+        # Check operation list
+        ops = transformed_qnode.qtape.operations
+        compare_operation_lists(ops, expected_op_list, expected_wires_list)
+
+    def test_undo_swaps_jax(self):
+        """Test QNode and gradient in JAX interface."""
+        jax = pytest.importorskip("jax")
+        from jax import numpy as jnp
+
+        from jax.config import config
+
+        remember = config.read("jax_enable_x64")
+        config.update("jax_enable_x64", True)
+
+        original_qnode = qml.QNode(qfunc, dev, interface="jax")
+        transformed_qnode = qml.QNode(transformed_qfunc, dev, interface="jax")
+
+        input = jnp.array([0.1, 0.2], dtype=jnp.float64)
+
+        # Check that the numerical output is the same
+        assert qml.math.allclose(original_qnode(input), transformed_qnode(input))
+
+        # Check that the gradient is the same
+        assert qml.math.allclose(
+            jax.grad(original_qnode)(input), jax.grad(transformed_qnode)(input)
+        )
+
+        # Check operation list
+        ops = transformed_qnode.qtape.operations
+        compare_operation_lists(ops, expected_op_list, expected_wires_list)