The problem of mutually unbiased bases in dimension 6

Introduction

This paper is based on the talk given by the second author at the International Conference on Design Theory and Applications, NUI, Galway, July 1-3, 2009.

The notion of mutually unbiased bases (MUBs) constitutes a basic concept of Quantum Information Theory and plays an essential role in quantum-tomography , quantum cryptography , the mean king problem as well as in constructions of teleportation and dense coding schemes .

One reason for the slow progress is that mutually unbiased bases are naturally related to complex Hadamard matrices. Indeed, if the bases $\mathcal{B}_{0},\ldots,\mathcal{B}_{m}$ are mutually unbiased we may identify each $\mathcal{B}_{l}=\{\mathbf{e}_{1}^{(l)},\ldots,\mathbf{e}_{d}^{(l)}\}$ with the unitary matrix

In particular, the existence of 4 MUBs $\mathcal{B}_{0},\mathcal{B}_{1},\mathcal{B}_{2},\mathcal{B}_{3}$ in dimension 6 is equivalent to the existence of 3 mutually unbiased Hadamard matrices $H_{1},H_{2},H_{3}.$ Therefore, in an attempt to prove that no collection of 4 MUBs exist in dimension 6 it is enough to prove that no triplet of mutually unbiased Hadamard matrices exist. This will be the core of our argument in this note.

A complete classification of complex Hadamard matrices, however, is only available up to dimension 5 (see ) which allows for a complete classification of MUBs (see ). The classification in dimension 6 is still out of reach despite recent efforts . This is one of the reasons for Problem 1.1 to be difficult.

In this paper we outline a discretization approach that is likely to lead to the proof of Conjecture 1.2 in the near future. Once all the ideas are properly implemented in a computer code, an exhaustive search will be carried out to prove Conjecture 1.2. We will include all the basic definitions and ideas as well as some preliminary results. We remark here that a partial result of this approach has already been completed: in we assumed that the first Hadamard matrix $H_{1}$ comes from the two-parameter Fourier family of complex Hadamard matrices, and we proved by discretization and an exhaustive computer search that in such a case a MUB-quartet $I,H_{1},H_{2},H_{3}$ cannot exist. In this paper, however, we tackle the general case, so that we must consider $H_{1}$ as any complex Hadamard matrix of dimension 6. This complicates matters quite considerably as the number of cases to check after the discretization increases by orders of magnitude. As an optimistic note let us recall here that the non-existence of a projective plane of order 10 was also proved by an exhaustive computer search .

Discretization

After multiplying rows and columns by appropriate scalars if necessary, we can assume that all coordinates of the first row and column of $A$ are 1’s, and all coordinates of the first column of all other matrices are 1’s (i.e. we assume that all vectors in the bases $A,B,C$ have first coordinate 1, and the first vector in basis $A$ is an all 1’s vector). All the other coordinates in the matrices are complex numbers of modulus 1, i.e. they are of the form $e^{2\pi i\rho}$ with $\rho\in[0,1)$. We will use a discretization approach. Let $N$ be a positive integer, called the discretization parameter. We partition the interval $[0,1)$ into $N$ sub-intervals $I_{0}^{(N)},I_{1}^{(N)},\ldots,I_{N-1}^{(N)}$ of equal length, i.e. $I_{j}^{(N)}=[j/N,(j+1)/N)$. (Other partitions are also possible, but this seems most convenient for programming.) Now, any entry $e^{2\pi i\rho}$ in any of the matrices $A,B,C$ will be represented by the integer $j$ if $\rho\in I_{j}^{(N)}$ (note that $0\leq j\leq N-1$). This means: whenever we see an entry $j$ somewhere in a matrix then we conclude that the original phase $\rho$ must lie somewhere in the interval $I_{j}^{(N)}$. We have no more and no less information than this. We also agree that the first coordinate of each row will be represented by , keeping in mind that it represents exactly 1, without error (and not the interval $I_{0}^{(N)}$).

In short: we will exclusively be dealing with row vectors of the form

There are altogether $N^{5}$ vectors of the form (1).

Also, there is a natural ordering among these vectors: $u\leq v$ if and only if it is so in lexicographical order. We will use this ordering throughout this note.

We will say that a vector $u$ of the form (1) belongs to $ORT_{N}$ if there exist $\phi_{k}\in I_{j_{k}}$ such that $1+\sum_{k=1}^{5}e^{2i\pi\phi_{k}}=0$.

