# 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
Commented May 20, 2021 at 8:11
• Oh yeah right. I guess an overall phase of -1 is also needed. Commented 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
Commented 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. Commented May 20, 2021 at 9:57
• Never said it is a problem! Commented May 20, 2021 at 18:57

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.