Consider diagonal quantum gates with eigenvalues $\pm 1$, i.e. all diagonal elements are either $+1$ or $-1$.
Can these gates always be decomposed into a finite number of Z and controlled-Z gates?
My gut feeling says yes, but I don't know how to prove it.
This is false. Let $n$ be the number of qubits. Since $Z$ and controlled-$Z$ gates all commute, only a total of $2^{O(n^2)}$ unitaries can be implemented with them, yet there are $2^{2^n-1}$ unitaries $U$ with $\pm 1$ on the diagonals ($U$ and $-U$ are considered the same unitary). This means that there is at least one $U$ that cannot be implemented.