Qiskit / qiskit / 25514239653

88%

main: 88%

Build Type

push

github

Committed by web-flow

Commit Message

Parallelize the CommutationAnalysis pass (#16014)

* Parallelize the CommutationAnalysis pass

Building on top of #15988 which removed the internal caching from the
commutation checker. This commit parallelizes the commutation analysis
pass so that the analysis per qubit is done in multiple threads and
aggregated together in the end. The speed-up this enables is fairly
modest because we're spending more of the time in the serial portion of
the pass. But even so it's a simple code change that does speed the pass
and by extension CommutativeCancellation.

In general the pass could probably use a rearchitecting as I think a lot
of the issues stem with how it's collecting data which seems overly
specific to how the pass worked from Python. However, since there is a
CommutativeOptimization pass that is designed to replace the
CommutationAnalysis/CommutativeCancellation passes spending too much
time on this is probably not worth it.

The other change made to facilitate this is removing the scratch map
from the CommutationChecker. Specifically this required mutable access
to check if two gates commute but in a parallel context we won't be able
to get mutable access. This scratch space isn't a huge speedup as it
just saved an allocation when checking PPR commutations.

* Avoid IndexMap usage inside the pass

This commit moves away from using an IndexMap for the CommutationSet and
NodeIndices types and replaces both with an outer Vec. They were both
keyed on qubits which is a contiguous range of 0..N_u32. A vec is more
natural for this at the cost of allocating and creating a vec large enough
to store all the qubits even if there isn't an entry for each qubit.

This will have two advantages the first for the parallel path in this PR
this will result in a deterministic iteration order when we build the
output dict for the python pass. The second is it should be even faster
both for the serial and parallel.

* Fix rebase issues and run cargo fmt

* Propogate PyE... (continued)

Coverage Stats

100 of 107 new or added lines in 3 files covered. (93.46%)

27 existing lines in 3 files now uncovered.

106988 of 122124 relevant lines covered (87.61%)

963943.02 hits per line