In this paper the authors describe that the MIN-COMMUTING-PARTITION problem is NP-hard. This problem is about finding sets of Pauli strings (of length $n$) in which the strings mutually commute - the size and number of sets should be optimal, i.e. $2^n+1$ sets with $2^n-1$ elements each. For $n=2$ it is possible to figure it out the sets by hand:
$$\{ 1\otimes Z, Z\otimes 1, Z\otimes Z\}$$ $$ \{ 1\otimes X, X\otimes 1, X\otimes X\} $$ $$ \{ 1\otimes Y, Y\otimes 1, Y\otimes Y\} $$ $$ \{ X\otimes Z, Z\otimes Y, Y\otimes X \} $$ $$ \{ Z\otimes X, Y\otimes Z, X\otimes Y \} $$
However, I fail at finding the corresponding sets already for $n=3$. Also writing a brute force algorithm did not lead me anywhere (but this might also due to bugs and impatience regarding the running time). Is there somewhere an implementation on github or somewhere else which implements an algorithm to find those optimal sets? I know, the problem is NP-hard, but it should work for small instance nevertheless ($n=3,4...$), right?
An approximate case is e.g. available in qiskit, but I urgently need optimal sets for at least small $n$. Could anyone help?
