Optimise `QuantumCircuit.assign_parameters` for single-parameter binding #10548

jakelishman · 2023-08-02T17:07:12Z

Summary

When assigning parameters in a heavily parametrised circuit, a significant amount of time was spent constructing a new set of all the Parameter instances used in a circuit. This completely dominated the execution time for the case of binding a single parameter out of a many-parameters circuit in place.

This modifies the internal-only method
QuantumCircuit._unsorted_parameters to directly return the set object already constructed by the ParameterTable tracking the operations, which makes the function close to free to call, at the cost that internal users of that function must take care not to mutate the output. This is not generally a problem, since no code in Terra outside of QuantumCircuit uses that method (nor should it!), and QuantumCircuit never needs to mutate that set.

Details and comments

Given setup code:

from qiskit.circuit import QuantumCircuit, ParameterVector
from qiskit.circuit.library import ECRGate

ecr_singleton = ECRGate()
num_qubits = 100
depth = 1000
ps_outer = ParameterVector("theta", 3 * num_qubits * (depth + 1))

def twirled_circuit():
    qc = QuantumCircuit(num_qubits)
    ps = iter(ps_outer)
    for _ in range(depth):
        for i in range(num_qubits):
            qc.rz(next(ps), i)
            qc.ry(next(ps), i)
            qc.rz(next(ps), i)
        for a in range(0, num_qubits - 1, 2):
            qc.append(ecr_singleton, [a, a+1], [])
        for a in range(1, num_qubits - 1, 2):
            qc.append(ecr_singleton, [a, a+1], [])
    for i in range(num_qubits):
        qc.rz(next(ps), i)
        qc.ry(next(ps), i)
        qc.rz(next(ps), i)
    return qc

qc = twirled_circuit()

this PR now takes 3.51(6)s on my machine to run:

for p in ps_outer:
    qc.assign_parameters({p: 0.5}, strict=False, flat_input=True, inplace=True)

Before this PR, that would have taken 30 minutes to an hour by my very approximate estimate.

To compare, one might have achieved the same thing using internal methods in Terra 0.24.2 that were removed in #10284 with:

from p in ps_outer:
    qc._assign_parameter(p, 0.5)

which took 3.03(5)s on my machine. There's a little more overhead in the new form (~15%), most likely from the additional cost to build the dicts, but that's hopefully acceptable given that a) it now uses only public methods and b) the new form is more efficient for full binding of ParameterVector elements against array and massively more efficient for binding wrapped instructions as used by algorithms.

cc: @chriseclectic.

When assigning parameters in a heavily parametrised circuit, a significant amount of time was spent constructing a new set of all the `Parameter` instances used in a circuit. This completely dominated the execution time for the case of binding a single parameter out of a many-parameters circuit in place. This modifies the internal-only method `QuantumCircuit._unsorted_parameters` to directly return the set object already constructed by the `ParameterTable` tracking the operations, which makes the function close to free to call, at the cost that internal users of that function must take care not to mutate the output. This is not generally a problem, since no code in Terra outside of `QuantumCircuit` uses that method (nor should it!), and `QuantumCircuit` never needs to mutate that set.

qiskit-bot · 2023-08-02T17:07:15Z

One or more of the the following people are requested to review this:

@Qiskit/terra-core

coveralls · 2023-08-02T17:39:58Z

Pull Request Test Coverage Report for Build 5741733957

5 of 5 (100.0%) changed or added relevant lines in 1 file are covered.
10 unchanged lines in 2 files lost coverage.
Overall coverage decreased (-0.005%) to 85.892%

Files with Coverage Reduction	New Missed Lines	%
crates/qasm2/src/lex.rs	4	91.39%
crates/qasm2/src/parse.rs	6	96.67%

Totals
Change from base Build 5727764372:	-0.005%
Covered Lines:	73062
Relevant Lines:	85063

💛 - Coveralls

Cryoris · 2023-08-16T09:10:10Z

qiskit/circuit/quantumcircuit.py

@@ -2632,14 +2632,26 @@ def parameters(self) -> ParameterView:
    @property
    def num_parameters(self) -> int:
        """The number of parameter objects in the circuit."""
+        # Avoid a (potential) object creation if we can.
+        if self._parameters is not None:
+            return len(self._parameters)
        return len(self._unsorted_parameters())


In the current format calling num_parameters would call _unsorted_parameters every time if _parameters is not yet set. Since sorting the parameters wouldn't be a big overhead once we gather them, how about replacing this whole property simply by

return len(self.parameters)

?

That would be a bit more expensive the first time, since it sorts the parameters on top of gathering them, but then the cached _parameters would be set.

Sorting the parameters actually is a big overhead - it scales as O(n lg(n)) in number of parameters and for PEC-style circuits that's a lot of parameters. One of the things I needed to make sure of in #10284 was that the sort cache was maintained when normalising the inputs for inplace=True because it tanked performance if it was lost. I also had to optimise the comparison key there because it was really showing up in benchmarking, and in the case of assigning single parameters, we're going to lose the cache each time which would mean that a subsequent num_parameters would retrigger it.

If parameters only get bound in the dictionary format only, then we never need to pay the sort cost at all in this format, and num_parameters would still avoid it.

The QuantumCircuit.parameters getter also (unfortunately) creates a new set object on every call, which is quite unfortunate for a property, really. It's potentially worth a follow-up PR to change the internal cache to a frozenset so we can return it directly, although it's annoying that that would be a breaking API change.

The QuantumCircuit.parameters getter also (unfortunately) creates a new set object on every call, which is quite unfortunate for a property, really. It's potentially worth a follow-up PR to change the internal cache to a frozenset so we can return it directly, although it's annoying that that would be a breaking API change.

