Repository: Qiskit/qiskit-terra (python)

Issue:
Improve TwoLocal and RealAmplitudes synthesis when entanglement='full'
### What should we add?

When choosing a `TwoLocal` or `RealAmplitude` or `EfficientSU2` gate with `entanglement=full` on n-qubits (for VQE ansatz),
then we get a circuit with a CX sub-circuit that contains `n*(n-1)/2` CX gates.
However, we can re-write this circuit with only `n-1` CX gates with a linear connectivity (see a code example below).

```
from qiskit.circuit.library import *
from qiskit.quantum_info import Operator

n = 5
# print (RealAmplitudes(n, reps=1, insert_barriers=True).decompose())
# now note that the CX-subcircuit is in fact the same as this qc below

qc = QuantumCircuit(n)
for i in range(n):
    for j in range(i+1, n):
        qc.cx(i,j)
# print ("qc", qc)
mat = LinearFunction(qc).linear
op = Operator(qc)

qc1 = QuantumCircuit(n)
for i in range(n-1):
    qc1.cx(n-i-2, n-i-1)
# print ("qc1", qc1)
mat1 = LinearFunction(qc).linear
op1 = Operator(qc1)

print((mat == mat1).all())
print (op == op1)
```

outputs:
```
True
True
```

It will be good to update either `NLocal` or `TwoLocal` to consider this specific enhancement, 
as it seems that this is used in many applications.

Pull request description:
Add optimization for TwoLocal synthesis when entanglement='full'
<!--
⚠️ If you do not respect this template, your pull request will be closed.
⚠️ Your pull request title should be short detailed and understandable for all.
⚠️ Also, please add a release note file using reno if the change needs to be
  documented in the release notes.
⚠️ If your pull request fixes an open issue, please link to the issue.

- [ ] I have added the tests to cover my changes.
- [ ] I have updated the documentation accordingly.
- [ ] I have read the CONTRIBUTING document.
-->

### Summary
close #8294
Update the [NLocal](https://qiskit.org/documentation/stubs/qiskit.circuit.library.NLocal.html#qiskit.circuit.library.NLocal) class.

### Details and comments
When choosing a `TwoLocal` or `RealAmplitude` or `EfficientSU2` gate with `entanglement=full` on n-qubits (for VQE ansatz),
for a circuit with a `CX` sub-circuit, improve the number of `CX` gates from `n*(n-1)/2` `CX` gates to only `n-1` `CX` gates with a linear connectivity



Patch:
diff --git a/qiskit/circuit/library/n_local/efficient_su2.py b/qiskit/circuit/library/n_local/efficient_su2.py
index b22fef5d0..91be34ec6 100644
--- a/qiskit/circuit/library/n_local/efficient_su2.py
+++ b/qiskit/circuit/library/n_local/efficient_su2.py
@@ -35,13 +35,13 @@ class EfficientSU2(TwoLocal):
 
     .. parsed-literal::
 
-        ┌──────────┐┌──────────┐ ░                 ░       ░ ┌───────────┐┌───────────┐
-        ┤ RY(θ[0]) ├┤ RZ(θ[3]) ├─░───■────■────────░─ ... ─░─┤ RY(θ[12]) ├┤ RZ(θ[15]) ├
-        ├──────────┤├──────────┤ ░ ┌─┴─┐  │        ░       ░ ├───────────┤├───────────┤
-        ┤ RY(θ[1]) ├┤ RZ(θ[4]) ├─░─┤ X ├──┼────■───░─ ... ─░─┤ RY(θ[13]) ├┤ RZ(θ[16]) ├
-        ├──────────┤├──────────┤ ░ └───┘┌─┴─┐┌─┴─┐ ░       ░ ├───────────┤├───────────┤
-        ┤ RY(θ[2]) ├┤ RZ(θ[5]) ├─░──────┤ X ├┤ X ├─░─ ... ─░─┤ RY(θ[14]) ├┤ RZ(θ[17]) ├
-        └──────────┘└──────────┘ ░      └───┘└───┘ ░       ░ └───────────┘└───────────┘
+        ┌──────────┐┌──────────┐ ░            ░       ░ ┌───────────┐┌───────────┐
+        ┤ RY(θ[0]) ├┤ RZ(θ[3]) ├─░────────■───░─ ... ─░─┤ RY(θ[12]) ├┤ RZ(θ[15]) ├
+        ├──────────┤├──────────┤ ░      ┌─┴─┐ ░       ░ ├───────────┤├───────────┤
+        ┤ RY(θ[1]) ├┤ RZ(θ[4]) ├─░───■──┤ X ├─░─ ... ─░─┤ RY(θ[13]) ├┤ RZ(θ[16]) ├
+        ├──────────┤├──────────┤ ░ ┌─┴─┐└───┘ ░       ░ ├───────────┤├───────────┤
+        ┤ RY(θ[2]) ├┤ RZ(θ[5]) ├─░─┤ X ├──────░─ ... ─░─┤ RY(θ[14]) ├┤ RZ(θ[17]) ├
+        └──────────┘└──────────┘ ░ └───┘      ░       ░ └───────────┘└───────────┘
 
     See :class:`~qiskit.circuit.library.RealAmplitudes` for more detail on the possible arguments
     and options such as skipping unentanglement qubits, which apply here too.
@@ -86,7 +86,7 @@ class EfficientSU2(TwoLocal):
                 List[Union[str, type, Instruction, QuantumCircuit]],
             ]
         ] = None,
