Sparse operators on extended alphabets

[nonhermitian]

What should we add?

The current primary operator class in Qiskit, SparsePauliOp, is limited to only Pauli observables, and is actually not sparse, but rather holds data in the form of two dense NumPy arrays. This design choice comes with several limitations. First, the restriction to Pauli operators means that one cannot use the current class for computing expectation values of projector operators, like those used in QML kernel methods, requiring a Pauli decomposition that scales exponentially. Second, the choice of internal representation results in a memory footprint and operator construction time that is larger than other quantum SDKs.

Instead, Qiskit should move to a real sparse format that allows for operations on extended alphabets that include projection operators, the most important being '0' and '1'. The limited alphabet can be stored efficiently where the indices of only non-identity terms should be kept in the data structure.