That would mean changing from a sorted ParameterView to returning a set of the parameters? Yeah would be worth a discussion whether sorting only when we really need to is better. A first issue that comes to mind is that users can no longer easily check the order of parameters and that binding via dict(zip(circuit.parameters, values)) isn't valid anymore.

I'm not proposing removing the sort from QuantumCircuit.parameters, this is just avoiding producing new temporary collections when we can get use data from something else already. The other part is that the parameters field is marked as an attribute, but it actually does a non-trivial amount of work to get itself; even if _parameters is cached, it returns a copy of it. It does that so a user can't mutate the inners of QuantumCircuit, but it comes with the cost of these performance bugs; it's not at all clear from accessing qc.parameters that what you're actually getting is amortised qc._parameters.copy(), which is somewhat costly for large numbers of parameters.

coveralls · 2023-08-31T11:40:57Z

Pull Request Test Coverage Report for Build 6036368171

5 of 5 (100.0%) changed or added relevant lines in 1 file are covered.
4 unchanged lines in 1 file lost coverage.
Overall coverage increased (+0.001%) to 87.294%

Files with Coverage Reduction	New Missed Lines	%
crates/qasm2/src/lex.rs	4	91.39%

Totals
Change from base Build 6036244196:	0.001%
Covered Lines:	74407
Relevant Lines:	85237

💛 - Coveralls

Cryoris · 2023-09-15T07:44:17Z

qiskit/circuit/quantumcircuit.py

+            The returned object may directly view onto the ``ParameterTable`` internals, and so
+            should not be mutated.  This is an internal performance detail.  Code outside of this
+            package should not use this method.


Do you want to link the object here?

Suggested change

The returned object may directly view onto the ``ParameterTable`` internals, and so

should not be mutated. This is an internal performance detail. Code outside of this

package should not use this method.

The returned object may directly view onto the :class:`.ParameterTable` internals, and so

should not be mutated. This is an internal performance detail. Code outside of this

package should not use this method.

ParameterTable isn't part of the documented API, since it's only meant to be used in the private QuantumCircuit._parameters, so there's no actual cross-ref that'll work for it. That said, this whole docstring is for a private method and not documented itself haha. (I guess I just wrote rST by force of habit)

jakelishman requested a review from a team as a code owner August 2, 2023 17:07

jakelishman mentioned this pull request Aug 2, 2023

Add fast path to Parameter.assign #10549

Merged

jakelishman added performance Changelog: New Feature Include in the "Added" section of the changelog labels Aug 2, 2023

mtreinish added this to the 0.45.0 milestone Aug 10, 2023

Cryoris reviewed Aug 16, 2023

View reviewed changes

Merge branch 'main' into optimise-unsorted-parameters

8c38277

jakelishman requested a review from Cryoris September 6, 2023 10:58

Cryoris reviewed Sep 15, 2023

View reviewed changes

Cryoris approved these changes Sep 15, 2023

View reviewed changes

Cryoris added this pull request to the merge queue Sep 15, 2023

Merged via the queue into Qiskit:main with commit 05e24d5 Sep 15, 2023

jakelishman deleted the optimise-unsorted-parameters branch September 15, 2023 12:25

Provide feedback

Saved searches

Use saved searches to filter your results more quickly

Uh oh!

Optimise `QuantumCircuit.assign_parameters` for single-parameter binding #10548

Optimise `QuantumCircuit.assign_parameters` for single-parameter binding #10548

Uh oh!

jakelishman commented Aug 2, 2023

Uh oh!

qiskit-bot commented Aug 2, 2023

Uh oh!

coveralls commented Aug 2, 2023

Uh oh!

Cryoris Aug 16, 2023

Uh oh!

jakelishman Aug 21, 2023

Uh oh!

Cryoris Sep 15, 2023

Uh oh!

jakelishman Sep 15, 2023

Uh oh!

coveralls commented Aug 31, 2023

Uh oh!

Cryoris Sep 15, 2023

Uh oh!

jakelishman Sep 15, 2023 •

edited

Loading

Uh oh!

Uh oh!

Optimise QuantumCircuit.assign_parameters for single-parameter binding #10548

Optimise QuantumCircuit.assign_parameters for single-parameter binding #10548

Uh oh!

Conversation

jakelishman commented Aug 2, 2023

Summary

Details and comments

Uh oh!

qiskit-bot commented Aug 2, 2023

Uh oh!

coveralls commented Aug 2, 2023

Pull Request Test Coverage Report for Build 5741733957

💛 - Coveralls

Uh oh!

Cryoris Aug 16, 2023

Choose a reason for hiding this comment

Uh oh!

jakelishman Aug 21, 2023

Choose a reason for hiding this comment

Uh oh!

Cryoris Sep 15, 2023

Choose a reason for hiding this comment

Uh oh!

jakelishman Sep 15, 2023

Choose a reason for hiding this comment

Uh oh!

coveralls commented Aug 31, 2023

Pull Request Test Coverage Report for Build 6036368171

💛 - Coveralls

Uh oh!

Cryoris Sep 15, 2023

Choose a reason for hiding this comment

Uh oh!

jakelishman Sep 15, 2023 • edited Loading Uh oh! There was an error while loading. Please reload this page.

Uh oh!

Choose a reason for hiding this comment

Uh oh!

Uh oh!

Optimise `QuantumCircuit.assign_parameters` for single-parameter binding #10548

Optimise `QuantumCircuit.assign_parameters` for single-parameter binding #10548

jakelishman Sep 15, 2023 •

edited

Loading