# Algorithm for Mutually Unbiased Basis Sets Available?

I'm looking for an implementation or a slightly more efficient algorithm for finding optimal Mutually Unbiased Bases (MUB). What I mean here are MUBs in terms of Pauli Strings as described here. There are implementations in Qiskit available which do not give the optimal partitioning into MUBs, however I need the optimal partitioning, namely for Pauli strings of length $$n$$ there should be $$2^n+1$$ sets with $$2^n-1$$ mutually commuting elements each. For example $$n=2$$ can yield the partitioning:

$$'IZ', 'ZI', 'ZZ'$$ $$'IX', 'XI', 'XX'$$ $$'XZ', 'YX', 'ZY'$$ $$'YI', 'IY', 'YY'$$ $$'ZX', 'XY', 'YZ'$$

Sets which consist of $$Z$$ and $$I$$ only can be fixed beforehand in my case such that the problem reduces to finding $$2^n$$ sets with $$2^n-1$$ elements. Since this problem is supposed to be NP-hard as described here, I'm looking for implementations which make it at least a bit smarter than I do. I implemented an algorithm (which constructs the sets step by step in a bruteforce manner) but with this I am only able to find the sets for $$n=2$$ and $$n=3$$, anything above takes drastically more time. I was browsing the literature already but could not find anything - has anyone hints?

• Not sure if this improves on the bruteforce algorithm you already have, but you might try looking for faster algorithms to the minimum clique cover problem. For example, a quick Google search reveals a python implementation of a backtracking algorithm for the problem: github.com/farjasju/CliqueCover. Jun 29, 2023 at 20:11
• However that it seems the problem is generally always very hard, because solving MCC takes time exponential in the problem size. The size of the Pauli graph is $4^n-1$, translating to a time complexity of $\exp(O(4^n))$ - doubly exponential in the number of qubits. Jun 29, 2023 at 20:16