On the connection between mutually unbiased bases and orthogonal Latin squares

T. Paterek, M. Pawlowski, M. Grassl, C. Brukner

Introduction

Mutually unbiased bases (MUB) encapsulate the concept of complementarity in quantum formalism. Quantum observables associated with these bases are maximally complementary in the sense that given a system in an eigenstate of one observable, measurement outcomes of the other observables are completely random. Although the complementarity is a distinguishing feature of quantum mechanics, we still do not know what the total number of mutually maximally complementary observables for a general $d$ -level system is.

It is known that for $d$ being a power of a prime, there are $d+1$ MUBs and this number sets the upper bound for arbitrary $d$ . For all other dimensions, it is a puzzle whether this bound is saturated. Solving this problem gives insight not only into physics, but also to mathematics, as the problem is linked with other unsolved mathematical problems . It was also noticed that it is similar in spirit to some combinatorial problems and problems in finite geometry . Here, we shall briefly review and study one such connection .

The problem which is assumed to be connected to finding the number of MUBs is that of finding the number of mutually orthogonal Latin squares (MOLS). The latter has a long history originating in the works by Euler and more is known about it than about the number of MUBs. For example, it is known that there are no more than three squares in the augmented set of MOLS of order six , but the question whether or not there are more than three MUBs in dimension six is still open. The connection of Ref. allows to link every square in an augmented set of MOLS with a MUB for power-of-prime dimensions and dimension six. Here we show that this connection fails in composite dimensions for which MacNeish’s bound is not tight . We study in detail the case of $d=10$ , being the smallest $d$ with this property: while there are at least four squares in an augmented set of MOLS, one cannot find more than three MUBs using the link of Ref. .

The connection

A Latin square of order $d$ is an array of numbers $\{0,...,d-1\}$ where every row and every column contains each number exactly once. Two Latin squares, $A=[A_{ij}]$ and $B=[B_{ij}]$ , are orthogonal if all ordered pairs $(A_{ij},B_{ij})$ are distinct. There are at most $d-1$ MOLS, and such a set of MOLS is called complete. Complete sets of MOLS are known to exist for $d$ being a power of a prime. It is also known that there are no two MOLS in dimension six . The existence of $L$ MOLS is equivalent to the existence of a combinatorial design called a net with $L+2$ rows . The net design has a form of a table in which every row contains $d^{2}$ distinct numbers. They are grouped into $d$ cells of $d$ numbers each, in such a way that the numbers of any cell in a given row are distributed among all cells of any other row. The additional two rows of the net design correspond to orthogonal but not Latin squares, with the entries $A_{ij}=j$ and $A_{ij}=i$ . The set of all $L+2$ squares is referred to as the augmented set of MOLS. An algorithm to construct the design from a set of MOLS is given, e.g., in Ref. .

The MUBs are constructed using the entries of any cell of the design. We write the entries in modulo $d$ decomposition such that each of them is now represented by two integers: $m$ and $n$ , having values from the set $\{0,1,\ldots,d-1\}$ . These integers are taken as exponents of Weyl-Schwinger operators, $\hat{X}_{d}^{m}\hat{Z}_{d}^{n}$ , defined as:

with $\eta_{d}=\exp{(i2\pi/d)}$ being a complex $d$ th root of unity. The Weyl-Schwinger operators span an unitary operator basis which is orthogonal with respect to trace scalar product. If one can find sets of $d$ of them which commute (each set including identity) the joint eigenbases of the commuting operators form MUBs . It turns out that for prime $d$ and for dimension six, the $d$ operators having exponents from a single cell of the design commute and therefore define MUBs . For power-of-prime $d=p^{r}$ , the operators having exponents from some cells do not commute. In order to obtain a complete set of $d+1$ MUBs one needs to take advantage of the fact that $d$ can be factored. In this case, every integer $m$ and $n$ from the net design can be represented by $r$ digits having their values from the set $\{0,1,\ldots,p-1\}$ , i.e. there is a mappingNote that there are many such mappings. Assuming that $m$ and $n$ can be decomposed independently gives $(d!)^{2}$ maps. $m\mapsto(m_{1},m_{2},\ldots,m_{r})$ and $n\mapsto(n_{1},n_{2},\ldots,n_{r})$ . We take these integers as exponents of tensor product operators $\hat{X}_{p}^{m_{1}}\hat{Z}_{p}^{n_{1}}\otimes\hat{X}_{p}^{m_{2}}\hat{Z}_{p}^{n_{2}}\otimes\ldots\otimes\hat{X}_{p}^{m_{r}}\hat{Z}_{p}^{n_{r}}$ . For suitable decompositions, related to finite fields, we find that the operators having exponents from a single cell of the design again commute and hence define MUBs.

MacNeish’s bound

MacNeish gave a lower bound on the number of MOLS . If two squares of order $a$ are orthogonal, $A\perp B$ , and two squares of order $b$ are orthogonal, $C\perp D$ , then the squares obtained by a direct product, of order $ab$ , are also orthogonal, $A\times C\perp B\times D$ . This implies that the number of MOLS, $\mathcal{L}$ , of order $d=p_{1}^{r_{1}}\ldots p_{n}^{r_{n}}$ , $p_{i}$ being prime factors of $d$ , is at least $\mathcal{L}\geq\min_{i}(p_{i}^{r_{i}}-1)$ , where $p_{i}^{r_{i}}-1$ is the number of MOLS of order $p_{i}^{r_{i}}$ .

