Add sparse representation support to cirq.DensePauliString

[tanujkhattar]

Is your feature request related to a use case or problem? Please describe.
cirq.PauliString drops identity gates by default and only stores non-identity terms. Therefore, a pauli sum hamiltonian $H$ acting on $N$ qubits and containing $M$ different pauli strings as part of the paul sum will contain $M$ * Avg(#non-identity terms per pauli string) different terms.

However, if we want to represent the same Hamiltonian as a sum of dense pauli strings (gate version, which can be applied on any set of target qubits); the number of terms in the representation will scale as $M\ast N$. For chemistry Hamiltonians; $N$ can be upto 1000 and $M$ is at least $N\ast \ast 2$; therefore the dense pauli string representation will scale as $N\ast \ast 3$ or more; which is pretty bad. As an example:

In [1]: import cirq, itertools

In [2]: def create_H_dps(N: int): # Uses trick to use mutable dense pauli strings and avoid copies to speed up the construction. 
   ...:     i_dps = cirq.MutableDensePauliString.eye(N)
   ...:     H_dps = []
   ...:     for a, b in itertools.product(range(N), range(N)):
   ...:         c = 'Z' if a != b else 'I'
   ...:         i_dps[a], i_dps[b] = c, c
   ...:         H_dps.append(i_dps.frozen())
   ...:         i_dps[a], i_dps[b] = 'I', 'I'
   ...:     return H_dps
In [3]: def create_H_ps(q):
   ...:     return [cirq.Z(a) * cirq.Z(b) for a, b in itertools.product(q, q)]

In [4]: N = 500 # N = 500
In [5]: q = cirq.LineQubit.range(N)

In [6]: %time H_ps = create_H_ps(q) # Construct PauliString hamiltonian with M = N ** 2 terms.
CPU times: user 13 s, sys: 672 ms, total: 13.6 s
Wall time: 12.7 s
In [7]: %time H_dps = create_H_dps(N) # Construct PauliString hamiltonian with M = N ** 2 terms.
CPU times: user 1.24 s, sys: 36.5 ms, total: 1.28 s
Wall time: 1.27 s

In [8]: len(H_ps), sum(len(ps) for ps in H_ps) / len(H_ps) #PauliString representation has length ~2 for each term in the sum.
Out[8]: (250000, 1.996)

In [9]: len(H_dps), sum(len(dps) for dps in H_dps) / len(H_dps) #DensePauliString representation has length N for each term in the sum.
Out[9]: (250000, 500.0)

Describe the solution you'd like
We should provide a way to store a dense representation of dense pauli strings which ignore identity terms, similar to pauli strings; so it can easily scale for large Hamiltonians.

What is the urgency from your perspective for this issue? Is it blocking important work?
P2 - we should do it in the next couple of quarters

[tanujkhattar]

Discussion from cirq sync:

We should do it. In terms of implementations, it's probably best to add a flag to DensePauliString which can control whether the internal representation is sparse or not since we are not allowed to do breaking changes after Cirq 1.0 and changing internal representation of dense pauli strings by default would be a breaking change (is it?? cc @95-martin-orion @verult @MichaelBroughton )

[daxfohl]

IIUC this is similar to a previous request for a CircuitOperationGate. Different target, but the same premise: we need a way to make complex gates where the actions are specified by indices, such that that later those indices can be mapped qubits.

I've been thinking for a while, does it make sense to do this more generally? Basically, get rid of qubits at the gate/operation layer, and use indices there instead. Then introduce qubits at the circuit/device/simulator layer. Ideally that approach would allow flattening of the gate/operation layer, so we don't have to maintain two different classes for each gate type. Of course it's a big change, but might it be something to consider?