Fix moment commutation detection for group-commuting operations (#6659) #7082

chamodtharakaperera · 2025-02-23T17:02:39Z

This PR fixes an issue where cirq.commutes() incorrectly returns False for moments that commute as a whole even when their individual operations don't commute. For example, given two Z gates and an RXX gate, [Z⊗Z, RXX] = 0 even though neither Z commutes with RXX individually.

The solution:

First tries fast path of checking individual operation commutation
If individual operations don't commute or result is indeterminate, falls back to checking if the full moments commute via unitary calculation
Properly handles edge cases:
- Disjoint qubit sets (trivially commute)
- Non-unitary operations (returns NotImplemented)
- Indeterminate cases (returns NotImplemented)

Added comprehensive test cases covering:

Original Z⊗Z with RXX commutation case
Disjoint qubit operations
Mixed cases where some operations commute individually and others as a group
Non-commuting cases to verify negative results
Complex cases requiring unitary calculation

Test outputs demonstrate correct behavior for all cases including the original issue where Z⊗Z should commute with RXX.

Add pairwise commuting checks and, when inconclusive, fall back to full unitary commutator. Includes new tests showing Z⊗Z commutes with RXX. Fixes quantumlib#6659.

google-cla · 2025-02-23T17:02:44Z

Thanks for your pull request! It looks like this may be your first contribution to a Google open source project. Before we can look at your pull request, you'll need to sign a Contributor License Agreement (CLA).

View this failed invocation of the CLA check for more information.

For the most up to date status, view the checks section at the bottom of the pull request.

daxfohl · 2025-03-04T17:38:10Z

cirq-core/cirq/circuits/moment.py

+            return True
+
+        # If individual operations don't commute or we couldn't determine,
+        # try checking if the full moments commute using unitary matrices


Seems like this could be part of protocols.commutes itself. If that was the case then we'd have full coverage of stuff that commutes or not, at least for unitary things, but we can still override _commutes_ like here for perf reasons. @pavoljuhas wdyt?

working on it today, update soon ...

* prune duplicate or redundant test cases * reuse cirq.AmplitudeDampingChannel to test with non-unitary * move commute-related test functions together

Also check `measurement_key_objs` and `control_keys` active for checked Moments as in the Operation commutes protocol.

Adapt `cirq.ops.classically_controlled_operation_test.test_commute`

codecov · 2025-03-15T06:37:37Z

Codecov Report

All modified and coverable lines are covered by tests ✅

Project coverage is 98.13%. Comparing base (0d3c972) to head (c1351da).
Report is 1 commits behind head on main.

Additional details and impacted files

@@            Coverage Diff             @@
##             main    #7082      +/-   ##
==========================================
- Coverage   98.13%   98.13%   -0.01%     
==========================================
  Files        1093     1093              
  Lines       95528    95579      +51     
==========================================
+ Hits        93746    93796      +50     
- Misses       1782     1783       +1

☔ View full report in Codecov by Sentry.
📢 Have feedback on the report? Share it here.

🚀 New features to boost your workflow:

❄ Test Analytics: Detect flaky tests, report on failures, and find test suite problems.
📦 JS Bundle Analysis: Save yourself from yourself by tracking and limiting bundle sizes in JS merges.

pavoljuhas · 2025-03-15T06:40:17Z

The PR was failing some tests as they were initially on the main branch

git checkout a0b813812f41e5b2216c7794f0399451bdf44785
git checkout "HEAD^2" -- cirq-core/cirq/circuits/moment_test.py
check/pytest -n0 cirq-core/cirq/circuits/moment_test.py

...
FAILED cirq-core/cirq/circuits/moment_test.py::test_commutes - TypeError: Failed to determine whether or not cirq.Moment(

The Operation.commutes function is already doing some clever things like checking the measurement and control keys, as well, as making sure calculation of unitaries would not take too much memory.

I decided to reuse that code by converting Moment to CircuitOperation if needed and then falling back to the commutes evaluation for operations. Here is my take on it,

@chamodtharakaperera and @daxfohl - please let me know if this looks OK

daxfohl · 2025-03-15T17:22:30Z

Should that logic from Operation._commutes_ be moved into the commutes protocol itself? Usually when I see jumping through hoops to use logic from one class in another class, it means that the logic was in the wrong place to begin with. I'd say either move it up a layer (into the commutes protocol as a strategy) or down a layer into a shared library function. As is, I think it adds too many implicit dependencies and I'm also not sure there's not an infinite recursion in there somewhere.

Generalize `Operation._commutes_` in a shared internal function `_operations_commutes_impl`

No change in code function.

Also adjust `_operations_commutes_impl` to assume equal Moment-s and Operation-s commute.

pavoljuhas · 2025-03-17T21:42:15Z

Should that logic from Operation._commutes_ be moved into the commutes protocol itself? Usually when I see jumping through hoops to use logic from one class in another class, it means that the logic was in the wrong place to begin with. I'd say either move it up a layer (into the commutes protocol as a strategy) or down a layer into a shared library function. As is, I think it adds too many implicit dependencies and I'm also not sure there's not an infinite recursion in there somewhere.

@daxfohl - I feel it is better to keep the protocol implementation at its top level general and isolated from the details (and import dependencies) of Operation / Moment classes. The second suggestion sounds very good, here is my take on it - 2fee594...a55b675.
Can you PTAL?

daxfohl

Looks good. I added a note, but may be out of scope here. But if it's a simple change I think it'd be worth it.

cirq-core/cirq/ops/raw_types.py

cirq-core/cirq/circuits/moment.py

daxfohl · 2025-03-18T01:28:08Z

cirq-core/cirq/ops/raw_types.py

-            return NotImplemented
-
-        return np.allclose(m12, m21, atol=atol)
+        return _operations_commutes_impl([self], [other], atol=atol)


Should this also check commutes(other, self) for consistency?

AFAICT, the _operations_commutes_impl is symmetric in its arguments.
The protocol.commutes will also do it for us anyway.

- frozenset().union(*tuples) is faster than iterating over all items in every tuple to construct a frozenset. - base class Operation does not have `__hash__` method, therefore we cannot use `set(operations)`.

pavoljuhas · 2025-03-18T02:51:43Z

Thank you @chamodtharakaperera and @daxfohl !

…tumlib#6659) (quantumlib#7082) * Fix Moment.commutes_ to handle multi-qubit unitaries (quantumlib#6659) Add pairwise commuting checks and, when inconclusive, fall back to full unitary commutator. Includes new tests showing Z⊗Z commutes with RXX. Fixes quantumlib#6659. * Put back pre-existing commutation tests * prune duplicate or redundant test cases * reuse cirq.AmplitudeDampingChannel to test with non-unitary * move commute-related test functions together * Refactor `Moment._commutes_` to convert to CircuitOperation if necessary Also check `measurement_key_objs` and `control_keys` active for checked Moments as in the Operation commutes protocol. * Test commutation of moments with measurement keys and controls Adapt `cirq.ops.classically_controlled_operation_test.test_commute` * Small tweak of docstring * Add shared internal function _operations_commutes_impl Generalize `Operation._commutes_` in a shared internal function `_operations_commutes_impl` * Sync module variable name with circuit module name No change in code function. * Use shared _operations_commutes_impl for Moment._commutes_ Also adjust `_operations_commutes_impl` to assume equal Moment-s and Operation-s commute. * Few optimizations in _operations_commutes_impl - frozenset().union(*tuples) is faster than iterating over all items in every tuple to construct a frozenset. - base class Operation does not have `__hash__` method, therefore we cannot use `set(operations)`. --------- Co-authored-by: Pavol Juhas <juhas@google.com>

Fix Moment.commutes_ to handle multi-qubit unitaries (quantumlib#6659)

960ff75

Add pairwise commuting checks and, when inconclusive, fall back to full unitary commutator. Includes new tests showing Z⊗Z commutes with RXX. Fixes quantumlib#6659.

chamodtharakaperera requested review from vtomole and a team as code owners February 23, 2025 17:02

chamodtharakaperera requested a review from MichaelBroughton February 23, 2025 17:02

CirqBot added the size: M 50< lines changed <250 label Feb 23, 2025

Merge branch 'main' into bugfix/comute-moments

095c7ca

daxfohl reviewed Mar 4, 2025

View reviewed changes

pavoljuhas self-assigned this Mar 13, 2025

chamodtharakaperera and others added 6 commits March 13, 2025 16:08

Merge branch 'main' into bugfix/comute-moments

a0b8138

Put back pre-existing commutation tests

a38a3e1

* prune duplicate or redundant test cases * reuse cirq.AmplitudeDampingChannel to test with non-unitary * move commute-related test functions together

Refactor Moment._commutes_ to convert to CircuitOperation if necessary

518462a

Also check `measurement_key_objs` and `control_keys` active for checked Moments as in the Operation commutes protocol.

Test commutation of moments with measurement keys and controls

9f2af04

Adapt `cirq.ops.classically_controlled_operation_test.test_commute`

Small tweak of docstring

b6736c5

Merge branch 'main' into bugfix/comute-moments

2fee594

pavoljuhas added 3 commits March 17, 2025 14:28

Add shared internal function _operations_commutes_impl

f63b170

Generalize `Operation._commutes_` in a shared internal function `_operations_commutes_impl`

Sync module variable name with circuit module name

8db5c59

No change in code function.

Use shared _operations_commutes_impl for Moment._commutes_

a55b675

Also adjust `_operations_commutes_impl` to assume equal Moment-s and Operation-s commute.

daxfohl approved these changes Mar 18, 2025

View reviewed changes

cirq-core/cirq/ops/raw_types.py Outdated Show resolved Hide resolved

daxfohl reviewed Mar 18, 2025

View reviewed changes

cirq-core/cirq/circuits/moment.py Show resolved Hide resolved

daxfohl reviewed Mar 18, 2025

View reviewed changes

pavoljuhas added 2 commits March 17, 2025 19:34

Few optimizations in _operations_commutes_impl

93d09c7

- frozenset().union(*tuples) is faster than iterating over all items in every tuple to construct a frozenset. - base class Operation does not have `__hash__` method, therefore we cannot use `set(operations)`.

Merge branch 'main' into bugfix/comute-moments

c1351da

pavoljuhas approved these changes Mar 18, 2025

View reviewed changes

pavoljuhas enabled auto-merge March 18, 2025 02:51

pavoljuhas added this pull request to the merge queue Mar 18, 2025

Merged via the queue into quantumlib:main with commit ce31720 Mar 18, 2025
38 checks passed

mhucka mentioned this pull request Apr 18, 2025

Improve reporting of errors & efficiency of pr-size-labeler #7288

Merged

Provide feedback

Saved searches

Use saved searches to filter your results more quickly

Uh oh!

Fix moment commutation detection for group-commuting operations (#6659) #7082

Fix moment commutation detection for group-commuting operations (#6659) #7082

Uh oh!

chamodtharakaperera commented Feb 23, 2025

Uh oh!

google-cla bot commented Feb 23, 2025

Uh oh!

daxfohl Mar 4, 2025

Uh oh!

pavoljuhas Mar 15, 2025

Uh oh!

codecov bot commented Mar 15, 2025 •

edited

Loading

Uh oh!

pavoljuhas commented Mar 15, 2025

Uh oh!

daxfohl commented Mar 15, 2025

Uh oh!

pavoljuhas commented Mar 17, 2025

Uh oh!

daxfohl left a comment

Uh oh!

Uh oh!

Uh oh!

daxfohl Mar 18, 2025

Uh oh!

pavoljuhas Mar 18, 2025

Uh oh!

pavoljuhas commented Mar 18, 2025

Uh oh!

Uh oh!

Uh oh!

Fix moment commutation detection for group-commuting operations (#6659) #7082

Fix moment commutation detection for group-commuting operations (#6659) #7082

Uh oh!

Conversation

chamodtharakaperera commented Feb 23, 2025

Uh oh!

google-cla bot commented Feb 23, 2025

Uh oh!

daxfohl Mar 4, 2025

Choose a reason for hiding this comment

Uh oh!

pavoljuhas Mar 15, 2025

Choose a reason for hiding this comment

Uh oh!

codecov bot commented Mar 15, 2025 • edited Loading Uh oh! There was an error while loading. Please reload this page.

Uh oh!

Codecov Report

Uh oh!

pavoljuhas commented Mar 15, 2025

Uh oh!

daxfohl commented Mar 15, 2025

Uh oh!

pavoljuhas commented Mar 17, 2025

Uh oh!

daxfohl left a comment

Choose a reason for hiding this comment

Uh oh!

Uh oh!

Uh oh!

daxfohl Mar 18, 2025

Choose a reason for hiding this comment

Uh oh!

pavoljuhas Mar 18, 2025

Choose a reason for hiding this comment

Uh oh!

pavoljuhas commented Mar 18, 2025

Uh oh!

Uh oh!

Uh oh!

codecov bot commented Mar 15, 2025 •

edited

Loading