General structure of parity preserving two qubit gate

I am trying to decompose a set of two qubit gates repecting parity, though I am not sure whether parity is the right word for this. The gate has the following structure:

$$\begin{bmatrix} u_{11}&0&0&u_{12} \\ 0&v_{11}&v_{12}&0 \\ 0&v_{21}&v_{22}&0 \\ u_{21}&0&0&u{22} \end{bmatrix} .$$

This symmetry requirement is required for quantum gates acting on two fermions. In the spin language it is preserving a $$Z_2$$ symmety.

I want to decompose this gate into a gate consisting CNOT gate and arbitrary single qubit gates. I adopt the optimal decomposition method for general two qubit gates. It generally takes three CNOT gates. Since CNOT gates are especially prone to error due to the longer evolution time times compared with single qubit gates, I wonder if I can reduce the number of CNOT gates further.

What structure in the two qubit gates would determine the number of CNOT gates used? If I want to preserve parity while having nontrivial unitary gates (other than identity), is three CNOT gates the least I can get?

• C-Z can do with less. Sep 10, 2019 at 15:27
• @NorbertSchuch That can't be right; the CZ differs from the CNOT only in single qubit rotations and in this context those are free. Sep 20, 2019 at 10:01
• @CraigGidney And in order to implement the CNOT gate using only CNOT gates and local unitaries, only one CNOT gate is required. Although it is of course also possible to do it with three. Sep 20, 2019 at 13:53
• @NorbertSchuch Oh I see, you were pointing out that implementing a CZ with CNOTs would only require 1 CNOT, not saying that you could use fewer CZs to perform a given operation. Sep 20, 2019 at 18:03
• @CraigGidney That's what the question asked. Sep 20, 2019 at 18:55

Consider the operation $$U(a, b) = e^{ia(X\otimes X+Y\otimes Y)} \cdot e^{ibZ\otimes Z}$$
This operation preserves $$Z_2$$ symmetry. In fact it preserves the total number of set bits, so it's even more restrictive.
When you take the Cartan KAK decomposition of this operation, you just get the same operation back. That is to say, the interaction coefficients are $$(x=a, y=a, z=b)$$. Whenever the three interaction coefficients of an operation are all not zero, you need three CNOTs in order to implement it. Except for a measure zero subset where $$a=0$$ or $$b=0$$, $$Z_2$$ preserving operations require three CNOTs.
This is the rule: the number of CNOTs is at least the number of non-zero interaction coefficients in the KAK decomposition, and if there's an interaction coefficient that's not 0 and not pi/4 then you need at least two CNOTs. (Example decomposition code in Cirq's two_qubit_matrix_to_operations method.)