1
$\begingroup$

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?

$\endgroup$
2
  • $\begingroup$ 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. $\endgroup$ Jun 29, 2023 at 20:11
  • $\begingroup$ 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. $\endgroup$ Jun 29, 2023 at 20:16

2 Answers 2

2
$\begingroup$

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.

$\endgroup$
1
  • $\begingroup$ Thanks for your hints! However, the problem with approximate solutions is that the resulting sets deviate from the optimal size (often there are more sets with fewer elements, this also happens e.g. in the Qiskit Implementation). However, I need indeed the optimal sets for the implementation of another algorithm (which strictly relies on the optimal sets). Could you possibly elaborate on the specific group theoretic properties etc. of Pauli strings which could be utilized here? Do you know references which deal with this? Thanks in advance!(: $\endgroup$
    – Juri V
    Jun 29, 2023 at 8:26
2
$\begingroup$

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.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.