Library of Unparameterizable Standard Gates Commutations

[sbrandhsn]

Summary

Addresses #8020 and #7101

Details and comments

Currently, when a transpiler pass needs to be informed by the commutation relation of a pair of quantum gates with matrices A and B, a matrix multiplication AB - BA is performed and checked against zero. The result of this check is cached and potentially reused by the same transpiler pass run. The cache is reset after the transpiler pass requiring the commutation information has been executed.

In this pull request, a commutation library is introduced. The commutation library consists of precomputed commutation relations of all pair of standard gates that are not parameterizable. When a commutation between a pair of quantum gates should now be determined, the CommutationChecker first checks the commutation library for an entry, before trying the commutation cache and eventually falling back on previous matrix multiplication. In detail, the following is added

• An implementation for generating a commutation library for the set of unparameterized standard gates.
• An efficient query of the commutation library and cached commutations before resorting to matrix multiplication.
• A space- and runtime-efficient key for querying the commutation of a pair of quantum gates with a given gate qubit overlap.
• A commutation cache that persists over different transpiler pass runs in the same qiskit execution when using SessionCommutationChecker.
• Updated test cases for the commutation library.

Ideally, one would also like to store the commutation of parameterizable quantum gates, i.e. rz, rx and so on. My first approach was to use SymPy to generate a symbolic expression for the commutator of these quantum gates and solve the participating rotational angles for zero. However, SymPy does not return all possible solutions for that commutator expression, which is what one would like to have in the ideal case as it then defines for what parameter regimes a pair of quantum gates commutes or does not commute. It also does not inform an user whether the solution set is complete or not (but that might be user error :-)). Apparently, SymPy is not at fault and solving these kinds of symbolic expression is likely undecidable when they involve exponential functions and definitely undecidable when they involve e.g. the sine function. I still think that for the kind of equations arising from commutators there should be some solution and will look into it a bit more.

Runtime

This section compares the runtime of circuit_to_dagdependency with only cached commutations and this pull request that combines cached commutations with a commutation library. The investigated quantum circuits are generated through random_circuit while omitting any parameterizable quantum gates. For each pair of depth and number of qubits 10 random circuits where generated and fed into the old commutation checker and this pull request.

Cached Commutations Only (Previous) - Single Random Circuit

Commutation Library - Single Random Circuit

All random circuits

Cached only	Commutation Library

These figures show that the runtime speedup is more pronounced for small-scale quantum circuits. In larger quantum circuits on a limited set of quantum gates, the cached commutations will eventually contain all relevant commutation and the matrix multiplication may amortize. The exact runtime speedup will depend on the transpilation task.

All random circuits comparison

For random circuits with 16 qubits and approximately 50 gates depth, we can see a roughly halved runtime.

[qiskit-bot]

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

• @Qiskit/terra-core

[coveralls]

Pull Request Test Coverage Report for Build 7728728139

• -4 of 134 (97.01%) changed or added relevant lines in 6 files are covered.
• 7 unchanged lines in 2 files lost coverage.
• Overall coverage increased (+0.03%) to 89.609%

---

Changes Missing Coverage	Covered Lines	Changed/Added Lines	%
qiskit/circuit/commutation_checker.py	117	121	96.69%

Files with Coverage Reduction	New Missed Lines	%
crates/qasm2/src/lex.rs	1	92.7%
crates/qasm2/src/parse.rs	6	97.62%

Totals
Change from base Build 7728099338:	0.03%
Covered Lines:	59402
Relevant Lines:	66290

---

💛 - Coveralls

[alexanderivrii]

In general the changes look great. I have already left a few comments and questions. In addition, a few more things that I would like to ask:

How does keeping a single SessionCommutationChecker and increasing the number of qubits to 4 for commutativity analysis affect transpile memory/runtime on "standard" circuits? Could you for instance check what happens on our ASV benchmarks?

Would it be possible to avoid loading the SessionCommutationChecker if it's not used by any transpiler pass?

In addition, could you please add a few more tests exercising different paths of storing/retrieving commutation results, such as for when we have None for some relative qubit placements or when we have gates with parameters (e.g., LinearFunctions).

[alexanderivrii]

