pauli_string.py

# Copyright 2018 The Cirq Developers
#
# Licensed under the Apache License, Version 2.0 (the "License");
# you may not use this file except in compliance with the License.
# You may obtain a copy of the License at
#
#     https://www.apache.org/licenses/LICENSE-2.0
#
# Unless required by applicable law or agreed to in writing, software
# distributed under the License is distributed on an "AS IS" BASIS,
# WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
# See the License for the specific language governing permissions and
# limitations under the License.
import cmath
import math
import numbers
from typing import (
    Any,
    cast,
    Dict,
    ItemsView,
    Iterable,
    Iterator,
    KeysView,
    List,
    Mapping,
    Optional,
    overload,
    Sequence,
    SupportsComplex,
    Tuple,
    TYPE_CHECKING,
    TypeVar,
    Union,
    ValuesView,
    AbstractSet,
    Callable,
    Generic,
)

import numpy as np

from cirq import value, protocols, linalg, qis
from cirq._doc import document
from cirq.ops import (
    clifford_gate,
    common_gates,
    gate_operation,
    global_phase_op,
    identity,
    op_tree,
    pauli_gates,
    pauli_interaction_gate,
    raw_types,
)
from cirq.type_workarounds import NotImplementedType

if TYPE_CHECKING:
    import cirq

TDefault = TypeVar('TDefault')
TKey = TypeVar('TKey', bound=raw_types.Qid)
TKeyNew = TypeVar('TKeyNew', bound=raw_types.Qid)
TKeyOther = TypeVar('TKeyOther', bound=raw_types.Qid)

# A value that can be unambiguously converted into a `cirq.PauliString`.

PAULI_STRING_LIKE = Union[
    complex,
    'cirq.OP_TREE',
    Mapping[TKey, 'cirq.PAULI_GATE_LIKE'],
    Iterable,  # of PAULI_STRING_LIKE, but mypy doesn't do recursive types yet.
]
document(
    PAULI_STRING_LIKE,  # type: ignore
    """A `cirq.PauliString` or a value that can easily be converted into one.

    Complex numbers turn into the coefficient of an empty Pauli string.

    Dictionaries from qubit to Pauli operation are wrapped into a Pauli string.
    Each Pauli operation can be specified as a cirq object (e.g. `cirq.X`) or as
    a string (e.g. `"X"`) or as an integer where 0=I, 1=X, 2=Y, 3=Z.

    Collections of Pauli operations are recursively multiplied into a single
    Pauli string.
    """,
)

PAULI_GATE_LIKE = Union[
    'cirq.Pauli',
    'cirq.IdentityGate',
    str,
    int,
]
document(
    PAULI_GATE_LIKE,  # type: ignore
    """An object that can be interpreted as a Pauli gate.

    Allowed values are:

    1. Cirq gates: `cirq.I`, `cirq.X`, `cirq.Y`, `cirq.Z`.
    2. Strings: "I", "X", "Y", "Z". Equivalently "i", "x", "y", "z".
    3. Integers from 0 to 3, with the convention 0=I, 1=X, 2=Y, 3=Z.
    """,
)


