The class of instantaneous quantum polynomial (IQP) circuits is an interesting restricted model of quantum computation - circuits running according to the model likely cannot achieve the full scope of quantum computing (nor even of classical computing) but nonetheless it may be difficult to classically sample from the corresponding distribution/wavefunction so obtained. This class is also referred to as a "commuting quantum model" as the gates are all diagonal in the computational basis and commute with one another.
This paper from Bremnar, Montenaro, and Shepard suggests that $CS=\sqrt{CZ}=\mathrm{diag}(1,1,1,i)$ and $T=R(\pi/4)$ gates, when sandwiched between Hadamard gates applied initially to the all-zero's ket, serve to generate (or be exponentially close to generating) all IQP circuits.
But, how can we show that $\sqrt{CZ}$ and $T$ gates generate all such diagonal matrices? For example, what would a circuit for $\mathrm{diag}(i,1,1,1)$ or $\mathrm{diag}(1,i,1,1)$ look like? (Presumably there are some hidden SWAPs used in case $CS$ can only be applied to neighboring qubits).
My intuition is that the Solovay-Kitaev proof doesn't carry through, as we cannot use arbitrary Hadamard gates.