I like the idea to have the limit on the maximum number of cached entries. If I understand correctly, currently if the limit is reached the full cache would be cleared. I guess in theory we could add tracking for how many times a specific entry was checked and evict less useful entries, but this can be done in a follow-up PR (and only if you think it's worthwhile to do this).

[sbrandhsn]

Yes, that is behaviour. I think what we should do ideally is to use the lru_cache decorator for the _commute_matmul function. However, I see two obstacles:

• We would need to get the gate object from the gate name as the Operation object is not hashable for some gates.
• We would need to pass the hashed version of the gate parameters in _commute_matmul and then reconstruct the gate parameter values inside that function. This is because the lru_cache decorator does not allow to set a custom key for a function signature or to omit some of the parameters. At least not in Python 3.7. It should be possible with cachetools but I don't think it makes sense to add a new requirement to qiskit because of this. :-) I'm also not in favour of developing an LRU cache ourselves...

[sbrandhsn]

Thank you for agreeing to review and sorry for the delay. Let me know if there are any further questions or changes you would like to see! I removed SessionCommutationChecker from the init file, so it should not be loaded unless required by a transpilation pass.

[alexanderivrii]

Thanks @sbrandhsn, this looks great. I have left a few minor comments related to the description/documentation, and I am happy to approve the PR once you take a look at these.

[alexanderivrii]

Are _cache_miss and _cache_hit used anywhere?

[sbrandhsn]

I found it useful to have these fields for validating the commutation checker. I can remove it if you think that would improve the code but I would prefer to keep them. So far these two fields are only used in TestCommutationChecker

[Cryoris]

I'm impressed by the amount of checking that this required! But I'm wondering if we could represent (or infer) some of these relations more efficiently than to hardcode them. My main concern here is that a hardcoded table can be challenging to maintain and adding new standard gates comes at quite an overhead. For example

• the id clearly commutes with any gate, is this something the compiler should know natively? Right now, adding a new standard gate would require adding an entry here, which is maybe not optimal.
• any diagonal gate commute with controls
• two controlled gates on any number of controls, C^m A and C^n B, commute if they act on the same and A and B commute

I might also have missed some discussion on this, sorry if this is the case! 🙂

[sbrandhsn]

Well, it is my first larger PR so far, so I expected a bit more back and forth. Thanks, @alexanderivrii ! :-)

I agree that commutation passes should know the commutation of gates such as id or gates that do not overlap at all natively. There is some work on the commutation analysis pass as far as I know - maybe this can be addressed in that context.

I agree that some of these relations can be stored more efficiently. However, the lookup of these relations must also be quicker than the corresponding matrix multiplications and another challenge is that these rules should be exhaustive for non-commutation and for commutation. Otherwise, we will need to resort to matrix multiplication again. I guess that we could add a function that is executed before the commutation library is queried to check for these rules but the runtime of the included checks must be offset by their applicability.

Regarding maintenance: ideally you would run something like build_commutation_library and validate_commutation_library to add a new standard gate. The corresponding diff should only show the new entries.

[alexanderivrii]

This looks good -- thanks for the hard work!

In addition, many thanks for the improved documentation/comments, it's now completely clear how the commutation library should be interpreted.

I have added suggestions for two small tweaks to the release notes, please take a look.

The only other minor question is whether the python code to build the default commutation library should be under qiskit (it currently in under qiskit/circuit/tools) or some other location (maybe the top-level tools directory containing things like update_fake_backends.py). @Cryoris or @jakelishman , could you please provide a quick feedback on this?

After this it's good to go.

P.S. There are a few interesting directions for the follow-up work that were raised in various discussions: extending the format and the commutation checks to handle parameterized gates, storing commutativity relations more efficiently, implementing other methods for deducing commutativity (#11192 (comment)).

[alexanderivrii]

Thanks for the quick changes!

[jakelishman]

I'm just quickly disembarking this from the queue so we can push through #10998 first, because it's too liable to get out of sync (including with this PR). As soon as that's in the queue, we can re-embark this.

[jakelishman]

Okey dokey - the minor conflicts that have just popped up are why #10998 needed to jump ahead. It should hopefully be trivial to fix them, then this can re-embark.

[mtreinish]

Just mirroring @alexanderivrii's earlier approval here to re-enqueue this for merging after the merge conflicts were fixed (which I confirmed are the only changes since the approval).