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.
Edit: As @glS has mentioned, an overall phase of $-1$ may be needed if the upper-left element is $-1$. Still, after adjusted for this $-1$ phase, my question remains.
No. This way, you only can get (a subset of) stabilizer circuits, but there are clearly gates which are not stabilizer circuits.
An example is the three-qubit gate $$ \begin{pmatrix}1\\ &1\\ &&1\\&&&1\\&&&&1\\&&&&&1\\&&&&&&1\\&&&&&&&-1 \end{pmatrix} $$ You can see that this is not a stabilizer by applying a Hadamard to the third qubit on both sides: Then, you get a Toffoli gate, which is not a stabilizer (in fact, together with stabilizers it allows to do universal quantum computation).
Another way to see that this is impossible is to just count the number of diagonal gates with $\pm1$ -- there are $2^{(2^N)}$) of those -- and compare them to the number of gates you can build with your recipe -- since they all commute, there are $2^{(N^2)}$ ways of putting the CZs, and $2^N$ ways of putting the $Z$'s, which is exponentially less.
Note that the counting argument does, in fact, give a more general impossibility argument for realizing such gates using only a limited class of diagonal gates.
