Oxidize commutative cancellation

sbrandhsn commented 3 weeks ago

Summary

fixes https://github.com/Qiskit/qiskit/issues/12270

Details and comments

This replaces the Python implementation of CommutativeCancellation with a Rust implementation:

As the Rust implementation does not use the PassManager to run its prerequisite CommutationAnalysis, the test case has been test_callback_with_pass_requires fixed. We might be able to remove that test case as the check is already covered in https://github.com/Qiskit/qiskit/blob/52733ae09f7ac9d2d5e2a674970ff95301d34bd6/test/python/transpiler/test_pass_scheduler.py#L111
The global phase was probably incorrectly set in the Python implementation in https://github.com/Qiskit/qiskit/blob/f4ca088644b4461b856b4b49c33e23b04a995019/qiskit/transpiler/passes/optimization/commutative_cancellation.py#L195, I changed this in the Rust implementation
Currently, control-flow operations are handled in Python - I'm looking into a Rust implementation for that too

Speedups (this branch vs Qiskit 1.2)

Top to bottom Clifford circuits, random circuits, random circuits with rotation gates only

Up to 5.5x speedup for Clifford circuits where the commutation relation of two gates is always determined by a look-up in an a priori constructed commutation library. Up to 7.0 speedup for random circuits as generated by random_circuit and up to 8x speedup when restricting that random circuit to rotational gates only. Note this benchmark compares end-to-end performance as given by

            pm = PassManager([CommutativeCancellation(target=be.target)])
            start_ts = time.time()
            pm.run(qc)
            end_ts = time.time()

instead of only comparing a python implementation of CommutativeCancellation with underlying Rust code vs a rust implementation of CommutativeCancellation with the same underlying code.

qiskit-bot commented 3 weeks ago

One or more of the following people are relevant to this code:

@Qiskit/terra-core
@kevinhartman
@mtreinish

coveralls commented 3 weeks ago

Pull Request Test Coverage Report for Build 10797636548

Warning: This coverage report may be inaccurate.

This pull request's base commit is no longer the HEAD commit of its target branch. This means it includes changes from outside the original pull request, including, potentially, unrelated coverage changes.

For more information on this, see Tracking coverage changes with pull request builds.
To avoid this issue with future PRs, see these Recommended CI Configurations.
For a quick fix, rebase this PR at GitHub. Your next report should be accurate.

Details

170 of 190 (89.47%) changed or added relevant lines in 7 files are covered.
127 unchanged lines in 7 files lost coverage.
Overall coverage decreased (-0.04%) to 89.134%

Changes Missing Coverage	Covered Lines	Changed/Added Lines	%
crates/accelerate/src/commutation_cancellation.rs	155	175	88.57%
<!--	Total:	170	190	89.47%	-->

Files with Coverage Reduction	New Missed Lines	%
qiskit/synthesis/one_qubit/one_qubit_decompose.py	1	70.67%
qiskit/transpiler/passes/synthesis/unitary_synthesis.py	2	88.26%
crates/qasm2/src/lex.rs	5	92.48%
crates/qasm2/src/parse.rs	6	97.61%
qiskit/synthesis/two_qubit/xx_decompose/decomposer.py	6	90.84%
crates/circuit/src/dag_node.rs	11	78.55%
qiskit/circuit/quantumcircuit.py	96	93.25%
<!--	Total:	127	-->

Totals
Change from base Build 10774677144:	-0.04%
Covered Lines:	73092
Relevant Lines:	82002

💛 - Coveralls

mtreinish commented 3 weeks ago

Oh also can you please rebase this on main so the commit history is just the local changes. While the final diff is ok, it makes the commit message and authors list for this PR the sum of all the commits on the branch, which is much larger than the actual work being done here.

Qiskit / qiskit