This is too crude, but we can iterate it to the “children” of $u$. Namely, assume that the numbers $\phi_{k}$ exist as in Definition 3.2. For each interval $I_{j_{k}}$ the value $\phi_{k}$ must lie in either the left or the right half of $I_{j_{k}}$. There are 32 choices, according to whether we consider the left or the right half of each interval $I_{j_{k}}$. These choices are called the 32 “children” of $u$. Clearly, at least one of these children needs to satisfy (2) with $\frac{5\pi}{2N}$ on the right hand side (and its own midpoints substituted to the left hand side, of course, instead of $r_{j_{k}}$). If none of the children satisfy this, then $u$ can be discarded. Of course we iterate this to grandchildren, and so on, down to 7-8 generations. The vector $u$ survives this test if it has at least one surviving descendant in each generation.

The set $ORT_{N}$ is clearly invariant under permutations of the last 5 coordinates $j_{1},j_{2},j_{3},j_{4},j_{5}$. Therefore it makes sense to introduce the set $ORT_{N,mon}$ of vectors in $ORT_{N}$ with monotonically increasing coordinates. To save time, in the actual computer code we first find the vectors of $ORT_{N,mon}$ by the method above, and then we permute the last 5 coordinates to arrive at the set $ORT_{N}$.

There exists also an improved error bound (see Lemma 3.2 in ). It is somewhat slower to check by computer and it is reasonable to believe that we arrive at the same set $ORT_{N}$ by applying either error bounds.

We have implemented a computer code for selecting the set $ORT_{N}$. For example, for $N=17$ we have $|ORT_{N}|=58450$, for $N=19$, $|ORT_{N}|=82630$, and for $N=53$, $|ORT_{N}|=1875110$. Experience shows that the set $ORT_{N}$ is unexpectedly large if $N$ is divisible by 2 or 3. Therefore, we have mainly restricted our attention to $N$ being a prime.

The optimal choice of $N$ seems to be crucial for the success of the project. Clearly, if $N$ is too small then the error bounds are not good enough and we will not reach a contradiction in the forthcoming steps (see Section 4 below). However, if $N$ is too large then the size of the sets $ORT_{N}$ and correspondingly $HAD_{N}$ will be far too large to be manageable. At present we believe that the optimal choice of $N$ is around $N\approx 50$.

We will say that the vectors $u=(0,j_{1},j_{2},j_{3},j_{4},j_{5})$ and $v=(0,m_{1},m_{2},m_{3},m_{4},m_{5})$ are $N$-orthogonal if there exist numbers $\phi_{k}$ and $\psi_{k}$ in the intervals $I_{j_{k}}$ and $I_{m_{k}}$, such that $1+\sum_{k=1}^{5}e^{2i\pi(\phi_{k}-\psi_{k})}=0$.

This property is clearly shift-invariant in the sense that it only depends on the values $(j_{1}-m_{1},\dots j_{5}-m_{5})$ modulo $N$. We can therefore take $m_{1}=\dots=m_{5}=0$ and correspondingly $v_{0}=(0,0\ldots,0)$, (where the last 5 coordinates represent the interval $I_{0}$, of course) and define the set $ORT_{eps,N}$ as the set of vectors of the form (1) which are $N$-orthogonal to $v_{0}$. (The notation $ORT_{eps,N}$ indicates that the vector $v_{0}$ contains an “epsilon” of error, because the last 5 coordinates represent the interval $I_{0}$ and not the exact number 1.) With this notation the shift-invariance means that $u$ and $v$ will be $N$-orthogonal if and only if the vector $(j_{1}-m_{1},\dots j_{5}-m_{5})(mod\ N)$ is in $ORT_{eps,N}$.

Having constructed the set $ORT_{N}$ previously, it is now easy to obtain $ORT_{eps,N}$. Indeed, by definition a vector $u=(0,j_{1},\dots j_{5})$ can only be $N$-orthogonal to $v_{0}$ if there exist numbers $\phi_{k}$ in the intervals $I_{j_{k}}$ and $\psi_{k}$ in $[0,\frac{1}{N})$, such that $1+\sum_{k=1}^{5}e^{2i\pi(\phi_{k}-\psi_{k})}=0$. But then the numbers $\phi_{k}-\psi_{k}$ must fall in the intervals $I_{j_{k}-\epsilon_{k}}$ where $\epsilon_{k}$ is either 0 or 1, and hence the vector $u_{\epsilon}=(0,j_{1}-\epsilon_{1},\ldots,j_{5}-\epsilon_{5})$ is in $ORT_{N}$.

