# Is it possible to receive the optimal commuting partitioning of pauli strings (MIN-COMMUTING-PARTITION)

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?

• Why do you say there are $2^n+1$ sets? For $n=2$, why can't I have the set $\{I\otimes Z, X\otimes I, X\otimes Z\}$, for example? Are you requiring that the sets are distinct? May 10 at 12:24
• @DaftWullie That $2^n+1$ sets with $2^n-1$ are the optimal partition is mentioned in the linked paper (section 2 F): "It is known that for $N$ qubits, there exists an MUB with $2^N+1$ rows and $2^N-1$ Pauli strings per row. This is optimal in the sense that $2^N-1$ is the maximum possible number of distinct Pauli strings (excluding identity) within a commuting family." Yes, the sets must be distinct. May 10 at 13:00