Improve coverage of _decompose_into_clifford_with_qubits_ and has_stabilizer_effect protocols

[tanujkhattar]

Is your feature request related to a use case or problem? Please describe.
The two protocols were added to Cirq to support fast stabilizer simulations for (mostly) Clifford operations. See #2600 (review) and #2423 for historical context.

However, the coverage of these two protocols across Cirq gates is not great. For example;

>>> cirq.has_stabilizer_effect(cirq.XX)
False # Should be true.
>>> hasattr(cirq.XX, '_decompose_into_clifford_with_qubits_')
True
>>> hasattr(cirq.ZZ, '_decompose_into_clifford_with_qubits_')
False # Should be true?

Describe the solution you'd like
This feature request is to improve the coverage of has_stabilizer_effect and _decompose_into_clifford_with_qubits_ protocols so that:

1. For all out gates defined by Cirq, users can easily identify whether the gate is a Clifford or not by calling these protocols.
2. Consider adding a cirq.is_clifford protocol which fallbacks to cirq.decompose to figure out if the current gate is a clifford or not by recursively checking whether all gates that the current gate decomposes into are cliffords or not.
3. Add consistency checks as part of assert_implements_consistent_protocols

What is the urgency from your perspective for this issue? Is it blocking important work?
P1 - I need this no later than the next release (end of quarter)

[tanujkhattar]

@NoureldinYosri Do you want to take a stab at this issue?

[NoureldinYosri]

@tanujkhattar sure, can you assign it to me?

[NoureldinYosri]

there are two ways to do this

1. Bruteforce add has_stabilizer_effect and _decompose_into_clifford_with_qubits_ to more gate classes.
2. Implement an algorithm that checks if a general unitary is a clifford operator (e.g. https://quantumcomputing.stackexchange.com/a/13158) and use it when the number of qubits of the operation is small (e.g. $\leq 4$) and for operations on more qubits fallback to the checking its decomposition.

The second option is more scalable and should be fast enough since we will only apply it when the unitary is relatively small.

[tanujkhattar]

Should we do both? We can make quick improvements to has_stabilizer_effect and _decompose_into_clifford_with_qubits_ to improve coverage (this should take a few days) and then also implement the algorithm to check if a general unitary is a clifford or not (this can take a few weeks)?

I think there is value in getting a quick fix for this this one; unless we think the general algorithm can be implemented within a week or two. What do you think?

[NoureldinYosri]

I have a prototype for the algorithm so it shouldn't take long to get it in a decent shape and create a PR.

A minor issue of the algorithm is that it is a numerical algorithm so what we get in the end is a check that depends on the tolerance we use (yes means definatly a clifford, no means maybe a larger tolerance could turn it to yes).

so the algorithm is would be a quick fix.. but adding the has_stabilizer_effect and _decompose_into_clifford_with_qubits_ to the most commonly used gates should also be done before closing this issue

[NoureldinYosri]

I compiled a list of classes that I think should be covered by the protocols inorder to achieve the goal of this issue:

• cirq.ops.clifford_gate.CliffordGate
• cirq.ops.dense_pauli_string.DensePauliString
• cirq.ops.parity_gates.XXPowGate
• cirq.ops.parity_gates.YYPowGate
• cirq.ops.parity_gates.ZZPowGate
• cirq.ops.pauli_interaction_gate.PauliInteractionGate
• cirq.ops.pauli_string_phasor.PauliStringPhasorGate
• cirq.ops.pauli_measurement_gate.PauliMeasurementGate
• cirq.ops.boolean_hamiltonian.BooleanHamiltonianGat

Most of these gates have _decompose_ method defined that yields clifford gates so _decompose_into_clifford_with_qubits_ would just copy that decomposition.