# Counting complete sets of mutually unbiased bases composed of stabilizer states

Consider $N$ qubits. There are many complete sets of $2^N+1$ mutually unbiased bases formed exclusively of stabilizer states. How many?

Each complete set can be constructed as follows: partition the set of $4^N-1$ Pauli operators (excluding the identity) into $(2^N+1)$ sets of $(2^N-1)$ mutually commuting operators. Each set of commuting Paulis forms a group (if you also include the identity and "copies" of the Paulis with added phases $\pm 1$, $\pm i$). The common eigenstates of the operators in each such group form a basis for the Hilbert space, and the bases are mutually unbiased. So the question is how many different such partitions there exist for $N$ qubits. For $N=2$ there are six partitions, for $N=3$ there are 960 (as I found computationally).

The construction above (due to Lawrence et al., see below) may be an example of a structure common in other discrete groups - a partition of the group elements into (almost) disjoint abelian subgroups having only the identity in common. Does anyone know about this?

Reference:

Mutually unbiased binary observable sets on N qubits - Jay Lawrence, Caslav Brukner, Anton Zeilinger, http://arxiv.org/abs/quant-ph/0104012

-

Here is an answer that should work. I do not currently have access to matlab to check this for anything other than the smallest cases, so you should do that.

First off, I find it easier personally to work in the reduced set of $3^N-1$ stabilizers for N qubits (generating the other from those). Entirely a personal preference, and doesn't change the result here.

So we want to divide the $3^N-1$ possible stabilizers into sets of $2^N-2$ commuting stabilizers, and find how many such divisions are possible.

Define

$\alpha = 2^N-2$ = size of sets

$\beta = \frac{3^N-1}{2^N-2}$ = number of sets.

We now pick our sets from the available stabilizers. The first time, we can pick anything - $3^N-1$ choices. Then we have to pick a commuting set, which we'll come back to. After picking the set, there are $(3^N-1) - \alpha$ stabilizers remaining. We can pick any for the first of the next set. And so on. However, for the final set there is no choice: there will only be $\alpha$ stabilizers left. So the choices for the first entry of each set are

$F = \prod_{k=0}^{\beta-2}(3^N-1) - \alpha k$

Now to pick each set. On average, half the stabilizers remaining to chose from will commute with any given one. So picking the second one, half the remainder will do. So for the first set, we have $((3^N-1) - 1)/2$ choices. The next choice has to commute with both the previous ones, so we have $((3^N-1) - 2)/2^2$ choices. And so on. For the next set, we start with $(3^N-1) - (\alpha+1)$ remaining stabilizers to pick the second entry. So the choices for picking the sets are

$S = \prod_{m=1}^{\beta} \prod_{i=1}^{\alpha-1}( \frac{3^N - (\alpha m + 1) - i)}{2^{i+1}} )$

So the number of possible partitions is $F.S$ divided by the number of possible ways to permute within the sets x number of sets (PR) and number of ways of permuting the sets themselves (PC):

$PR = \beta.\alpha !$

$PC = \beta !$

So the number of partitions is $\frac{F.S}{PR.PC}$

-
Thanks for thinking about this problem, but I got lost right at the beginning of your argument. If you want to work with the Pauli operators that exclude identity on any qubit, there should be $3^N$ operators, and not $3^N-1$. Perhaps it's better to keep track of a set of generators of each Abelian group, there are $N$ such operators in each set. Also, the number of sets must correspond to the maximum number of Mutually unbiased bases, so there should be $2^N+1$ sets, and not $\beta$ as you state above. –  Ernesto Oct 6 '11 at 11:59
The reduced set is the one that excludes all extensions of Pauli-Y as these can be produced by multiplying together some of the stabilizers that remain. It is just a way to reduce to all the independent stabilizers. In the same way, you can produce the extra sets for the MUBs from the reduced sets by the relevant multiplication. As the question was about the number of partitions, not the number of sets, this reduced representation is fine. Any set can be expanded to give all the MUBs corresponding to it. –  Clare Oct 6 '11 at 12:57
I agree one can use X and Z's only. The number of sets, however, has to be exactly $2^N-1$, as that is the number of required MUB. Notice that your number of sets $\beta$ may be fractional! Moreover, you argue that to pick the stabilizers in each set it is enough to choose stabilizers that commute with the previously chosen ones in the set; unfortunately this is not sufficient. If you pick your stabilizers with only this concern, you can paint yourself into a corner, as it may be impossible to partition the remaining operators into commuting sets. The reference has useful, explicit examples. –  Ernesto Oct 6 '11 at 17:34
Sorry for the mistake in the previous comment, the number of sets must be $2^N+1$. So the point is that if you pick your bases carelessly, you may find yourself in a situation in which the remaining operators cannot be partitioned as wanted. So the problem seems to be a complicated combinatorial problem, as opposed to a simple enumeration one. –  Ernesto Oct 6 '11 at 17:43
The above argument takes in the combinatorics of "painting into a corner" - as the number remaining gets smaller, the elements in S will start becoming fractional, showing what fraction of the previous combinations are valid. You can run this argument with $4^N-1$ instead of $3^N-1$, and $2^N-1, 2^N+1$ instead of $\alpha,\beta$ if you like. –  Clare Oct 7 '11 at 1:15

For finite dimensional systems, R. Buniy and T Kephart in 1012.2630 quant-ph provide a tool for defining a set of equivalence classes for entanglement states based on their algebraic properties. Your answer should be in there.

-