Repository: Qiskit/qiskit-terra (python)

Issue:
`QuantumCircuit._check_dup_param_spec` becomes slow for many gates reusing few parameters
<!-- ⚠️ If you do not respect this template, your issue will be closed -->
<!-- ⚠️ Make sure to browse the opened and closed issues to confirm this idea does not exist. -->

### What is the expected enhancement?

When building a parameterized circuit where a large number of gates re-use a comparatively small number of parameters, `QuantumCircuit._check_dup_param_spec` becomes a performance bottleneck.

For example, `circuit_construction.ParameterizedCircuitConstructionBench.time_build_parameterized_circuit` takes 90s to build a 131k gate circuit with 8 distinct parameters, vs. <5s to build a 131k gate circuit with anything more than 128 parameters:

https://qiskit.github.io/qiskit/#circuit_construction.ParameterizedCircuitConstructionBench.time_build_parameterized_circuit?x-axis=number%20of%20params

Since the structure of the `ParameterTable` is dict mapping `Parameter` instances to lists of `Instruction`s, each call to `_check_dup_param_spec` must walk the entire `Instruction` list to look for a match. One option would be to convert the list to a dict, which could be efficiently checked for membership.

Pull request:
Use `ParameterReferences` type for `ParameterTable` values
<!--
⚠️ 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.

- [X] I have added the tests to cover my changes.
- [X] I have updated the documentation accordingly.
- [X] I have read the CONTRIBUTING document.
-->

### Summary
Changes `ParameterTable` value type from `List[(Instruction, int)]` to a new collection type, `ParameterReferences`, which is set-like, and **no longer seq-like**.

`ParameterReferences`:

> A set of instruction parameter slot references. Items are expected in the form `(instruction, param_index)`. Membership testing is overriden such that items that are otherwise value-wise equal are still considered distinct if their `instruction`s are referentially distinct.

### Details and comments
It's not actually necessary to update existing uses of `ParameterTable` or its values, but usage is updated in `QuantumCircuit` for performance (mostly to avoid creating lists that are then immediately spooled into `ParameterReferences`). See `ParameterReferences` docstring for more information.

Fixes #6725. `ParameterReferences` is set-like, so there's no need to perform a linear search in `_update_parameter_table` to check existing references for every instruction parameter.

Patch:
diff --git a/qiskit/circuit/parametertable.py b/qiskit/circuit/parametertable.py
index 115854cd9..0fd00951e 100644
--- a/qiskit/circuit/parametertable.py
+++ b/qiskit/circuit/parametertable.py
@@ -12,43 +12,122 @@
 """
 Look-up table for variable parameters in QuantumCircuit.
 """
-import warnings
 import functools
-from collections.abc import MutableMapping, MappingView
+import warnings
+from collections.abc import MappingView, MutableMapping, MutableSet
+
+
+class ParameterReferences(MutableSet):
+    """A set of instruction parameter slot references.
+    Items are expected in the form ``(instruction, param_index)``. Membership
+    testing is overriden such that items that are otherwise value-wise equal
+    are still considered distinct if their ``instruction``\\ s are referentially
+    distinct.
+    """
+
+    def _instance_key(self, ref):
+        return (id(ref[0]), ref[1])
+
+    def __init__(self, refs):
+        self._instance_ids = {}
+
+        for ref in refs:
+            if not isinstance(ref, tuple) or len(ref) != 2:
+                raise ValueError("refs must be in form (instruction, param_index)")
+            k = self._instance_key(ref)
+            self._instance_ids[k] = ref[0]
+
+    def __getstate__(self):
+        # Leave behind the reference IDs (keys of _instance_ids) since they'll
+        # be incorrect after unpickling on the other side.
+        return list(self)
+
+    def __setstate__(self, refs):
+        # Recompute reference IDs for the newly unpickled instructions.
+        self._instance_ids = {self._instance_key(ref): ref[0] for ref in refs}
+
+    def __len__(self):
+        return len(self._instance_ids)
+
+    def __iter__(self):
+        for (_, idx), instruction in self._instance_ids.items():
+            yield (instruction, idx)
+
+    def __contains__(self, x) -> bool:
+        return self._instance_key(x) in self._instance_ids
 