@value.value_equality(approximate=True, manual_cls=True)
class PauliString(raw_types.Operation, Generic[TKey]):
    def __init__(
        self,
        *contents: 'cirq.PAULI_STRING_LIKE',
        qubit_pauli_map: Optional[Dict[TKey, 'cirq.Pauli']] = None,
        coefficient: Union[int, float, complex] = 1,
    ):
        """Initializes a new PauliString.

        Args:
            *contents: A value or values to convert into a pauli string. This
                can be a number, a pauli operation, a dictionary from qubit to
                pauli/identity gates, or collections thereof. If a list of
                values is given, they are each individually converted and then
                multiplied from left to right in order.
            qubit_pauli_map: Initial dictionary mapping qubits to pauli
                operations. Defaults to the empty dictionary. Note that, unlike
                dictionaries passed to contents, this dictionary must not
                contain any identity gate values. Further note that this
                argument specifies values that are logically *before* factors
                specified in `contents`; `contents` are *right* multiplied onto
                the values in this dictionary.
            coefficient: Initial scalar coefficient. Defaults to 1.

        Examples:
            >>> a, b, c = cirq.LineQubit.range(3)

            >>> print(cirq.PauliString([cirq.X(a), cirq.X(a)]))
            I

            >>> print(cirq.PauliString(-1, cirq.X(a), cirq.Y(b), cirq.Z(c)))
            -X(0)*Y(1)*Z(2)

            >>> print(cirq.PauliString({a: cirq.X}, [-2, 3, cirq.Y(a)]))
            -6j*Z(0)

            >>> print(cirq.PauliString({a: cirq.I, b: cirq.X}))
            X(1)

            >>> print(cirq.PauliString({a: cirq.Y},
            ...                        qubit_pauli_map={a: cirq.X}))
            1j*Z(0)
        """
        if qubit_pauli_map is not None:
            for v in qubit_pauli_map.values():
                if not isinstance(v, pauli_gates.Pauli):
                    raise TypeError(f'{v} is not a Pauli')

        self._qubit_pauli_map: Dict[TKey, 'cirq.Pauli'] = qubit_pauli_map or {}
        self._coefficient = complex(coefficient)
        if contents:
            m = self.mutable_copy().inplace_left_multiply_by(contents).frozen()
            self._qubit_pauli_map = m._qubit_pauli_map
            self._coefficient = m._coefficient

    @property
    def coefficient(self) -> complex:
        return self._coefficient

    def _value_equality_values_(self):
        if len(self._qubit_pauli_map) == 1 and self.coefficient == 1:
            q, p = list(self._qubit_pauli_map.items())[0]
            return gate_operation.GateOperation(p, [q])._value_equality_values_()

        return (frozenset(self._qubit_pauli_map.items()), self._coefficient)

    def _json_dict_(self) -> Dict[str, Any]:
        return {
            'cirq_type': self.__class__.__name__,
            # JSON requires mappings to have string keys.
            'qubit_pauli_map': list(self._qubit_pauli_map.items()),
            'coefficient': self.coefficient,
        }

    @classmethod
    def _from_json_dict_(cls, qubit_pauli_map, coefficient, **kwargs):
        return cls(qubit_pauli_map=dict(qubit_pauli_map), coefficient=coefficient)

    def _value_equality_values_cls_(self):
        if len(self._qubit_pauli_map) == 1 and self.coefficient == 1:
            return gate_operation.GateOperation
        return PauliString

    def equal_up_to_coefficient(self, other: 'cirq.PauliString') -> bool:
        return self._qubit_pauli_map == other._qubit_pauli_map

    def __getitem__(self, key: TKey) -> pauli_gates.Pauli:
        return self._qubit_pauli_map[key]

    # pylint: disable=function-redefined
    @overload
    def get(self, key: Any, default: None = None) -> pauli_gates.Pauli:
        pass

    @overload
    def get(self, key: Any, default: TDefault) -> Union[pauli_gates.Pauli, TDefault]:
        pass

    def get(self, key: Any, default=None):
        return self._qubit_pauli_map.get(key, default)

    @overload
    def __mul__(  # type: ignore
        self, other: 'cirq.PauliString[TKeyOther]'
    ) -> 'cirq.PauliString[Union[TKey, TKeyOther]]':
        pass

    @overload
    def __mul__(
        self, other: Mapping[TKeyOther, 'cirq.PAULI_GATE_LIKE']
    ) -> 'cirq.PauliString[Union[TKey, TKeyOther]]':
        pass

    @overload
    def __mul__(
        self, other: Iterable['cirq.PAULI_STRING_LIKE']
    ) -> 'cirq.PauliString[Union[TKey, cirq.Qid]]':
        pass

    @overload
    def __mul__(self, other: 'cirq.Operation') -> 'cirq.PauliString[Union[TKey, cirq.Qid]]':
        pass

    @overload
    def __mul__(
        self, other: Union[complex, int, float, numbers.Number]
    ) -> 'cirq.PauliString[TKey]':
        pass

    def __mul__(self, other):
        known = False
        if isinstance(other, raw_types.Operation) and isinstance(other.gate, identity.IdentityGate):
            known = True
        elif isinstance(other, (PauliString, numbers.Number)):
            known = True
        if known:
            return PauliString(
                cast(PAULI_STRING_LIKE, other),
                qubit_pauli_map=self._qubit_pauli_map,
                coefficient=self.coefficient,
            )
        return NotImplemented

    # pylint: enable=function-redefined

    @property
    def gate(self) -> 'cirq.DensePauliString':
        order: List[Optional[pauli_gates.Pauli]] = [
            None,
            pauli_gates.X,
            pauli_gates.Y,
            pauli_gates.Z,
        ]
        from cirq.ops.dense_pauli_string import DensePauliString

        return DensePauliString(
            coefficient=self.coefficient, pauli_mask=[order.index(self[q]) for q in self.qubits]
        )

    def __rmul__(self, other) -> 'PauliString':
        if isinstance(other, numbers.Number):
            return PauliString(
                qubit_pauli_map=self._qubit_pauli_map,
                coefficient=self._coefficient * complex(cast(SupportsComplex, other)),
            )

        if isinstance(other, raw_types.Operation) and isinstance(other.gate, identity.IdentityGate):
            return self

        # Note: PauliString case handled by __mul__.
        return NotImplemented

    def __truediv__(self, other):
        if isinstance(other, numbers.Number):
            return PauliString(
                qubit_pauli_map=self._qubit_pauli_map,
                coefficient=self._coefficient / complex(cast(SupportsComplex, other)),
            )
        return NotImplemented

    def __add__(self, other):
        from cirq.ops.linear_combinations import PauliSum

        return PauliSum.from_pauli_strings(self).__add__(other)

    def __radd__(self, other):
        return self.__add__(other)

    def __sub__(self, other):
        from cirq.ops.linear_combinations import PauliSum

        return PauliSum.from_pauli_strings(self).__sub__(other)

    def __rsub__(self, other):
        return -self.__sub__(other)

    def __contains__(self, key: TKey) -> bool:
        return key in self._qubit_pauli_map

    def _decompose_(self):
        if not self._has_unitary_():
            return None
        return [
            *(
                []
                if self.coefficient == 1
                else [global_phase_op.GlobalPhaseOperation(self.coefficient)]
            ),
            *[self[q].on(q) for q in self.qubits],
        ]

    def keys(self) -> KeysView[TKey]:
        return self._qubit_pauli_map.keys()

    @property
    def qubits(self) -> Tuple[TKey, ...]:
        return tuple(sorted(self.keys()))

    def _circuit_diagram_info_(self, args: 'cirq.CircuitDiagramInfoArgs') -> List[str]:
        if not len(self._qubit_pauli_map):
            return NotImplemented

        qs = args.known_qubits or list(self.keys())
        symbols = list(str(self.get(q)) for q in qs)
        if self.coefficient == 1:
            prefix = '+'
        elif self.coefficient == -1:
            prefix = '-'
        elif self.coefficient == 1j:
            prefix = 'i'
        elif self.coefficient == -1j:
            prefix = '-i'
        else:
            prefix = f'({args.format_complex(self.coefficient)})*'
        symbols[0] = f'PauliString({prefix}{symbols[0]})'
        return symbols

    def with_qubits(self, *new_qubits: 'cirq.Qid') -> 'PauliString':
        return PauliString(
            qubit_pauli_map=dict(zip(new_qubits, (self[q] for q in self.qubits))),
            coefficient=self._coefficient,
        )

    def with_coefficient(self, new_coefficient: Union[int, float, complex]) -> 'PauliString':
        return PauliString(qubit_pauli_map=dict(self._qubit_pauli_map), coefficient=new_coefficient)

    def values(self) -> ValuesView[pauli_gates.Pauli]:
        return self._qubit_pauli_map.values()

    def items(self) -> ItemsView[TKey, pauli_gates.Pauli]:
        return self._qubit_pauli_map.items()

    def frozen(self) -> 'cirq.PauliString':
        """Returns a cirq.PauliString with the same contents."""
        return self

    def mutable_copy(self) -> 'cirq.MutablePauliString':
        """Returns a new cirq.MutablePauliString with the same contents."""
        return MutablePauliString(
            coefficient=self.coefficient,
            pauli_int_dict={
                q: PAULI_GATE_LIKE_TO_INDEX_MAP[p] for q, p in self._qubit_pauli_map.items()
            },
        )

    def __iter__(self) -> Iterator[TKey]:
        return iter(self._qubit_pauli_map.keys())

    def __bool__(self):
        return bool(self._qubit_pauli_map)

    def __len__(self) -> int:
        return len(self._qubit_pauli_map)

    def _repr_pretty_(self, p: Any, cycle: bool) -> None:
        """Print ASCII diagram in Jupyter."""
        if cycle:
            # There should never be a cycle.  This is just in case.
            p.text('cirq.PauliString(...)')
        else:
            p.text(str(self))

    def __repr__(self) -> str:
        ordered_qubits = sorted(self.qubits)
        prefix = ''

        factors = []
        if self._coefficient == -1:
            prefix = '-'
        elif self._coefficient != 1:
            factors.append(repr(self._coefficient))

        if not ordered_qubits:
            factors.append('cirq.PauliString()')
        for q in ordered_qubits:
            factors.append(repr(cast(raw_types.Gate, self[q]).on(q)))

        fused = prefix + '*'.join(factors)
        if len(factors) > 1:
            return f'({fused})'
        return fused

    def __str__(self) -> str:
        ordered_qubits = sorted(self.qubits)
        prefix = ''

        factors = []
        if self._coefficient == -1:
            prefix = '-'
        elif self._coefficient != 1:
            factors.append(repr(self._coefficient))

        if not ordered_qubits:
            factors.append('I')
        for q in ordered_qubits:
            factors.append(str(cast(raw_types.Gate, self[q]).on(q)))

        return prefix + '*'.join(factors)

    def matrix(self, qubits: Optional[Iterable[TKey]] = None) -> np.ndarray:
        """Returns the matrix of self in computational basis of qubits.

        Args:
            qubits: Ordered collection of qubits that determine the subspace
                in which the matrix representation of the Pauli string is to
                be computed. Qubits absent from self.qubits are acted on by
                the identity. Defaults to self.qubits.
        """
        qubits = self.qubits if qubits is None else qubits
        factors = [self.get(q, default=identity.I) for q in qubits]
        return linalg.kron(self.coefficient, *[protocols.unitary(f) for f in factors])

    def _has_unitary_(self) -> bool:
        return abs(1 - abs(self.coefficient)) < 1e-6

    def _unitary_(self) -> Optional[np.ndarray]:
        if not self._has_unitary_():
            return None
        return self.matrix()

    def _apply_unitary_(self, args: 'protocols.ApplyUnitaryArgs'):
        if not self._has_unitary_():
            return None
        if self.coefficient != 1:
            args.target_tensor *= self.coefficient
        return protocols.apply_unitaries([self[q].on(q) for q in self.qubits], self.qubits, args)

    def expectation_from_state_vector(
        self,
        state_vector: np.ndarray,
        qubit_map: Mapping[TKey, int],
        *,
        atol: float = 1e-7,
        check_preconditions: bool = True,
    ) -> float:
        r"""Evaluate the expectation of this PauliString given a state vector.

        Compute the expectation value of this PauliString with respect to a
        state vector. By convention expectation values are defined for Hermitian
        operators, and so this method will fail if this PauliString is
        non-Hermitian.

        `state` must be an array representation of a state vector and have
        shape `(2 ** n, )` or `(2, 2, ..., 2)` (n entries) where `state` is
        expressed over n qubits.

        `qubit_map` must assign an integer index to each qubit in this
        PauliString that determines which bit position of a computational basis
        state that qubit corresponds to. For example if `state` represents
        $|0\rangle |+\rangle$ and `q0, q1 = cirq.LineQubit.range(2)` then:

            cirq.X(q0).expectation(state, qubit_map={q0: 0, q1: 1}) = 0
            cirq.X(q0).expectation(state, qubit_map={q0: 1, q1: 0}) = 1

        Args:
            state_vector: An array representing a valid state vector.
            qubit_map: A map from all qubits used in this PauliString to the
                indices of the qubits that `state_vector` is defined over.
            atol: Absolute numerical tolerance.
            check_preconditions: Whether to check that `state_vector` represents
                a valid state vector.

        Returns:
            The expectation value of the input state.

        Raises:
            NotImplementedError if this PauliString is non-Hermitian.
        """
        if abs(self.coefficient.imag) > 0.0001:
            raise NotImplementedError(
                'Cannot compute expectation value of a non-Hermitian '
                f'PauliString <{self}>. Coefficient must be real.'
            )

        # FIXME: Avoid enforce specific complex type. This is necessary to
        # prevent an `apply_unitary` bug (Issue #2041).
        if state_vector.dtype.kind != 'c':
            raise TypeError("Input state dtype must be np.complex64 or np.complex128")

        size = state_vector.size
        num_qubits = size.bit_length() - 1
        if len(state_vector.shape) != 1 and state_vector.shape != (2,) * num_qubits:
            raise ValueError(
                "Input array does not represent a state vector "
                "with shape `(2 ** n,)` or `(2, ..., 2)`."
            )

        _validate_qubit_mapping(qubit_map, self.qubits, num_qubits)
        if check_preconditions:
            qis.validate_normalized_state_vector(
                state_vector=state_vector,
                qid_shape=(2,) * num_qubits,
                dtype=state_vector.dtype,
                atol=atol,
            )
        return self._expectation_from_state_vector_no_validation(state_vector, qubit_map)

    def _expectation_from_state_vector_no_validation(
        self, state_vector: np.ndarray, qubit_map: Mapping[TKey, int]
    ) -> float:
        """Evaluate the expectation of this PauliString given a state vector.

        This method does not provide input validation. See
        `PauliString.expectation_from_state_vector` for function description.

        Args:
            state_vector: An array representing a valid state vector.
            qubit_map: A map from all qubits used in this PauliString to the
            indices of the qubits that `state` is defined over.

        Returns:
            The expectation value of the input state.
        """
        if len(state_vector.shape) == 1:
            num_qubits = state_vector.shape[0].bit_length() - 1
            state_vector = np.reshape(state_vector, (2,) * num_qubits)

        ket = np.copy(state_vector)
        for qubit, pauli in self.items():
            buffer = np.empty(ket.shape, dtype=state_vector.dtype)
            args = protocols.ApplyUnitaryArgs(
                target_tensor=ket, available_buffer=buffer, axes=(qubit_map[qubit],)
            )
            ket = protocols.apply_unitary(pauli, args)

        return self.coefficient * (
            np.tensordot(state_vector.conj(), ket, axes=len(ket.shape)).item()
        )

    def expectation_from_density_matrix(
        self,
        state: np.ndarray,
        qubit_map: Mapping[TKey, int],
        *,
        atol: float = 1e-7,
        check_preconditions: bool = True,
    ) -> float:
        r"""Evaluate the expectation of this PauliString given a density matrix.

        Compute the expectation value of this PauliString with respect to an
        array representing a density matrix. By convention expectation values
        are defined for Hermitian operators, and so this method will fail if
        this PauliString is non-Hermitian.

        `state` must be an array representation of a density matrix and have
        shape `(2 ** n, 2 ** n)` or `(2, 2, ..., 2)` (2*n entries), where
        `state` is expressed over n qubits.

        `qubit_map` must assign an integer index to each qubit in this
        PauliString that determines which bit position of a computational basis
        state that qubit corresponds to. For example if `state` represents
        $|0\rangle |+\rangle$ and `q0, q1 = cirq.LineQubit.range(2)` then:

            cirq.X(q0).expectation(state, qubit_map={q0: 0, q1: 1}) = 0
            cirq.X(q0).expectation(state, qubit_map={q0: 1, q1: 0}) = 1

        Args:
            state: An array representing a valid  density matrix.
            qubit_map: A map from all qubits used in this PauliString to the
                indices of the qubits that `state` is defined over.
            atol: Absolute numerical tolerance.
            check_preconditions: Whether to check that `state` represents a
                valid density matrix.

        Returns:
            The expectation value of the input state.

        Raises:
            NotImplementedError if this PauliString is non-Hermitian.
        """
        if abs(self.coefficient.imag) > 0.0001:
            raise NotImplementedError(
                'Cannot compute expectation value of a non-Hermitian '
                f'PauliString <{self}>. Coefficient must be real.'
            )

        # FIXME: Avoid enforcing specific complex type. This is necessary to
        # prevent an `apply_unitary` bug (Issue #2041).
        if state.dtype.kind != 'c':
            raise TypeError("Input state dtype must be np.complex64 or np.complex128")

        size = state.size
        num_qubits = int(np.sqrt(size)).bit_length() - 1
        dim = 1 << num_qubits
        if state.shape != (dim, dim) and state.shape != (2, 2) * num_qubits:
            raise ValueError(
                "Input array does not represent a density matrix "
                "with shape `(2 ** n, 2 ** n)` or `(2, ..., 2)`."
            )

        _validate_qubit_mapping(qubit_map, self.qubits, num_qubits)
        if check_preconditions:
            # Do not enforce reshaping if the state all axes are dimension 2.
            _ = qis.to_valid_density_matrix(
                density_matrix_rep=state.reshape(dim, dim),
                num_qubits=num_qubits,
                dtype=state.dtype,
                atol=atol,
            )
        return self._expectation_from_density_matrix_no_validation(state, qubit_map)

    def _expectation_from_density_matrix_no_validation(
        self, state: np.ndarray, qubit_map: Mapping[TKey, int]
    ) -> float:
        """Evaluate the expectation of this PauliString given a density matrix.

        This method does not provide input validation. See
        `PauliString.expectation_from_density_matrix` for function description.

        Args:
            state: An array representing a valid  density matrix.
            qubit_map: A map from all qubits used in this PauliString to the
            indices of the qubits that `state` is defined over.

        Returns:
            The expectation value of the input state.
        """
        result = np.copy(state)
        if len(state.shape) == 2:
            num_qubits = state.shape[0].bit_length() - 1
            result = np.reshape(result, (2,) * num_qubits * 2)

        for qubit, pauli in self.items():
            buffer = np.empty(result.shape, dtype=state.dtype)
            args = protocols.ApplyUnitaryArgs(
                target_tensor=result, available_buffer=buffer, axes=(qubit_map[qubit],)
            )
            result = protocols.apply_unitary(pauli, args)

        while any(result.shape):
            result = np.trace(result, axis1=0, axis2=len(result.shape) // 2)
        return result * self.coefficient

    def zip_items(
        self, other: 'cirq.PauliString[TKey]'
    ) -> Iterator[Tuple[TKey, Tuple[pauli_gates.Pauli, pauli_gates.Pauli]]]:
        for qubit, pauli0 in self.items():
            if qubit in other:
                yield qubit, (pauli0, other[qubit])

    def zip_paulis(
        self, other: 'cirq.PauliString'
    ) -> Iterator[Tuple[pauli_gates.Pauli, pauli_gates.Pauli]]:
        return (paulis for qubit, paulis in self.zip_items(other))

    def _commutes_(
        self, other: Any, *, atol: Union[int, float] = 1e-8
    ) -> Union[bool, NotImplementedType, None]:
        if not isinstance(other, PauliString):
            return NotImplemented
        return sum(not protocols.commutes(p0, p1) for p0, p1 in self.zip_paulis(other)) % 2 == 0

    def __neg__(self) -> 'PauliString':
        return PauliString(qubit_pauli_map=self._qubit_pauli_map, coefficient=-self._coefficient)

    def __pos__(self) -> 'PauliString':
        return self

    def __array_ufunc__(self, ufunc, method, *inputs, **kwargs):
        """Override behavior of numpy's exp method."""
        if ufunc == np.exp and len(inputs) == 1 and inputs[0] is self:
            return math.e ** self
        return NotImplemented

    def __pow__(self, power):
        if power == 1:
            return self
        if power == -1:
            return PauliString(
                qubit_pauli_map=self._qubit_pauli_map, coefficient=self.coefficient ** -1
            )
        if isinstance(power, (int, float)):
            r, i = cmath.polar(self.coefficient)
            if abs(r - 1) > 0.0001:
                # Raising non-unitary PauliStrings to a power is not supported.
                return NotImplemented

            if len(self) == 1:
                q, p = next(iter(self.items()))
                gates = {
                    pauli_gates.X: common_gates.XPowGate,
                    pauli_gates.Y: common_gates.YPowGate,
                    pauli_gates.Z: common_gates.ZPowGate,
                }
                return gates[p](exponent=power).on(q)

            global_half_turns = power * (i / math.pi)

            # HACK: Avoid circular dependency.
            from cirq.ops import pauli_string_phasor

            return pauli_string_phasor.PauliStringPhasor(
                PauliString(qubit_pauli_map=self._qubit_pauli_map),
                exponent_neg=global_half_turns + power,
                exponent_pos=global_half_turns,
            )
        return NotImplemented

    def __rpow__(self, base):
        if isinstance(base, (int, float)) and base > 0:
            if abs(self.coefficient.real) > 0.0001:
                raise NotImplementedError(
                    'Exponentiated to a non-Hermitian PauliString '
                    f'<{base}**{self}>. Coefficient must be imaginary.'
                )

            half_turns = 2 * math.log(base) * (-self.coefficient.imag / math.pi)

            if len(self) == 1:
                q, p = next(iter(self.items()))
                gates = {
                    pauli_gates.X: common_gates.XPowGate,
                    pauli_gates.Y: common_gates.YPowGate,
                    pauli_gates.Z: common_gates.ZPowGate,
                }
                return gates[p](exponent=half_turns, global_shift=-0.5).on(q)

            # HACK: Avoid circular dependency.
            from cirq.ops import pauli_string_phasor

            return pauli_string_phasor.PauliStringPhasor(
                PauliString(qubit_pauli_map=self._qubit_pauli_map),
                exponent_neg=+half_turns / 2,
                exponent_pos=-half_turns / 2,
            )
        return NotImplemented

    def map_qubits(self, qubit_map: Dict[TKey, TKeyNew]) -> 'cirq.PauliString[TKeyNew]':
        new_qubit_pauli_map = {qubit_map[qubit]: pauli for qubit, pauli in self.items()}
        return PauliString(qubit_pauli_map=new_qubit_pauli_map, coefficient=self._coefficient)

    def to_z_basis_ops(self) -> Iterator[raw_types.Operation]:
        """Returns operations to convert the qubits to the computational basis."""
        for qubit, pauli in self.items():
            yield clifford_gate.SingleQubitCliffordGate.from_single_map(
                {pauli: (pauli_gates.Z, False)}
            )(qubit)

    def dense(self, qubits: Sequence[TKey]) -> 'cirq.DensePauliString':
        """Returns a `cirq.DensePauliString` version of this Pauli string.

        This method satisfies the invariant `P.dense(qubits).on(*qubits) == P`.

        Args:
            qubits: The implicit sequence of qubits used by the dense pauli
                string. Specifically, if the returned dense Pauli string was
                applied to these qubits (via its `on` method) then the result
                would be a Pauli string equivalent to the receiving Pauli
                string.

        Returns:
            A `cirq.DensePauliString` instance `D` such that `D.on(*qubits)`
            equals the receiving `cirq.PauliString` instance `P`.
        """
        from cirq.ops.dense_pauli_string import DensePauliString

        if not self.keys() <= set(qubits):
            raise ValueError('not self.keys() <= set(qubits)')
        # pylint: disable=too-many-function-args
        pauli_mask = [self.get(q, identity.I) for q in qubits]
        # pylint: enable=too-many-function-args
        return DensePauliString(pauli_mask, coefficient=self.coefficient)

    def conjugated_by(self, clifford: 'cirq.OP_TREE') -> 'PauliString':
        r"""Returns the Pauli string conjugated by a clifford operation.

        The product-of-Paulis $P$ conjugated by the Clifford operation $C$ is

            $$
            C^\dagger P C
            $$

        For example, conjugating a +Y operation by an S operation results in a
        +X operation (as opposed to a -X operation).

        In a circuit diagram where `P` is a pauli string observable immediately
        after a Clifford operation `C`, the pauli string `P.conjugated_by(C)` is
        the equivalent pauli string observable just before `C`.

            --------------------------C---P---

            = ---C---P------------------------

            = ---C---P---------C^-1---C-------

            = ---C---P---C^-1---------C-------

            = --(C^-1 · P · C)--------C-------

            = ---P.conjugated_by(C)---C-------

        Analogously, a Pauli product P can be moved from before a Clifford C in
        a circuit diagram to after the Clifford C by conjugating P by the
        inverse of C:

            ---P---C---------------------------

            = -----C---P.conjugated_by(C^-1)---

        Args:
            clifford: The Clifford operation to conjugate by. This can be an
                individual operation, or a tree of operations.

                Note that the composite Clifford operation defined by a sequence
                of operations is equivalent to a circuit containing those
                operations in the given order. Somewhat counter-intuitively,
                this means that the operations in the sequence are conjugated
                onto the Pauli string in reverse order. For example,
                `P.conjugated_by([C1, C2])` is equivalent to
                `P.conjugated_by(C2).conjugated_by(C1)`.

        Examples:
            >>> a, b = cirq.LineQubit.range(2)
            >>> print(cirq.X(a).conjugated_by(cirq.CZ(a, b)))
            X(0)*Z(1)
            >>> print(cirq.X(a).conjugated_by(cirq.S(a)))
            -Y(0)
            >>> print(cirq.X(a).conjugated_by([cirq.H(a), cirq.CNOT(a, b)]))
            Z(0)*X(1)

        Returns:
            The Pauli string conjugated by the given Clifford operation.
        """
        pauli_map = dict(self._qubit_pauli_map)
        should_negate = False
        for op in list(op_tree.flatten_to_ops(clifford))[::-1]:
            if pauli_map.keys().isdisjoint(set(op.qubits)):
                continue
            for clifford_op in _decompose_into_cliffords(op)[::-1]:
                if pauli_map.keys().isdisjoint(set(clifford_op.qubits)):
                    continue
                should_negate ^= PauliString._pass_operation_over(pauli_map, clifford_op, False)
        coef = -self._coefficient if should_negate else self.coefficient
        return PauliString(qubit_pauli_map=pauli_map, coefficient=coef)

    def after(self, ops: 'cirq.OP_TREE') -> 'cirq.PauliString':
        r"""Determines the equivalent pauli string after some operations.

        If the PauliString is $P$ and the Clifford operation is $C$, then the
        result is $C P C^\dagger$.

        Args:
            ops: A stabilizer operation or nested collection of stabilizer
                operations.

        Returns:
            The result of propagating this pauli string from before to after the
            given operations.
        """
        return self.conjugated_by(protocols.inverse(ops))

    def before(self, ops: 'cirq.OP_TREE') -> 'cirq.PauliString':
        r"""Determines the equivalent pauli string before some operations.

        If the PauliString is $P$ and the Clifford operation is $C$, then the
        result is $C^\dagger P C$.

        Args:
            ops: A stabilizer operation or nested collection of stabilizer
                operations.

        Returns:
            The result of propagating this pauli string from after to before the
            given operations.
        """
        return self.conjugated_by(ops)

    def pass_operations_over(
        self, ops: Iterable['cirq.Operation'], after_to_before: bool = False
    ) -> 'PauliString':
        """Determines how the Pauli string changes when conjugated by Cliffords.

        The output and input pauli strings are related by a circuit equivalence.
        In particular, this circuit:

            ───ops───INPUT_PAULI_STRING───

        will be equivalent to this circuit:

            ───OUTPUT_PAULI_STRING───ops───

        up to global phase (assuming `after_to_before` is not set).

        If ops together have matrix C, the Pauli string has matrix P, and the
        output Pauli string has matrix P', then P' == C^-1 P C up to
        global phase.

        Setting `after_to_before` inverts the relationship, so that the output
        is the input and the input is the output. Equivalently, it inverts C.

        Args:
            ops: The operations to move over the string.
            after_to_before: Determines whether the operations start after the
                pauli string, instead of before (and so are moving in the
                opposite direction).
        """
        pauli_map = dict(self._qubit_pauli_map)
        should_negate = False
        for op in ops:
            if pauli_map.keys().isdisjoint(set(op.qubits)):
                continue
            decomposed = _decompose_into_cliffords(op)
            if not after_to_before:
                decomposed = decomposed[::-1]
            for clifford_op in decomposed:
                if pauli_map.keys().isdisjoint(set(clifford_op.qubits)):
                    continue
                should_negate ^= PauliString._pass_operation_over(
                    pauli_map, clifford_op, after_to_before
                )
        coef = -self._coefficient if should_negate else self.coefficient
        return PauliString(qubit_pauli_map=pauli_map, coefficient=coef)

    @staticmethod
    def _pass_operation_over(
        pauli_map: Dict[TKey, pauli_gates.Pauli],
        op: 'cirq.Operation',
        after_to_before: bool = False,
    ) -> bool:
        if isinstance(op, gate_operation.GateOperation):
            gate = op.gate
            if isinstance(gate, clifford_gate.SingleQubitCliffordGate):
                return PauliString._pass_single_clifford_gate_over(
                    pauli_map, gate, cast(TKey, op.qubits[0]), after_to_before=after_to_before
                )
            if isinstance(gate, pauli_interaction_gate.PauliInteractionGate):
                return PauliString._pass_pauli_interaction_gate_over(
                    pauli_map,
                    gate,
                    cast(TKey, op.qubits[0]),
                    cast(TKey, op.qubits[1]),
                    after_to_before=after_to_before,
                )
        raise NotImplementedError(f'Unsupported operation: {op!r}')

    @staticmethod
    def _pass_single_clifford_gate_over(
        pauli_map: Dict[TKey, pauli_gates.Pauli],
        gate: clifford_gate.SingleQubitCliffordGate,
        qubit: TKey,
        after_to_before: bool = False,
    ) -> bool:
        if qubit not in pauli_map:
            return False
        if not after_to_before:
            gate **= -1
        pauli, inv = gate.transform(pauli_map[qubit])
        pauli_map[qubit] = pauli
        return inv

    @staticmethod
    def _pass_pauli_interaction_gate_over(
        pauli_map: Dict[TKey, pauli_gates.Pauli],
        gate: pauli_interaction_gate.PauliInteractionGate,
        qubit0: TKey,
        qubit1: TKey,
        after_to_before: bool = False,
    ) -> bool:
        def merge_and_kickback(
            qubit: TKey,
            pauli_left: Optional[pauli_gates.Pauli],
            pauli_right: Optional[pauli_gates.Pauli],
            inv: bool,
        ) -> int:
            assert pauli_left is not None or pauli_right is not None
            if pauli_left is None or pauli_right is None:
                pauli_map[qubit] = cast(pauli_gates.Pauli, pauli_left or pauli_right)
                return 0
            if pauli_left == pauli_right:
                del pauli_map[qubit]
                return 0

            pauli_map[qubit] = pauli_left.third(pauli_right)
            if (pauli_left < pauli_right) ^ after_to_before:
                return int(inv) * 2 + 1

            return int(inv) * 2 - 1

        quarter_kickback = 0
        if qubit0 in pauli_map and not protocols.commutes(pauli_map[qubit0], gate.pauli0):
            quarter_kickback += merge_and_kickback(
                qubit1, gate.pauli1, pauli_map.get(qubit1), gate.invert1
            )
        if qubit1 in pauli_map and not protocols.commutes(pauli_map[qubit1], gate.pauli1):
            quarter_kickback += merge_and_kickback(
                qubit0, pauli_map.get(qubit0), gate.pauli0, gate.invert0
            )
        assert (
            quarter_kickback % 2 == 0
        ), 'Impossible condition.  quarter_kickback is either incremented twice or never.'
        return quarter_kickback % 4 == 2


def _validate_qubit_mapping(
    qubit_map: Mapping[TKey, int], pauli_qubits: Tuple[TKey, ...], num_state_qubits: int
) -> None:
    """Validates that a qubit map is a valid mapping.

    This will enforce that all elements of `pauli_qubits` appear in `qubit_map`,
    and that the integers in `qubit_map` correspond to valid positions in a
    representation of a state over `num_state_qubits`.

    Args:
        qubit_map: A map from qubits to integers.
        pauli_qubits: The qubits that must be contained in `qubit_map`.
        num_state_qubits: The number of qubits over which a state is expressed.
    """
    if not isinstance(qubit_map, Mapping) or not all(
        isinstance(k, raw_types.Qid) and isinstance(v, int) for k, v in qubit_map.items()
    ):
        raise TypeError(
            "Input qubit map must be a valid mapping from Qubit ID's to integer indices."
        )

    if not set(qubit_map.keys()) >= set(pauli_qubits):
        raise ValueError(
            "Input qubit map must be a complete mapping over all of this PauliString's qubits."
        )

    used_inds = [qubit_map[q] for q in pauli_qubits]
    if len(used_inds) != len(set(used_inds)) or not set(range(num_state_qubits)) >= set(
        sorted(used_inds)
    ):
        raise ValueError(
            f'Input qubit map indices must be valid for a state over {num_state_qubits} qubits.'
        )


# Ignoring type because mypy believes `with_qubits` methods are incompatible.
class SingleQubitPauliStringGateOperation(  # type: ignore
    gate_operation.GateOperation, PauliString
):
    """A Pauli operation applied to a qubit.

    Satisfies the contract of both GateOperation and PauliString. Relies
    implicitly on the fact that PauliString({q: X}) compares as equal to
    GateOperation(X, [q]).
    """

    def __init__(self, pauli: pauli_gates.Pauli, qubit: 'cirq.Qid'):
        PauliString.__init__(self, qubit_pauli_map={qubit: pauli})
        gate_operation.GateOperation.__init__(self, cast(raw_types.Gate, pauli), [qubit])

    def with_qubits(self, *new_qubits: 'cirq.Qid') -> 'SingleQubitPauliStringGateOperation':
        if len(new_qubits) != 1:
            raise ValueError("len(new_qubits) != 1")
        return SingleQubitPauliStringGateOperation(
            cast(pauli_gates.Pauli, self.gate), new_qubits[0]
        )

    @property
    def pauli(self) -> pauli_gates.Pauli:
        return cast(pauli_gates.Pauli, self.gate)

    @property
    def qubit(self) -> raw_types.Qid:
        assert len(self.qubits) == 1
        return self.qubits[0]

    def _as_pauli_string(self) -> PauliString:
        return PauliString(qubit_pauli_map={self.qubit: self.pauli})

    def __mul__(self, other):
        if isinstance(other, SingleQubitPauliStringGateOperation):
            return self._as_pauli_string() * other._as_pauli_string()
        if isinstance(other, (PauliString, complex, float, int)):
            return self._as_pauli_string() * other
        return NotImplemented

    def __rmul__(self, other):
        if isinstance(other, (PauliString, complex, float, int)):
            return other * self._as_pauli_string()
        return NotImplemented

    def __neg__(self):
        return -self._as_pauli_string()

    def _json_dict_(self) -> Dict[str, Any]:
        return protocols.obj_to_dict_helper(self, ['pauli', 'qubit'])

    @classmethod
    def _from_json_dict_(  # type: ignore
        cls, pauli: pauli_gates.Pauli, qubit: 'cirq.Qid', **kwargs
    ):
        # Note, this method is required or else superclasses' deserialization
        # would be used
        return cls(pauli=pauli, qubit=qubit)


@value.value_equality(unhashable=True, manual_cls=True, approximate=True)
class MutablePauliString(Generic[TKey]):
    def __init__(
        self,
        *contents: 'cirq.PAULI_STRING_LIKE',
        coefficient: Union[int, float, complex] = 1,
        pauli_int_dict: Optional[Dict[TKey, int]] = None,
    ):
        self.coefficient = complex(coefficient)
        self.pauli_int_dict: Dict[TKey, int] = {} if pauli_int_dict is None else pauli_int_dict
        if contents:
            self.inplace_left_multiply_by(contents)

    def _value_equality_values_(self):
        return self.frozen()._value_equality_values_()

    def _value_equality_values_cls_(self):
        return self.frozen()._value_equality_values_cls_()

    def _imul_atom_helper(self, key: TKey, pauli_lhs: int, sign: int) -> int:
        pauli_old = self.pauli_int_dict.pop(key, 0)
        pauli_new = pauli_lhs ^ pauli_old
        if pauli_new:
            self.pauli_int_dict[key] = pauli_new
        if not pauli_lhs or not pauli_old or pauli_lhs == pauli_old:
            return 0
        if (pauli_old - pauli_lhs) % 3 == 1:
            return sign
        return -sign

    def keys(self) -> AbstractSet[TKey]:
        return self.pauli_int_dict.keys()

    def values(self) -> Iterator[Union['cirq.Pauli', 'cirq.IdentityGate']]:
        for v in self.pauli_int_dict.values():
            yield _INT_TO_PAULI[v]

    def __iter__(self) -> Iterator[TKey]:
        return iter(self.pauli_int_dict)

    def __len__(self) -> int:
        return len(self.pauli_int_dict)

    def __bool__(self) -> bool:
        return bool(self.pauli_int_dict)

    def frozen(self) -> 'cirq.PauliString':
        """Returns a cirq.PauliString with the same contents.

        For example, this is useful because cirq.PauliString is an operation
        whereas cirq.MutablePauliString is not.
        """
        return PauliString(
            coefficient=self.coefficient,
            qubit_pauli_map={
                q: cast(pauli_gates.Pauli, _INT_TO_PAULI[p])
                for q, p in self.pauli_int_dict.items()
                if p
            },
        )

    def mutable_copy(self) -> 'cirq.MutablePauliString':
        """Returns a new cirq.MutablePauliString with the same contents."""
        return MutablePauliString(
            coefficient=self.coefficient,
            pauli_int_dict=dict(self.pauli_int_dict),
        )

    def items(self) -> Iterator[Tuple[TKey, Union['cirq.Pauli', 'cirq.IdentityGate']]]:
        for k, v in self.pauli_int_dict.items():
            yield k, _INT_TO_PAULI[v]

    def __contains__(self, item: Any) -> bool:
        return item in self.pauli_int_dict

    def __getitem__(self, item: Any) -> Union['cirq.Pauli', 'cirq.IdentityGate']:
        return _INT_TO_PAULI[self.pauli_int_dict[item]]

    def __setitem__(self, key: TKey, value: 'cirq.PAULI_GATE_LIKE'):
        value = _pauli_like_to_pauli_int(key, value)
        if value:
            self.pauli_int_dict[key] = _pauli_like_to_pauli_int(key, value)
        else:
            self.pauli_int_dict.pop(key, None)

    def __delitem__(self, key: TKey):
        del self.pauli_int_dict[key]

    # pylint: disable=function-redefined
    @overload
    def get(
        self, key: TKey, default: None = None
    ) -> Union['cirq.Pauli', 'cirq.IdentityGate', None]:
        pass

    @overload
    def get(
        self, key: TKey, default: TDefault
    ) -> Union['cirq.Pauli', 'cirq.IdentityGate', TDefault]:
        pass

    def get(self, key: TKey, default=None):
        result = self.pauli_int_dict.get(key, None)
        return default if result is None else _INT_TO_PAULI[result]

    # pylint: enable=function-redefined

    def inplace_before(self, ops: 'cirq.OP_TREE') -> 'cirq.MutablePauliString':
        r"""Propagates the pauli string from after to before a Clifford effect.

        If the old value of the MutablePauliString is $P$ and the Clifford
        operation is $C$, then the new value of the MutablePauliString is
        $C^\dagger P C$.

        Args:
            ops: A stabilizer operation or nested collection of stabilizer
                operations.

        Returns:
            The mutable pauli string that was mutated.
        """
        return self.inplace_after(protocols.inverse(ops))

    def inplace_after(self, ops: 'cirq.OP_TREE') -> 'cirq.MutablePauliString':
        r"""Propagates the pauli string from before to after a Clifford effect.

        If the old value of the MutablePauliString is $P$ and the Clifford
        operation is $C$, then the new value of the MutablePauliString is
        $C P C^\dagger$.

        Args:
            ops: A stabilizer operation or nested collection of stabilizer
                operations.

        Returns:
            The mutable pauli string that was mutated.
        """
        for clifford in op_tree.flatten_to_ops(ops):
            for op in _decompose_into_cliffords(clifford):
                ps = [self.pauli_int_dict.pop(cast(TKey, q), 0) for q in op.qubits]
                if not any(ps):
                    continue
                gate = op.gate

                if isinstance(gate, clifford_gate.SingleQubitCliffordGate):
                    out = gate.transform(cast(pauli_gates.Pauli, _INT_TO_PAULI[ps[0]]))
                    if out.flip:
                        self.coefficient *= -1
                    self.pauli_int_dict[cast(TKey, op.qubits[0])] = PAULI_GATE_LIKE_TO_INDEX_MAP[
                        out.to
                    ]

                elif isinstance(gate, pauli_interaction_gate.PauliInteractionGate):
                    q0, q1 = op.qubits
                    p0 = _INT_TO_PAULI[ps[0]]
                    p1 = _INT_TO_PAULI[ps[1]]

                    # Kick across Paulis that anti-commute with the controls.
                    kickback_0_to_1 = not protocols.commutes(p0, gate.pauli0)
                    kickback_1_to_0 = not protocols.commutes(p1, gate.pauli1)
                    kick0 = gate.pauli1 if kickback_0_to_1 else identity.I
                    kick1 = gate.pauli0 if kickback_1_to_0 else identity.I
                    self.__imul__({q0: p0, q1: kick0})
                    self.__imul__({q0: kick1, q1: p1})

                    # Decompose inverted controls into single-qubit operations.
                    if gate.invert0:
                        self.inplace_after(gate.pauli1(q1))
                    if gate.invert1:
                        self.inplace_after(gate.pauli0(q0))

                else:
                    # coverage: ignore
                    raise NotImplementedError(f"Unrecognized decomposed Clifford: {op!r}")
        return self

    def _imul_helper(self, other: 'cirq.PAULI_STRING_LIKE', sign: int):
        """Left-multiplies or right-multiplies by a PAULI_STRING_LIKE.

        Args:
            other: What to multiply by.
            sign: +1 to left-multiply, -1 to right-multiply.

        Returns:
            self on success, NotImplemented given an unknown type of value.
        """

        if isinstance(other, (Mapping, PauliString, MutablePauliString)):
            if isinstance(other, (PauliString, MutablePauliString)):
                self.coefficient *= other.coefficient
            phase_log_i = 0
            for qubit, pauli_gate_like in other.items():
                pauli_int = _pauli_like_to_pauli_int(qubit, pauli_gate_like)
                phase_log_i += self._imul_atom_helper(cast(TKey, qubit), pauli_int, sign)
            self.coefficient *= 1j ** (phase_log_i & 3)
        elif isinstance(other, numbers.Number):
            self.coefficient *= complex(cast(SupportsComplex, other))
        elif isinstance(other, raw_types.Operation) and isinstance(
            other.gate, identity.IdentityGate
        ):
            pass
        elif isinstance(other, Iterable) and not isinstance(other, str):
            if sign == +1:
                other = reversed(list(other))
            for item in other:
                if self._imul_helper(cast(PAULI_STRING_LIKE, item), sign) is NotImplemented:
                    return NotImplemented
        else:
            return NotImplemented

        return self

    def _imul_helper_checkpoint(self, other: 'cirq.PAULI_STRING_LIKE', sign: int):
        """Like `_imul_helper` but guarantees no-op on error."""
        if not isinstance(other, (numbers.Number, PauliString, MutablePauliString)):
            other = MutablePauliString()._imul_helper(other, sign)
            if other is NotImplemented:
                return NotImplemented
        return self._imul_helper(other, sign)

    def inplace_left_multiply_by(
        self, other: 'cirq.PAULI_STRING_LIKE'
    ) -> 'cirq.MutablePauliString':
        """Left-multiplies a pauli string into this pauli string.

        Args:
            other: A pauli string or `cirq.PAULI_STRING_LIKE` to left-multiply
                into `self`.

        Returns:
            The `self` mutable pauli string that was mutated.

        Raises:
            TypeError: `other` was not a `cirq.PAULI_STRING_LIKE`. `self`
                was not mutated.
        """
        if self._imul_helper_checkpoint(other, -1) is NotImplemented:
            raise TypeError(f"{other!r} is not cirq.PAULI_STRING_LIKE.")
        return self

    def _json_dict_(self) -> Dict[str, Any]:
        return {
            'cirq_type': self.__class__.__name__,
            # JSON requires mappings to have string keys.
            'pauli_int_dict': list(self.pauli_int_dict.items()),
            'coefficient': self.coefficient,
        }

    @classmethod
    def _from_json_dict_(cls, pauli_int_dict, coefficient, **kwargs):
        return cls(pauli_int_dict=dict(pauli_int_dict), coefficient=coefficient)

    def inplace_right_multiply_by(
        self, other: 'cirq.PAULI_STRING_LIKE'
    ) -> 'cirq.MutablePauliString':
        """Right-multiplies a pauli string into this pauli string.

        Args:
            other: A pauli string or `cirq.PAULI_STRING_LIKE` to right-multiply
                into `self`.

        Returns:
            The `self` mutable pauli string that was mutated.

        Raises:
            TypeError: `other` was not a `cirq.PAULI_STRING_LIKE`. `self`
                was not mutated.
        """
        if self._imul_helper_checkpoint(other, +1) is NotImplemented:
            raise TypeError(f"{other!r} is not cirq.PAULI_STRING_LIKE.")
        return self

    def __neg__(self) -> 'cirq.MutablePauliString':
        result = self.mutable_copy()
        result.coefficient *= -1
        return result

    def __pos__(self) -> 'cirq.MutablePauliString':
        return self.mutable_copy()

    def transform_qubits(
        self, func: Callable[[TKey], TKeyNew], *, inplace: bool = False
    ) -> 'cirq.MutablePauliString[TKeyNew]':
        """Returns a mutable pauli string with transformed qubits.

        Args:
            func: The qubit transformation to apply.
            inplace: If false (the default), creates a new mutable pauli string
                to store the result. If true, overwrites this mutable pauli
                string's contents. Defaults to false for consistency with
                `cirq.PauliString.transform_qubits` in situations where the
                pauli string being used may or may not be mutable.

        Returns:
            A transformed MutablePauliString.
            If inplace=True, returns `self`.
            If inplace=False, returns a new instance.
        """
        new_dict = {func(q): p for q, p in self.pauli_int_dict.items()}
        if not inplace:
            return MutablePauliString(
                coefficient=self.coefficient,
                pauli_int_dict=new_dict,
            )
        result = cast('cirq.MutablePauliString[TKeyNew]', self)
        result.pauli_int_dict = new_dict
        return result

    def __imul__(self, other: 'cirq.PAULI_STRING_LIKE') -> 'cirq.MutablePauliString':
        """Left-multiplies a pauli string into this pauli string.

        Args:
            other: A pauli string or `cirq.PAULI_STRING_LIKE` to left-multiply
                into `self`.

        Returns:
            The `self` mutable pauli string that was successfully mutated.

            If `other` is not a `cirq.PAULI_STRING_LIKE`, `self` is not mutated
            and `NotImplemented` is returned.

        """
        return self._imul_helper_checkpoint(other, +1)

    def __mul__(self, other: 'cirq.PAULI_STRING_LIKE') -> 'cirq.PauliString':
        """Multiplies two pauli-string-likes together.

        The result is not mutable.
        """
        return self.frozen() * other

    def __rmul__(self, other: 'cirq.PAULI_STRING_LIKE') -> 'cirq.PauliString':
        """Multiplies two pauli-string-likes together.

        The result is not mutable.
        """
        return other * self.frozen()

    def __str__(self) -> str:
        return f'mutable {self.frozen()}'

    def __repr__(self) -> str:
        return f'{self.frozen()!r}.mutable_copy()'


def _decompose_into_cliffords(op: 'cirq.Operation') -> List['cirq.Operation']:
    # An operation that can be ignored?
    if isinstance(op, global_phase_op.GlobalPhaseOperation):
        return []

    # Already a known Clifford?
    if isinstance(
        op.gate,
        (clifford_gate.SingleQubitCliffordGate, pauli_interaction_gate.PauliInteractionGate),
    ):
        return [op]

    # Specifies a decomposition into Cliffords?
    v = getattr(op, '_decompose_into_clifford_', None)
    if v is not None:
        result = v()
        if result is not None and result is not NotImplemented:
            return list(op_tree.flatten_to_ops(result))

    # Specifies a decomposition that happens to contain only Cliffords?
    decomposed = protocols.decompose_once(op, None)
    if decomposed is not None:
        return [out for sub_op in decomposed for out in _decompose_into_cliffords(sub_op)]

    raise TypeError(
        f'Operation is not a known Clifford and did not decompose into known Cliffords: {op!r}'
    )


# Mypy has extreme difficulty with these constants for some reason.
_i = cast(identity.IdentityGate, identity.I)  # type: ignore
_x = cast(pauli_gates.Pauli, pauli_gates.X)  # type: ignore
_y = cast(pauli_gates.Pauli, pauli_gates.Y)  # type: ignore
_z = cast(pauli_gates.Pauli, pauli_gates.Z)  # type: ignore

PAULI_GATE_LIKE_TO_INDEX_MAP: Dict['cirq.PAULI_GATE_LIKE', int] = {
    _i: 0,
    _x: 1,
    _y: 2,
    _z: 3,
    'I': 0,
    'X': 1,
    'Y': 2,
    'Z': 3,
    'i': 0,
    'x': 1,
    'y': 2,
    'z': 3,
    0: 0,
    1: 1,
    2: 2,
    3: 3,
}

_INT_TO_PAULI: List[Union['cirq.Pauli', 'cirq.IdentityGate']] = [_i, _x, _y, _z]

PAULI_GATE_LIKE_TO_GATE_MAP: Dict[
    'cirq.PAULI_GATE_LIKE', Union['cirq.Pauli', 'cirq.IdentityGate']
] = {k: _INT_TO_PAULI[v] for k, v in PAULI_GATE_LIKE_TO_INDEX_MAP.items()}


def _pauli_like_to_pauli_int(key: Any, pauli_gate_like: PAULI_GATE_LIKE):
    pauli_int = PAULI_GATE_LIKE_TO_INDEX_MAP.get(pauli_gate_like, None)
    if pauli_int is None:
        raise TypeError(
            f'Expected {key!r}: {pauli_gate_like!r} to have a '
            f'cirq.PAULI_GATE_LIKE value. '
            f"But the value isn't in "
            f"{list(PAULI_GATE_LIKE_TO_INDEX_MAP.keys())!r}"
        )
    return cast(int, pauli_int)