Add `IdentityGate._commutes_`

[perlinm]

I wrote a custom stabilizer-like simulator in Cirq for this paper (arXiv), which involved commuting Pauli strings through circuit operations. The speed of my simulations turned out to be limited by calls to protocols.commutes inside MutablePauliString.inplace_after. I found that checking conditions for commutation "manually" led to considerable speedups, and figured I could push this change upstream.

Long story short: two Pauli operators P and Q commute iff (one of P or Q is the identity operator, or P == Q).

As an example, on my laptop the changes in this PR reduce the runtime of the script below from ~2 minutes to ~39 seconds.

#!/usr/bin/env python3
import random

import cirq

# random Clifford circuit
circuit = cirq.testing.random_circuit(
    qubits=cirq.LineQubit.range(10),
    n_moments=100,
    op_density=0.5,
    gate_domain={cirq.Z: 1, cirq.H: 1, cirq.S: 1, cirq.CX: 2, cirq.CZ: 2},
    random_state=0,
)

# propagate random Pauli strings through the Clifford circuit
for seed in range(10_000):
    random.seed(seed)
    pauli_ops = {
        qubit: random.choice([cirq.I, cirq.X, cirq.Y, cirq.Z])
        for qubit in circuit.all_qubits()
    }
    string = cirq.PauliString(pauli_ops).mutable_copy()
    string.inplace_after(circuit)

[perlinm]

It occurs to me that there are other places in the changed file that check for commutation of two Pauli operators. Perhaps I should just add a _pauli_commutes method to the file, and use that everywhere within?

EDIT: done

[perlinm]

If I work with the commutes protocol, it looks like one neat option is to add something like

    def _commutes_(self, other: Any, *, atol: float = 1e-8) -> bool:
        return True

to cirq.ops.identity.IdentityGate. That results in a nearly identical speedup of 2 min --> 40 sec in my original example.

This change seems reasonable because an identity gate commutes with everything, but I'm not sure whether IdentityGate._commutes_ should return NotImplemented for certain "invalid" types of other. Thoughts?

[vtomole]

What sorts of  "invalid" types come to mind?

[perlinm]

None come to mind for me 🙂

If you think that addition to IdentityGate is good, I'll just go ahead and add it.

[vtomole]

The change to IdentityGate sounds good to me.

[pavoljuhas]

This change seems reasonable because an identity gate commutes with everything, but I'm not sure whether IdentityGate._commutes_ should return NotImplemented for certain "invalid" types of other. Thoughts?

Using the IdentityGate option sounds great. The current IdentityGate._commutes_ inherits from the Gate which returns NotImplemented for non-gate arguments. I think we should keep that behavior, because it can expose bugs in the calling code.

We don't need to redo the qid_shape check (line 477), because IdentityGate behaves as a plain wire which commutes.

https://github.com/quantumlib/Cirq/blob/8d8a6c57fd5c0117026357d4b3ad8662f787235c/cirq-core/cirq/ops/raw_types.py#L472-L481

[perlinm]

@pavoljuhas great! I think checking for Gate types covers my worries about invalid inputs.

How are the current proposed changes? I'm not sure what kind of test makes sense for IdentityGate._commutes_...

[codecov[bot]]

Codecov Report

All modified and coverable lines are covered by tests :white_check_mark:

Project coverage is 97.83%. Comparing base (8d8a6c5) to head (23a7480). Report is 1 commits behind head on main.

Additional details and impacted files

```diff @@ Coverage Diff @@ ## main #6702 +/- ## ======================================= Coverage 97.83% 97.83% ======================================= Files 1077 1077 Lines 92493 92502 +9 ======================================= + Hits 90492 90501 +9 Misses 2001 2001 ```

:umbrella: View full report in Codecov by Sentry.
:loudspeaker: Have feedback on the report? Share it here.

[perlinm]

My thinking was to ensure that this test calls IdentityGate._commutes_, rather than deciding that cirq.I commutes with cirq.X for independent reasons. I'm happy to change it back though if you prefer.

[vtomole]

change it back though if you prefer.

Let's do that. We try to write tests the way an external user would call the API.

[perlinm]

Makes sense. Done.