-from .instruction import Instruction
+    def __repr__(self) -> str:
+        return f"ParameterReferences({repr(list(self))})"
+
+    def add(self, value):
+        """Adds a reference to the listing if it's not already present."""
+        k = self._instance_key(value)
+        self._instance_ids[k] = value[0]
+
+    def discard(self, value):
+        k = self._instance_key(value)
+        self._instance_ids.pop(k, None)
+
+    def copy(self):
+        """Create a shallow copy."""
+        return ParameterReferences(self)
 
 
 class ParameterTable(MutableMapping):
-    """Class for managing and setting circuit parameters"""
+    """Class for tracking references to circuit parameters by specific
+    instruction instances.
+
+    Keys are parameters. Values are of type :class:`~ParameterReferences`,
+    which overrides membership testing to be referential for instructions,
+    and is set-like. Elements of :class:`~ParameterReferences`
+    are tuples of ``(instruction, param_index)``.
+    """
 
     __slots__ = ["_table", "_keys", "_names"]
 
-    def __init__(self, *args, **kwargs):
-        """
-        the structure of _table is,
-           {var_object: [(instruction_object, parameter_index), ...]}
+    def __init__(self, mapping=None):
+        """Create a new instance, initialized with ``mapping`` if provided.
+
+        Args:
+            mapping (Mapping[Parameter, ParameterReferences]):
+                Mapping of parameter to the set of parameter slots that reference
+                it.
+
+        Raises:
+            ValueError: A value in ``mapping`` is not a :class:`~ParameterReferences`.
         """
-        self._table = dict(*args, **kwargs)
+        if mapping is not None:
+            if any(not isinstance(refs, ParameterReferences) for refs in mapping.values()):
+                raise ValueError("Values must be of type ParameterReferences")
+            self._table = mapping.copy()
+        else:
+            self._table = {}
+
         self._keys = set(self._table)
         self._names = {x.name for x in self._table}
 
     def __getitem__(self, key):
         return self._table[key]
 
-    def __setitem__(self, parameter, instr_params):
-        """Sets list of Instructions that depend on Parameter.
+    def __setitem__(self, parameter, refs):
+        """Associate a parameter with the set of parameter slots ``(instruction, param_index)``
+        that reference it.
+
+        .. note::
+
+            Items in ``refs`` are considered unique if their ``instruction`` is referentially
+            unique. See :class:`~ParameterReferences` for details.
 
         Args:
-            parameter (Parameter): the parameter to set
-            instr_params (list): List of (Instruction, int) tuples. Int is the
-              parameter index at which the parameter appears in the instruction.
+            parameter (Parameter): the parameter
+            refs (Union[ParameterReferences, Iterable[(Instruction, int)]]): the parameter slots.
+                If this is an iterable, a new :class:`~ParameterReferences` is created from its
+                contents.
         """
+        if not isinstance(refs, ParameterReferences):
+            refs = ParameterReferences(refs)
 
-        for instruction, param_index in instr_params:
-            assert isinstance(instruction, Instruction)
-            assert isinstance(param_index, int)
-        self._table[parameter] = instr_params
+        self._table[parameter] = refs
         self._keys.add(parameter)
         self._names.add(parameter.name)
 
diff --git a/qiskit/circuit/quantumcircuit.py b/qiskit/circuit/quantumcircuit.py
index 5c6ff13e9..612a6abeb 100644
--- a/qiskit/circuit/quantumcircuit.py
+++ b/qiskit/circuit/quantumcircuit.py
@@ -49,7 +49,7 @@ from qiskit.utils.deprecation import deprecate_function
 from .parameterexpression import ParameterExpression, ParameterValueType
 from .quantumregister import QuantumRegister, Qubit, AncillaRegister, AncillaQubit
 from .classicalregister import ClassicalRegister, Clbit
-from .parametertable import ParameterTable, ParameterView
+from .parametertable import ParameterReferences, ParameterTable, ParameterView
 from .parametervector import ParameterVector, ParameterVectorElement
 from .instructionset import InstructionSet
 from .register import Register
@@ -1285,31 +1285,19 @@ class QuantumCircuit:
 
             for parameter in atomic_parameters:
                 if parameter in self._parameter_table:
-                    if not self._check_dup_param_spec(
-                        self._parameter_table[parameter], instruction, param_index
-                    ):
-                        self._parameter_table[parameter].append((instruction, param_index))
+                    self._parameter_table[parameter].add((instruction, param_index))
                 else:
                     if parameter.name in self._parameter_table.get_names():
                         raise CircuitError(f"Name conflict on adding parameter: {parameter.name}")
-                    self._parameter_table[parameter] = [(instruction, param_index)]
+                    self._parameter_table[parameter] = ParameterReferences(
+                        ((instruction, param_index),)
+                    )
 
                     # clear cache if new parameter is added
                     self._parameters = None
 
         return instruction
 
-    def _check_dup_param_spec(
-        self,
-        parameter_spec_list: Sequence[Tuple[Instruction, int]],
-        instruction: Instruction,
-        param_index: int,
-    ) -> bool:
-        for spec in parameter_spec_list:
-            if spec[0] is instruction and spec[1] == param_index:
-                return True
-        return False
-
     def add_register(self, *regs: Union[Register, int, Sequence[Bit]]) -> None:
         """Add registers."""
         if not regs:
@@ -2118,10 +2106,10 @@ class QuantumCircuit:
 
         cpy._parameter_table = ParameterTable(
             {
-                param: [
+                param: ParameterReferences(
                     (instr_copies[id(instr)], param_index)
                     for instr, param_index in self._parameter_table[param]
-                ]
+                )
                 for param in self._parameter_table
             }
         )