-        entanglement: Union[str, List[List[int]], Callable[[int], List[int]]] = "full",
+        entanglement: Union[str, List[List[int]], Callable[[int], List[int]]] = "reverse_linear",
         reps: int = 3,
         skip_unentangled_qubits: bool = False,
         skip_final_rotation_layer: bool = False,
@@ -106,9 +106,12 @@ class EfficientSU2(TwoLocal):
                 If a list of gates is provided, all gates are applied to each qubit in the provided
                 order.
             entanglement: Specifies the entanglement structure. Can be a string ('full', 'linear'
-                , 'circular' or 'sca'), a list of integer-pairs specifying the indices of qubits
-                entangled with one another, or a callable returning such a list provided with
+                , 'reverse_linear', 'circular' or 'sca'), a list of integer-pairs specifying the indices
+                of qubits entangled with one another, or a callable returning such a list provided with
                 the index of the entanglement layer.
+                Default to 'reverse_linear' entanglement.
+                Note that 'reverse_linear' entanglement provides the same unitary as 'full'
+                with fewer entangling gates.
                 See the Examples section of :class:`~qiskit.circuit.library.TwoLocal` for more
                 detail.
             initial_state: A `QuantumCircuit` object to prepend to the circuit.
diff --git a/qiskit/circuit/library/n_local/n_local.py b/qiskit/circuit/library/n_local/n_local.py
index 9c5cdfddd..902374f98 100644
--- a/qiskit/circuit/library/n_local/n_local.py
+++ b/qiskit/circuit/library/n_local/n_local.py
@@ -1011,7 +1011,12 @@ def get_entangler_map(
 
     if entanglement == "full":
         return list(combinations(list(range(n)), m))
-    if entanglement in ["linear", "circular", "sca", "pairwise"]:
+    elif entanglement == "reverse_linear":
+        # reverse linear connectivity. In the case of m=2 and the entanglement_block='cx'
+        # then it's equivalent to 'full' entanglement
+        reverse = [tuple(range(n - i - m, n - i)) for i in range(n - m + 1)]
+        return reverse
+    elif entanglement in ["linear", "circular", "sca", "pairwise"]:
         linear = [tuple(range(i, i + m)) for i in range(n - m + 1)]
         # if the number of block qubits is 1, we don't have to add the 'circular' part
         if entanglement == "linear" or m == 1:
diff --git a/qiskit/circuit/library/n_local/real_amplitudes.py b/qiskit/circuit/library/n_local/real_amplitudes.py
index ba66293e3..2838c898f 100644
--- a/qiskit/circuit/library/n_local/real_amplitudes.py
+++ b/qiskit/circuit/library/n_local/real_amplitudes.py
@@ -29,18 +29,17 @@ class RealAmplitudes(TwoLocal):
     It is called ``RealAmplitudes`` since the prepared quantum states will only have
     real amplitudes, the complex part is always 0.
 
-    For example a ``RealAmplitudes`` circuit with 2 repetitions on 3 qubits with ``'full'``
+    For example a ``RealAmplitudes`` circuit with 2 repetitions on 3 qubits with ``'reverse_linear'``
     entanglement is
 
     .. parsed-literal::
-
-         ┌──────────┐ ░                 ░ ┌──────────┐ ░                 ░ ┌──────────┐
-         ┤ RY(θ[0]) ├─░───■────■────────░─┤ RY(θ[3]) ├─░───■────■────────░─┤ RY(θ[6]) ├
-         ├──────────┤ ░ ┌─┴─┐  │        ░ ├──────────┤ ░ ┌─┴─┐  │        ░ ├──────────┤
-         ┤ RY(θ[1]) ├─░─┤ X ├──┼────■───░─┤ RY(θ[4]) ├─░─┤ X ├──┼────■───░─┤ RY(θ[7]) ├
-         ├──────────┤ ░ └───┘┌─┴─┐┌─┴─┐ ░ ├──────────┤ ░ └───┘┌─┴─┐┌─┴─┐ ░ ├──────────┤
-         ┤ RY(θ[2]) ├─░──────┤ X ├┤ X ├─░─┤ RY(θ[5]) ├─░──────┤ X ├┤ X ├─░─┤ RY(θ[8]) ├
-         └──────────┘ ░      └───┘└───┘ ░ └──────────┘ ░      └───┘└───┘ ░ └──────────┘
+         ┌──────────┐ ░            ░ ┌──────────┐ ░            ░ ┌──────────┐
+         ┤ Ry(θ[0]) ├─░────────■───░─┤ Ry(θ[3]) ├─░────────■───░─┤ Ry(θ[6]) ├
+         ├──────────┤ ░      ┌─┴─┐ ░ ├──────────┤ ░      ┌─┴─┐ ░ ├──────────┤
+         ┤ Ry(θ[1]) ├─░───■──┤ X ├─░─┤ Ry(θ[4]) ├─░───■──┤ X ├─░─┤ Ry(θ[7]) ├
+         ├──────────┤ ░ ┌─┴─┐└───┘ ░ ├──────────┤ ░ ┌─┴─┐└───┘ ░ ├──────────┤
+         ┤ Ry(θ[2]) ├─░─┤ X ├──────░─┤ Ry(θ[5]) ├─░─┤ X ├──────░─┤ Ry(θ[8]) ├
+         └──────────┘ ░ └───┘      ░ └──────────┘ ░ └───┘      ░ └──────────┘
 
     The entanglement can be set using the ``entanglement`` keyword as string or a list of
     index-pairs. See the documentation of :class:`~qiskit.circuit.library.TwoLocal` and
@@ -56,6 +55,16 @@ class RealAmplitudes(TwoLocal):
     Examples:
 
         >>> ansatz = RealAmplitudes(3, reps=2)  # create the circuit on 3 qubits
+        >>> print(ansatz)
+             ┌──────────┐                 ┌──────────┐                 ┌──────────┐
+        q_0: ┤ Ry(θ[0]) ├──────────■──────┤ Ry(θ[3]) ├──────────■──────┤ Ry(θ[6]) ├
+             ├──────────┤        ┌─┴─┐    ├──────────┤        ┌─┴─┐    ├──────────┤
+        q_1: ┤ Ry(θ[1]) ├──■─────┤ X ├────┤ Ry(θ[4]) ├──■─────┤ X ├────┤ Ry(θ[7]) ├
+             ├──────────┤┌─┴─┐┌──┴───┴───┐└──────────┘┌─┴─┐┌──┴───┴───┐└──────────┘
+        q_2: ┤ Ry(θ[2]) ├┤ X ├┤ Ry(θ[5]) ├────────────┤ X ├┤ Ry(θ[8]) ├────────────
+             └──────────┘└───┘└──────────┘            └───┘└──────────┘
+
+        >>> ansatz = RealAmplitudes(3, entanglement='full', reps=2)  # it is the same unitary as above
         >>> print(ansatz)
              ┌──────────┐          ┌──────────┐                      ┌──────────┐
         q_0: ┤ RY(θ[0]) ├──■────■──┤ RY(θ[3]) ├──────────────■────■──┤ RY(θ[6]) ├────────────
@@ -107,7 +116,7 @@ class RealAmplitudes(TwoLocal):
     def __init__(
         self,
         num_qubits: Optional[int] = None,
-        entanglement: Union[str, List[List[int]], Callable[[int], List[int]]] = "full",
+        entanglement: Union[str, List[List[int]], Callable[[int], List[int]]] = "reverse_linear",
         reps: int = 3,
         skip_unentangled_qubits: bool = False,
         skip_final_rotation_layer: bool = False,
@@ -123,9 +132,12 @@ class RealAmplitudes(TwoLocal):
             reps: Specifies how often the structure of a rotation layer followed by an entanglement
                 layer is repeated.
             entanglement: Specifies the entanglement structure. Can be a string ('full', 'linear'
-                or 'sca'), a list of integer-pairs specifying the indices of qubits
-                entangled with one another, or a callable returning such a list provided with
+                'reverse_linear, 'circular' or 'sca'), a list of integer-pairs specifying the indices
+                of qubits entangled with one another, or a callable returning such a list provided with
                 the index of the entanglement layer.
+                Default to 'reverse_linear' entanglement.
+                Note that 'reverse_linear' entanglement provides the same unitary as 'full'
+                with fewer entangling gates.
                 See the Examples section of :class:`~qiskit.circuit.library.TwoLocal` for more
                 detail.
             initial_state: A `QuantumCircuit` object to prepend to the circuit.
diff --git a/qiskit/circuit/library/n_local/two_local.py b/qiskit/circuit/library/n_local/two_local.py
index c4586f260..14edd8955 100644
--- a/qiskit/circuit/library/n_local/two_local.py
+++ b/qiskit/circuit/library/n_local/two_local.py
@@ -61,6 +61,13 @@ class TwoLocal(NLocal):
     * ``'full'`` entanglement is each qubit is entangled with all the others.
     * ``'linear'`` entanglement is qubit :math:`i` entangled with qubit :math:`i + 1`,
       for all :math:`i \in \{0, 1, ... , n - 2\}`, where :math:`n` is the total number of qubits.
+    * ``'reverse_linear'`` entanglement is qubit :math:`i` entangled with qubit :math:`i + 1`,
+      for all :math:`i \in \{n-2, n-3, ... , 1, 0\}`, where :math:`n` is the total number of qubits.
+      Note that if ``entanglement_blocks = 'cx'`` then this option provides the same unitary as
+      ``'full'`` with fewer entangling gates.
+    * ``'pairwise'`` entanglement is one layer where qubit :math:`i` is entangled with qubit
+      :math:`i + 1`, for all even values of :math:`i`, and then a second layer where qubit :math:`i`
+      is entangled with qubit :math:`i + 1`, for all odd values of :math:`i`.
     * ``'circular'`` entanglement is linear entanglement but with an additional entanglement of the
       first and last qubit before the linear part.
     * ``'sca'`` (shifted-circular-alternating) entanglement is a generalized and modified version
@@ -179,10 +186,12 @@ class TwoLocal(NLocal):
             entanglement_blocks: The gates used in the entanglement layer. Can be specified in
                 the same format as `rotation_blocks`.
             entanglement: Specifies the entanglement structure. Can be a string ('full', 'linear'
-                , 'circular' or 'sca'), a list of integer-pairs specifying the indices of qubits
-                entangled with one another, or a callable returning such a list provided with
+                , 'reverse_linear, 'circular' or 'sca'), a list of integer-pairs specifying the indices
+                of qubits entangled with one another, or a callable returning such a list provided with
                 the index of the entanglement layer.
                 Default to 'full' entanglement.
+                Note that if ``entanglement_blocks = 'cx'``, then ``'full'`` entanglement provides the
+                same unitary as ``'reverse_linear'`` but the latter option has fewer entangling gates.
                 See the Examples section for more detail.
             reps: Specifies how often a block consisting of a rotation layer and entanglement
                 layer is repeated.
diff --git a/releasenotes/notes/add-reverse-linear-entanglement-nlocal-38581e4ffb7a7c68.yaml b/releasenotes/notes/add-reverse-linear-entanglement-nlocal-38581e4ffb7a7c68.yaml
new file mode 100644
index 000000000..1f51ab260
--- /dev/null
+++ b/releasenotes/notes/add-reverse-linear-entanglement-nlocal-38581e4ffb7a7c68.yaml
@@ -0,0 +1,9 @@
+---
+features:
+  - |
+    Add a new entanglement method `entanglement="reverse_linear"` to :class:`~.NLocal` circuits.
+    In the case of :class:`~.TwoLocal` circuits, if `entanglement_blocks="cx"` then
+    `entanglement="reverse_linear"` actually provides the same n-qubit circuit as
+    `entanglement="full"` but with only n-1 CX gates, instead of n(n-1)/2.
+    For :class:`~.RealAmplitudes` and :class:`~.EfficientSU2` circuits, the default value
+    has therefore been changed from `entanglement="full"` to `entanglement="reverse_linear"`.


Test patch:
diff --git a/test/python/circuit/library/test_nlocal.py b/test/python/circuit/library/test_nlocal.py
index 3204269ed..5c77bac35 100644
--- a/test/python/circuit/library/test_nlocal.py
+++ b/test/python/circuit/library/test_nlocal.py
@@ -13,6 +13,7 @@
 """Test library of n-local circuits."""
 
 import unittest
+from test import combine
 
 import numpy as np
 
@@ -40,6 +41,7 @@ from qiskit.circuit.library import (
 )
 from qiskit.circuit.random.utils import random_circuit
 from qiskit.converters.circuit_to_dag import circuit_to_dag
+from qiskit.quantum_info import Operator
 
 
 @ddt
@@ -296,7 +298,16 @@ class TestNLocal(QiskitTestCase):
                 idle = set(dag.idle_wires())
                 self.assertEqual(skipped_set, idle)
 
-    @data("linear", "full", "circular", "sca", ["linear", "full"], ["circular", "linear", "sca"])
+    @data(
+        "linear",
+        "full",
+        "circular",
+        "sca",
+        "reverse_linear",
+        ["linear", "full"],
+        ["reverse_linear", "full"],
+        ["circular", "linear", "sca"],
+    )
     def test_entanglement_by_str(self, entanglement):
         """Test setting the entanglement of the layers by str."""
         reps = 3
@@ -311,6 +322,8 @@ class TestNLocal(QiskitTestCase):
         def get_expected_entangler_map(rep_num, mode):
             if mode == "linear":
                 return [(0, 1, 2), (1, 2, 3), (2, 3, 4)]
+            elif mode == "reverse_linear":
+                return [(2, 3, 4), (1, 2, 3), (0, 1, 2)]
             elif mode == "full":
                 return [
                     (0, 1, 2),
@@ -343,7 +356,7 @@ class TestNLocal(QiskitTestCase):
 
             with self.subTest(rep_num=rep_num):
                 # using a set here since the order does not matter
-                self.assertEqual(set(entangler_map), set(expected))
+                self.assertEqual(entangler_map, expected)
 
     def test_pairwise_entanglement(self):
         """Test pairwise entanglement."""
@@ -620,8 +633,30 @@ class TestTwoLocal(QiskitTestCase):
             expected = [(-np.pi, np.pi)] * two.num_parameters
             np.testing.assert_almost_equal(two.parameter_bounds, expected)
 
-    def test_ry_circuit(self):
-        """Test an RealAmplitudes circuit."""
+    def test_ry_circuit_reverse_linear(self):
+        """Test a RealAmplitudes circuit with entanglement = "reverse_linear"."""
+        num_qubits = 3
+        reps = 2
+        entanglement = "reverse_linear"
+        parameters = ParameterVector("theta", num_qubits * (reps + 1))
+        param_iter = iter(parameters)
+
+        expected = QuantumCircuit(3)
+        for _ in range(reps):
+            for i in range(num_qubits):
+                expected.ry(next(param_iter), i)
+            expected.cx(1, 2)
+            expected.cx(0, 1)
+        for i in range(num_qubits):
+            expected.ry(next(param_iter), i)
+
+        library = RealAmplitudes(
+            num_qubits, reps=reps, entanglement=entanglement
+        ).assign_parameters(parameters)
+        self.assertCircuitEqual(library, expected)
+
+    def test_ry_circuit_full(self):
+        """Test a RealAmplitudes circuit with entanglement = "full"."""
         num_qubits = 3
         reps = 2
         entanglement = "full"
@@ -648,7 +683,6 @@ class TestTwoLocal(QiskitTestCase):
         library = RealAmplitudes(
             num_qubits, reps=reps, entanglement=entanglement
         ).assign_parameters(parameters)
-
         self.assertCircuitEqual(library, expected)
 
     def test_ryrz_blocks(self):
@@ -868,6 +902,19 @@ class TestTwoLocal(QiskitTestCase):
         self.assertEqual(two_np32.decompose().count_ops()["cx"], expected_cx)
         self.assertEqual(two_np64.decompose().count_ops()["cx"], expected_cx)
 
+    @combine(num_qubits=[4, 5])
+    def test_full_vs_reverse_linear(self, num_qubits):
+        """Test that 'full' and 'reverse_linear' provide the same unitary element."""
+        reps = 2
+        full = RealAmplitudes(num_qubits=num_qubits, entanglement="full", reps=reps)
+        num_params = (reps + 1) * num_qubits
+        np.random.seed(num_qubits)
+        params = np.random.rand(num_params)
+        reverse = RealAmplitudes(num_qubits=num_qubits, entanglement="reverse_linear", reps=reps)
+        full.assign_parameters(params, inplace=True)
+        reverse.assign_parameters(params, inplace=True)
+        assert Operator(full) == Operator(reverse)
+
 
 if __name__ == "__main__":
     unittest.main()
diff --git a/test/python/circuit/library/test_pauli_feature_map.py b/test/python/circuit/library/test_pauli_feature_map.py
index bc2754c1a..4cdc199b8 100644
--- a/test/python/circuit/library/test_pauli_feature_map.py
+++ b/test/python/circuit/library/test_pauli_feature_map.py
@@ -13,6 +13,7 @@
 """Test library of Pauli feature map circuits."""
 
 import unittest
+from test import combine
 
 import numpy as np
 
@@ -152,10 +153,11 @@ class TestDataPreparation(QiskitTestCase):
 
         self.assertTrue(Operator(encoding).equiv(ref))
 
-    def test_zz_pairwise_entanglement(self):
-        """Test the ZZ feature map works with pairwise entanglement."""
+    @combine(entanglement=["linear", "reverse_linear", "pairwise"])
+    def test_zz_entanglement(self, entanglement):
+        """Test the ZZ feature map works with pairwise, linear and reverse_linear entanglement."""
         num_qubits = 5
-        encoding = ZZFeatureMap(num_qubits, entanglement="pairwise", reps=1)
+        encoding = ZZFeatureMap(num_qubits, entanglement=entanglement, reps=1)
         ops = encoding.decompose().count_ops()
         expected_ops = {"h": num_qubits, "p": 2 * num_qubits - 1, "cx": 2 * (num_qubits - 1)}
         self.assertEqual(ops, expected_ops)