Therefore, $ORT_{eps,N}$ will consist of all the vectors of the form $u^{\epsilon}=(0,j_{1}+\epsilon_{1},\ldots,j_{5}+\epsilon_{5})$, where $\epsilon_{k}$ is 0 or 1, and the vector $(0,j_{1},\ldots,j_{5})$ is in $ORT_{N}.$

Each $u\in ORT_{N}$ gives rise to 32 different $u^{\epsilon}$ above. One could therefore expect that the size of $ORT_{eps,N}$ will be nearly 32 times the size of $ORT_{N}$. This is not so, however, because there will be many coincidences. Experience shows that the size of $ORT_{eps,N}$ is approximately 4 times the size of $ORT_{N}$, regardless of the value of $N$.

– each row and column must come from $ORT_{N}$.

– each row (resp. column) must be lexicographically larger than any previous rows (resp. columns). In particular, the entries of the second row and column are monotonically increasing, i.e. they belong to $ORT_{N,mon}$.

– the second column must be lexicographically larger than or equal to the second row.

– each row (resp. column) must be $N$-orthogonal to any previous rows (resp. columns). This is equivalent to the fact that the pairwise differences of the rows (resp. columns) modulo $N$ must be contained in $ORT_{eps,N}$.

– each row (resp. column) must be compatible with the already existing entries of the matrix (e.g. when we fit in the fourth row, then its first 3 coordinates are already fixed because the first three columns of the matrix have already been filled out previously).

We will say that a vector $u=(0,j_{1},j_{2},j_{3},j_{4},j_{5})$ belongs to the set $UB_{N}$ if there exist $\phi_{k}\in I_{j_{k}}$ such that $|1+\sum_{k=1}^{5}e^{2i\pi\phi_{k}}|=\sqrt{6}$. We will say that $u$ belongs to $UB_{N,mon}$ if the coordinates of $u$ are monotonically increasing.

The set $UB_{N}$ can be constructed in a similar way as $ORT_{N}$. With $r_{j_{k}}$ denoting the midpoint of the interval $I_{j_{k}}$ the trivial estimate gives

This is too crude, of course, and the descendants of $u$ need to be checked for some 7-8 generations.

Once again, the set $UB_{N}$ is invariant under the permutation of the last 5 coordinates $j_{1},j_{2},j_{3},j_{4},j_{5}$. Therefore, in practice, we first check monotonically increasing vectors only, and obtain $UB_{N,mon}$. Then we permute the coordinates to obtain $UB_{N}$.

The set $UB_{N}$ is much larger than $ORT_{N}$. This can be expected because orthogonality of complex vectors induces two conditions (the real part and imaginary part both being zero) while unbiasedness only induces one condition.

We have implemented a code for listing the set of vectors $UB_{N}$. For example, for $N=17$ we have $|UB_{N}|=479340$, while for $N=19$, $|UB_{N}|=764060$.

We will also need a set $UB_{eps,N}$ which is analogous to $ORT_{eps,N}$.

We will say that the vectors $u=(0,j_{1},j_{2},j_{3},j_{4},j_{5})$ and $v=(0,m_{1},m_{2},m_{3},m_{4},m_{5})$ are $N$-unbiased if there exist numbers $\phi_{k}$ and $\psi_{k}$ in the intervals $I_{j_{k}}$ and $I_{m_{k}}$, such that $|1+\sum_{k=1}^{5}e^{2i\pi(\phi_{k}-\psi_{k})}|=\sqrt{6}$.

This property is again shift-invariant in the sense that it only depends on the values $(j_{1}-m_{1},\dots j_{5}-m_{5})$ modulo $N$. We can therefore take $m_{1}=\dots=m_{5}=0$ and correspondingly $v_{0}=(0,0\ldots,0)$, (where the last 5 coordinates represent the interval $I_{0}$, of course) and define the set $UB_{eps,N}$ as the set of vectors of the form (1) which are $N$-unbiased to $v_{0}$. With this notation the shift-invariance means that $u$ and $v$ will be $N$-unbiased if and only if the vector $(j_{1}-m_{1},\dots j_{5}-m_{5})(mod\ N)$ is in $UB_{eps,N}$.

Finally, we remark that the entire discretization procedure described above has already been completed in in the restricted setting when $A$ is assumed to belong to the Fourier family $F(a,b)$ of complex Hadamard matrices.

[Theorem 1.4 in ] None of the pairs \bigl{(}Id,F(a,b)\bigr{)} of mutually unbiased orthonormal bases can be extended to a quartet \bigl{(}Id,F(a,b),B,C\bigr{)} of mutually unbiased orthonormal bases.

References