A parallel result holds for MUBs , which we call the quantum MacNeish bound. If $|a\rangle$ and $|b\rangle$ are the states of two different MUBs in dimension $d_{1}$ , and $|c\rangle$ and $|d\rangle$ are the states of two MUBs in dimension $d_{2}$ , then the tensor product bases $|a\rangle\otimes|c\rangle$ and $|b\rangle\otimes|d\rangle$ form MUBs in dimension $d_{1}d_{2}$ . Thus, for $d=p_{1}^{r_{1}}\ldots p_{n}^{r_{n}}$ there are at least $\min_{i}(p_{i}^{r_{i}}+1)$ MUBs.

Our motivation to study dimension ten comes from the fact that it is the simplest case in which MacNeish’s bound is not tight. There are at least two MOLS of order ten, which is larger than MacNeish’s bound of one. If the connection established in Ref. holds generally, we shall correspondingly expect the quantum MacNeish bound not to be tight for $d=10$ . It is already known that the quantum bound is not tight in general, but the smalltest case for which it was proven is $d=26^{2}=676$ .

Ten dimensions

Using the algorithm of Ref. , the representative four cells of the net design read:

where we present pairs of numbers $m\,n$ . Writing the pairs as exponents of operators $\hat{X}_{10}^{m}\hat{Z}_{10}^{n}$ , the first row gives ten commuting operators $\hat{Z}_{10}^{n}$ and therefore defines the eigenbasis of $\hat{Z}_{10}$ . Similarly, the second row gives the eigenbasis of $\hat{X}_{10}$ , and the third row provides the eigenbasis of $\hat{X}_{10}\hat{Z}_{10}$ . However, the operators corresponding to the fourth row do not commute, e.g. $[\hat{X}_{10}^{2}\hat{Z}_{10}^{4},\hat{X}_{10}^{3}\hat{Z}_{10}^{9}]\neq 0$ , and in this way we do not improve upon the quantum MacNeish bound, which is three for $d=10$ .

Similar to the case of $d$ being a power of a prime, one may ask if there is a decomposition of $m$ and $n$ into pairs $m_{1}\,m_{2}$ and $n_{1}\,n_{2}$ (with $m_{1},n_{1}\in\{0,1\}$ and $m_{2},n_{2}\in\{0,1,2,3,4\}$ ), respectively, such that the operators $\hat{X}_{2}^{m_{1}}\hat{Z}_{2}^{n_{1}}\otimes\hat{X}_{5}^{m_{2}}\hat{Z}_{5}^{n_{2}}$ , having their exponents from the corresponding entries of the rows of (1), commute. However, contrary to the case of power-of-prime $d$ , for $d=d_{1}d_{2}$ with coprime factors, the problem of finding commuting operators $\hat{X}_{d_{1}}^{m_{1}}\hat{Z}_{d_{1}}^{n_{1}}\otimes\hat{X}_{d_{2}}^{m_{2}}\hat{Z}_{d_{2}}^{n_{2}}$ is equivalent to the problem of finding commuting operators $\hat{X}_{d}^{m}\hat{Z}_{d}^{n}$ . This is a consequence of the lemma in the appendix, which states that the tensor product operators and the operators in $d$ dimensions are related by a permutation.

We checked by grouping the commuting operators $\hat{X}_{10}^{m}\hat{Z}_{10}^{n}$ , that their eigenbases lead to at most three MUBs. Similarly, we verified for $d=35$ that there are at most six MUBs formed by the eigenbases of $\hat{X}_{35}^{m}\hat{Z}_{35}^{n}$ . These are independent proofs of special cases of the result by Aschbacher, Childs and Wocjan . In particular, they showed that the eigenbases of Weyl-Schwinger operators do not lead to more MUBs than given by the quantum MacNeish bound. Therefore, for all $d$ in which MacNeish’s bound on the number of MOLS is not tight, the connection of Ref. fails to relate all the squares with MUBs.

Conclusions

We presented some evidence that the physical problem of the number of MUBs might not be equivalent to the mathematical problem of the number of MOLS. The proof of this statement is still an open question.

Acknowledgments

This work is supported by the National Research Foundation and Ministry of Education in Singapore, and by the European Commission, Project QAP (No. 015848). ČB acknowledges support from the Austrian Science Foundation FWF within Project No. P19570-N16, SFB and CoQuS No. W1210-N16. The collaboration is a part of an ÖAD/MNiSW program.

Appendix

Lemma: If $d=d_{1}d_{2}$ with $\gcd(d_{1},d_{2})=1$ , there exists a permutation matrix $\hat{T}$ such that

Proof: Define the permutationIt follows from the Chinese remainder theorem that $\hat{T}$ is a permutation, and this is why $d$ has to have coprime factors. matrix $\hat{T}$ by:

where we used $\eta_{d_{i}}^{j}=\eta_{d_{i}}^{j\bmod d_{i}}=\eta_{d_{i}}^{j_{i}}$ for $i=1,2$ .