@@ -2569,7 +2557,7 @@ class QuantumCircuit:
                 reference to a value that cannot be assigned.
         """
         # parameter might be in global phase only
-        if parameter in self._parameter_table.keys():
+        if parameter in self._parameter_table:
             for instr, param_index in self._parameter_table[parameter]:
                 assignee = instr.params[param_index]
                 # Normal ParameterExpression.
@@ -2598,7 +2586,7 @@ class QuantumCircuit:
                 entry = self._parameter_table.pop(parameter)
                 for new_parameter in value.parameters:
                     if new_parameter in self._parameter_table:
-                        self._parameter_table[new_parameter].extend(entry)
+                        self._parameter_table[new_parameter] |= entry
                     else:
                         self._parameter_table[new_parameter] = entry
             else:
@@ -4128,11 +4116,12 @@ class QuantumCircuit:
                 atomic_parameters.update(parameter.parameters)
         for atomic_parameter in atomic_parameters:
             entries = self._parameter_table[atomic_parameter]
-            new_entries = [
+            new_entries = ParameterReferences(
                 (entry_instruction, entry_index)
                 for entry_instruction, entry_index in entries
                 if entry_instruction is not instruction
-            ]
+            )
+
             if not new_entries:
                 del self._parameter_table[atomic_parameter]
                 # Invalidate cache.
diff --git a/qiskit/opflow/gradients/circuit_gradients/lin_comb.py b/qiskit/opflow/gradients/circuit_gradients/lin_comb.py
index 0fa8ada96..0a911b9ed 100644
--- a/qiskit/opflow/gradients/circuit_gradients/lin_comb.py
+++ b/qiskit/opflow/gradients/circuit_gradients/lin_comb.py
@@ -29,7 +29,7 @@ from qiskit.circuit import (
     ParameterExpression,
     Parameter,
 )
-from qiskit.circuit.parametertable import ParameterTable
+from qiskit.circuit.parametertable import ParameterReferences, ParameterTable
 from qiskit.circuit.controlledgate import ControlledGate
 from qiskit.circuit.library import SGate, SdgGate, XGate
 from qiskit.circuit.library.standard_gates import (
@@ -604,9 +604,9 @@ class LinComb(CircuitGradient):
                     if isinstance(param_expression, ParameterExpression):
                         for param in param_expression.parameters:
                             if param not in table.keys():
-                                table[param] = [(op, idx)]
+                                table[param] = ParameterReferences(((op, idx),))
                             else:
-                                table[param].append((op, idx))
+                                table[param].add((op, idx))
 
             out._parameter_table = table
 
diff --git a/qiskit/opflow/gradients/circuit_gradients/param_shift.py b/qiskit/opflow/gradients/circuit_gradients/param_shift.py
index a49e1027e..3b2aacfa7 100644
--- a/qiskit/opflow/gradients/circuit_gradients/param_shift.py
+++ b/qiskit/opflow/gradients/circuit_gradients/param_shift.py
@@ -207,8 +207,13 @@ class ParamShift(CircuitGradient):
 
             shifted_ops = []
             summed_shifted_op = None
-            for m, param_occurence in enumerate(circ._parameter_table[param]):
-                param_index = param_occurence[1]
+
+            iref_to_data_index = {id(inst): idx for idx, (inst, _, _) in enumerate(circ.data)}
+
+            for param_reference in circ._parameter_table[param]:
+                original_gate, param_index = param_reference
+                m = iref_to_data_index[id(original_gate)]
+
                 pshift_op = deepcopy(operator)
                 mshift_op = deepcopy(operator)
 
@@ -216,8 +221,8 @@ class ParamShift(CircuitGradient):
                 pshift_circ = self.get_unique_circuits(pshift_op)[0]
                 mshift_circ = self.get_unique_circuits(mshift_op)[0]
 
-                pshift_gate = pshift_circ._parameter_table[param][m][0]
-                mshift_gate = mshift_circ._parameter_table[param][m][0]
+                pshift_gate = pshift_circ.data[m][0]
+                mshift_gate = mshift_circ.data[m][0]
 
                 p_param = pshift_gate.params[param_index]
                 m_param = mshift_gate.params[param_index]
diff --git a/qiskit/opflow/gradients/circuit_qfis/overlap_block_diag.py b/qiskit/opflow/gradients/circuit_qfis/overlap_block_diag.py
index 01e947384..7daf64866 100644
--- a/qiskit/opflow/gradients/circuit_qfis/overlap_block_diag.py
+++ b/qiskit/opflow/gradients/circuit_qfis/overlap_block_diag.py
@@ -136,7 +136,7 @@ class OverlapBlockDiag(CircuitQFI):
                         "gates parameterized by a single parameter. For such "
                         "circuits use LinCombFull"
                     )
-                gate = circuit._parameter_table[param][0][0]
+                gate = next(iter(circuit._parameter_table[param]))[0]
                 if len(gate.params) > 1:
                     raise OpflowError(
                         "OverlapDiag cannot yet support gates with more than one parameter."
diff --git a/qiskit/opflow/gradients/circuit_qfis/overlap_diag.py b/qiskit/opflow/gradients/circuit_qfis/overlap_diag.py
index 65b752d16..9efca9f67 100644
--- a/qiskit/opflow/gradients/circuit_qfis/overlap_diag.py
+++ b/qiskit/opflow/gradients/circuit_qfis/overlap_diag.py
@@ -120,7 +120,7 @@ class OverlapDiag(CircuitQFI):
                     "circuits use LinCombFull"
                 )
 
-            gate = circuit._parameter_table[param][0][0]
+            gate = next(iter(circuit._parameter_table[param]))[0]
 
             if len(gate.params) != 1:
                 raise TypeError(
diff --git a/releasenotes/notes/param-table-perf-72cd1c40533b3882.yaml b/releasenotes/notes/param-table-perf-72cd1c40533b3882.yaml
new file mode 100644
index 000000000..7388fbbb5
--- /dev/null
+++ b/releasenotes/notes/param-table-perf-72cd1c40533b3882.yaml
@@ -0,0 +1,6 @@
+---
+fixes:
+  - |
+    Improves the performance of building and working with parameterized
+    :class:`~qiskit.circuit.QuantumCircuit` instances with many gates
+    that share a relatively small number of parameters.


Test patch:
diff --git a/test/python/circuit/test_circuit_data.py b/test/python/circuit/test_circuit_data.py
index bcc3a5d44..6fe7fbae3 100644
--- a/test/python/circuit/test_circuit_data.py
+++ b/test/python/circuit/test_circuit_data.py
@@ -422,6 +422,6 @@ class TestQuantumCircuitInstructionData(QiskitTestCase):
         qc0.append(rx, [0])
         qc1.append(rx, [0])
         qc0.assign_parameters({a: b}, inplace=True)
-        qc0_instance = qc0._parameter_table[b][0][0]
-        qc1_instance = qc1._parameter_table[a][0][0]
+        qc0_instance = next(iter(qc0._parameter_table[b]))[0]
+        qc1_instance = next(iter(qc1._parameter_table[a]))[0]
         self.assertNotEqual(qc0_instance, qc1_instance)
diff --git a/test/python/circuit/test_parameters.py b/test/python/circuit/test_parameters.py
index fe294c0f6..1fd07243d 100644
--- a/test/python/circuit/test_parameters.py
+++ b/test/python/circuit/test_parameters.py
@@ -25,9 +25,10 @@ from ddt import data, ddt
 
 import qiskit
 import qiskit.circuit.library as circlib
+from qiskit.circuit.library.standard_gates.rz import RZGate
 from qiskit import BasicAer, ClassicalRegister, QuantumCircuit, QuantumRegister
 from qiskit.circuit import Gate, Instruction, Parameter, ParameterExpression, ParameterVector
-from qiskit.circuit.parametertable import ParameterView
+from qiskit.circuit.parametertable import ParameterReferences, ParameterTable, ParameterView
 from qiskit.circuit.exceptions import CircuitError
 from qiskit.compiler import assemble, transpile
 from qiskit.execute_function import execute
@@ -144,7 +145,7 @@ class TestParameters(QiskitTestCase):
         vparams = qc._parameter_table
         self.assertEqual(len(vparams), 1)
         self.assertIs(theta, next(iter(vparams)))
-        self.assertEqual(rxg, vparams[theta][0][0])
+        self.assertEqual(rxg, next(iter(vparams[theta]))[0])
 
     def test_get_parameters_by_index(self):
         """Test getting parameters by index"""
@@ -466,7 +467,6 @@ class TestParameters(QiskitTestCase):
 
     def test_gate_multiplicity_binding(self):
         """Test binding when circuit contains multiple references to same gate"""
-        from qiskit.circuit.library.standard_gates.rz import RZGate
 
         qc = QuantumCircuit(1)
         theta = Parameter("theta")
@@ -1578,8 +1578,6 @@ class TestParameterExpressions(QiskitTestCase):
         """Bind a parameter which was included via a broadcast instruction."""
         # ref: https://github.com/Qiskit/qiskit-terra/issues/3008
 
-        from qiskit.circuit.library.standard_gates.rz import RZGate
-
         theta = Parameter("θ")
         n = 5
 
@@ -1783,6 +1781,155 @@ class TestParameterEquality(QiskitTestCase):
         self.assertEqual(phi._parameter_symbols, cos_phi._parameter_symbols)
 
 
+class TestParameterReferences(QiskitTestCase):
+    """Test the ParameterReferences class."""
+
+    def test_equal_inst_diff_instance(self):
+        """Different value equal instructions are treated as distinct."""
+
+        theta = Parameter("theta")
+        gate1 = RZGate(theta)
+        gate2 = RZGate(theta)
+
+        self.assertIsNot(gate1, gate2)
+        self.assertEqual(gate1, gate2)
+
+        refs = ParameterReferences(((gate1, 0), (gate2, 0)))
+
+        # test __contains__
+        self.assertIn((gate1, 0), refs)
+        self.assertIn((gate2, 0), refs)
+
+        gate_ids = {id(gate1), id(gate2)}
+        self.assertEqual(gate_ids, {id(gate) for gate, _ in refs})
+        self.assertTrue(all(idx == 0 for _, idx in refs))
+
+    def test_pickle_unpickle(self):
+        """Membership testing after pickle/unpickle."""
+
+        theta = Parameter("theta")
+        gate1 = RZGate(theta)
+        gate2 = RZGate(theta)
+
+        self.assertIsNot(gate1, gate2)
+        self.assertEqual(gate1, gate2)
+
+        refs = ParameterReferences(((gate1, 0), (gate2, 0)))
+
+        to_pickle = (gate1, refs)
+        pickled = pickle.dumps(to_pickle)
+        (gate1_new, refs_new) = pickle.loads(pickled)
+
+        self.assertEqual(len(refs_new), len(refs))
+        self.assertNotIn((gate1, 0), refs_new)
+        self.assertIn((gate1_new, 0), refs_new)
+
+    def test_equal_inst_same_instance(self):
+        """Referentially equal instructions are treated as same."""
+
+        theta = Parameter("theta")
+        gate = RZGate(theta)
+
+        refs = ParameterReferences(((gate, 0), (gate, 0)))
+
+        self.assertIn((gate, 0), refs)
+        self.assertEqual(len(refs), 1)
+        self.assertIs(next(iter(refs))[0], gate)
+        self.assertEqual(next(iter(refs))[1], 0)
+
+    def test_extend_refs(self):
+        """Extending references handles duplicates."""
+
+        theta = Parameter("theta")
+        ref0 = (RZGate(theta), 0)
+        ref1 = (RZGate(theta), 0)
+        ref2 = (RZGate(theta), 0)
+
+        refs = ParameterReferences((ref0,))
+        refs |= ParameterReferences((ref0, ref1, ref2, ref1, ref0))
+
+        self.assertEqual(refs, ParameterReferences((ref0, ref1, ref2)))
+
+    def test_copy_param_refs(self):
+        """Copy of parameter references is a shallow copy."""
+
+        theta = Parameter("theta")
+        ref0 = (RZGate(theta), 0)
+        ref1 = (RZGate(theta), 0)
+        ref2 = (RZGate(theta), 0)
+        ref3 = (RZGate(theta), 0)
+
+        refs = ParameterReferences((ref0, ref1))
+        refs_copy = refs.copy()
+
+        # Check same gate instances in copy
+        gate_ids = {id(ref0[0]), id(ref1[0])}
+        self.assertEqual({id(gate) for gate, _ in refs_copy}, gate_ids)
+
+        # add new ref to original and check copy not modified
+        refs.add(ref2)
+        self.assertNotIn(ref2, refs_copy)
+        self.assertEqual(refs_copy, ParameterReferences((ref0, ref1)))
+
+        # add new ref to copy and check original not modified
+        refs_copy.add(ref3)
+        self.assertNotIn(ref3, refs)
+        self.assertEqual(refs, ParameterReferences((ref0, ref1, ref2)))
+
+
+class TestParameterTable(QiskitTestCase):
+    """Test the ParameterTable class."""
+
+    def test_init_param_table(self):
+        """Parameter table init from mapping."""
+
+        p1 = Parameter("theta")
+        p2 = Parameter("theta")
+
+        ref0 = (RZGate(p1), 0)
+        ref1 = (RZGate(p1), 0)
+        ref2 = (RZGate(p2), 0)
+
+        mapping = {p1: ParameterReferences((ref0, ref1)), p2: ParameterReferences((ref2,))}
+
+        table = ParameterTable(mapping)
+
+        # make sure editing mapping doesn't change `table`
+        del mapping[p1]
+
+        self.assertEqual(table[p1], ParameterReferences((ref0, ref1)))
+        self.assertEqual(table[p2], ParameterReferences((ref2,)))
+
+    def test_set_references(self):
+        """References replacement by parameter key."""
+
+        p1 = Parameter("theta")
+
+        ref0 = (RZGate(p1), 0)
+        ref1 = (RZGate(p1), 0)
+
+        table = ParameterTable()
+        table[p1] = ParameterReferences((ref0, ref1))
+        self.assertEqual(table[p1], ParameterReferences((ref0, ref1)))
+
+        table[p1] = ParameterReferences((ref1,))
+        self.assertEqual(table[p1], ParameterReferences((ref1,)))
+
+    def test_set_references_from_iterable(self):
+        """Parameter table init from iterable."""
+
+        p1 = Parameter("theta")
+
+        ref0 = (RZGate(p1), 0)
+        ref1 = (RZGate(p1), 0)
+        ref2 = (RZGate(p1), 0)
+
+        table = ParameterTable({p1: ParameterReferences((ref0, ref1))})
+        table[p1] = (ref2, ref1, ref0)
+
+        self.assertEqual(table[p1], ParameterReferences((ref2, ref1, ref0)))
+
+
 class TestParameterView(QiskitTestCase):
     """Test the ParameterView object."""