# Is $\{Z, CZ\}$ an universal quantum gate set for diagonal gates with eigenvalues +1 and -1?

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.

• neither of them has a $-1$ on the upper left, so how are you going to get the matrix ${\rm diag}(-1,1,1,1)$?
– glS
May 20, 2021 at 8:11
• Oh yeah right. I guess an overall phase of -1 is also needed. May 20, 2021 at 9:43
• well, then you can just verify that you can get the four diagonal matrices with a single $-1$, modulo global phase, no? E.g. you can use $Z_1 Z_2 {\rm CZ}, Z_2 {\rm CZ}, Z_1 {\rm CZ}$, and ${\rm CZ}$
– glS
May 20, 2021 at 9:46
• I am considering quantum gates for an arbitrary number of qubits. A reference point for this problem is that the {CNOT, H, S, T} gate set is universal for any operation possible on a quantum computer. May 20, 2021 at 9:57
• Never said it is a problem! May 20, 2021 at 18:57

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.