I am working on learning grouped measurement and I began by reading this paper by a group out of UChicago showing a method for the synthesis of circuits for the grouped measurement of a set of commuting Pauli Operators. I tried it for a simple problem, electronic Hamiltonian for H2. I used the code they reference on their github and Pennylane and some hacking to get it to work for other groups. However, when I pass this subset of Pauli operators $P = \{ X_0 X_1 Y_2 Y_3, X_0 Y_1 Y_2 X_3, Y_0 X_1 X_2 Y_3, Y_0 Y_1 X_2 X_3 \}$ the algorithm fails to generate a circuit.
The stabilizer matrix takes form $$ S = \begin{pmatrix} 0 & 0& 1& 1 \\ 0& 1& 0& 1 \\ 1& 1& 0& 0 \\ 1& 0& 1& 0 \\ 1& 1& 1& 1 \\ 1& 1& 1& 1 \\ 1& 1& 1& 1 \\ 1& 1& 1& 1 \end{pmatrix} = \begin{pmatrix} Z \\ X \end{pmatrix} $$
Where the Z-matrix refers to the first 4 rows of the stabilizer matrix. Each row corresponds to whether there's an Pauli-Z matrix acting on that site. Similarly, for the X-matrix (bottom 4 rows). A Pauli-Y operator on site i of the jth operator is represented as 1 at the ith row and jth column of the X matrix and a 1 at the ith row and jth column of the Z matrix. We adopt the Pauli group sans phase, i.e. XZ = ZX = Y.
The goal is to get the X-matrix into full rank by applying Hadamard gates, which serve as a row-swap elementary row operation. The problem is, the X-matrix has at most rank 3 even after the application of row-swaps with the Z-matrix. This seems to be a problem since lemma 6 of Efficient Simulation of Stabilizer Circuits, states "it is always possible to apply Hadamard gates to a subset of the qubits so as to make the X matrix have full rank".
I looked into the algebra of this group. The first thought I had was that since the max rank of the X-matrix was 3, maybe a 3-term subset of this group would suffice to span the rest of the set. But this group does not have that property. Any attempt to partition into subsets and you won't be able to get the rest of the elements back via multiplication.
How do I compute the diagonalizing unitary $U; UP_iU^\dagger = I_0...I_{i-1}Z_iI_{i+1}...I_{n-1}$ for this group if not by this method?
