1

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?

Juri V
  • 115
  • 7

2 Answers2

2

You can use heuristic algorithms or optimization techniques to search for good approximate solutions. These algorithms aim to find suboptimal solutions that are close to the optimal partitioning of MUBs. Metaheuristic algorithms such as genetic algorithms, simulated annealing, or tabu search can be applied to explore the solution space and find good approximations.

The symmetry properties and constraints can be used to reduce the search space and improve efficiency. Exploiting the properties of Pauli matrices and their relations can help in constructing the MUBs more efficiently. For example, you can use techniques such as group theory, combinatorial optimization, or algebraic techniques to find patterns and exploit symmetries.

Gandalf73
  • 133
  • 6
2

Even though I did not find an implementation, I had a look at mathematical constructions of those MUBs in prime power dimensions - what I've found was this paper and I implemented the described mathematical construction in python. So far I could get the MUB for up to 7 qubits, where the latter took approximately an hour.

Juri V
  • 115
  • 7