PauliGate and PauliString equality works only on odd exponents

[daxfohl]

Describe the issue

There's an inconsistency in how Pauli ops handle exponentiation and multiplication with respect to equality. While equality holds when the exponent is odd, it doesn't when the exponent is even.

import cirq
x = cirq.X(cirq.LineQubit(0))
print(1 * x == x)  # True
print(x * x == x**2)  # False
print(x * x * x == x**3)  # True
print(x * x * x * x == x**4)  # False
print(x * x * x * x * x == x**5)  # True
print(x * x * x * x * x * x == x**6)  # False
print(x * x * x * x * x * x * x == x**7)  # True

There may not be a way around this. The reason it doesn't hold for even exponents is that x * x evaluates to an empty PauliString(), as PauliString silently drops any identity qubits, whereas x**2 is still an XPowGate on a qubit.

The options I can think of would be (no particular order):

1. Modify PauliString to retain identity qubits, but I assume there's a reason it was designed the way it is, and/or would be a breaking change.
2. Change it so that PauliString and GateOperation[X/Y/ZPowGate] are not comparable, so both even and odd exponents return False.
3. Allow e.g. (X**2==PauliString()) == True. This would run into transitivity issues because we'd also need (Y**2==PauliString()) == True etc., but X**2 != Y**2. If we were to go with this option, we would likely need to create a universal Identity equality value, and have all "identity" ops be equal. On the surface, that actually seems kind of nice, an easy way to check if op==cirq.I generically, but note it would imply cirq.I(q1) == cirq.I(q2) for q1 != q2, which seems wrong.
4. Change it so that PauliString and GateOperation[X/Y/ZPowGate] are only comparable when the exponent is one. This also causes transitivity problems because x==x**3==x**5==.... So if x == PauliString(x) but x**3 != PauliString(x), that could lead to problems.
5. Leave things as-is.

Tell us the version of Cirq where this happens

1.6.1

[ToastCheng]

Hi @daxfohl! I'd like to give it a try, looking at the code, I think the problem is that the multiplication and power operations are either returning different types or not implemented. Feel free to assign to me.

[daxfohl]

@ToastCheng yeah that was my thought too. I started looking at it here main...daxfohl:fix-pauli-exponent, and really it just came down to implementing SingleQubitPauliStringGateOperation.__pow__, and having that and __mul__ return SingleQubitPauliStringGateOperation when possible. That actually made it possible to clean up a bunch of other code that worked around the lack of consistency in those operations.

The main challenge was with equality checking, as for backward consistency it was necessary to have some special handling for SingleQubitPauliStringGateOperation comparisons to raw PauliString, to raw GateOperations, to a special NotImplementedChecker and to have them all hash correctly.

I finally came up with something that worked for all existing tests (the linked branch), but as I started thinking about it more, something was nagging at me. It finally occurred to me that having even number exponents evaluate as equal may not be well-formed. If they do, then X**2 == X * X == PauliString() == Y * Y == Y**2. But X**2 != Y**2 in Cirq, and I don't think it'd be possible without some big changes that are probably breaking, so transitivity of equality would be lost, equal things would have different hashes, etc. Note this isn't a problem with odd exponents because their PauliString representations are all distinct.

So, IDK if that would be worse than the inconsistency presented in the issue or not. It kind of makes me think that maybe something is more fundamentally broken here. But, more eyes can help. Maybe there's an easy option I'm missing. Feel free to take a look!

[daxfohl]

@ToastCheng I went ahead and split this into two issues. I updated this one so it's just about equality of even/odd exponents, and it may end up being a "will not fix", given each of the alternatives seem to have concerns. (Though feel free to propose other options if you can think of any)! I'll unassign you from this issue for now since I think we need to establish consensus on whether we're going to do anything about it first.

The issue related to the TypeError exceptions, I extracted to #7588. AFAICT that should be tractable. Post something on that issue if you'd like to take it.