Maximal Sets of Mutually Unbiased Quantum States in Dimension Six

Introduction

The dynamics of an autonomous Hamiltonian system with a single degree of freedom differs considerably from that of a system with two or more degrees of freedom. Nontrivial interactions among the degrees of freedom usually lead to an effectively unpredictable time evolution. From a kinematical point of view, however, there is not much of a difference: the composite system simply inherits the fundamental symplectic structure of its constituents.

Schwinger associates one degree of freedom with a quantum system whenever the dimension $d$ of its Hilbert space is a prime number . Quantum systems with two or more degrees of freedom are obtained by tensoring copies of these building blocks. Our classically trained intuition wants to make us believe that the kinematics of composite quantum systems will not depend on the dimensions of the building blocks. In other words, we expect that composite quantum systems with dimensions $d_{1}=2\times 3$ and $d_{2}=3\times 3$, for example, are structurally identical.

Thus, the states form $(d+1)$ orthonormal bases, and scalar products between states taken from different bases have constant modulus. If the dimension $d$ is a prime or the power of a prime, complete sets of MU bases do exist, and it is impossible to have more than $(d+1)$ such bases. For composite dimensions $d=6,10,12,\ldots$, however, their existence poses an open problem despite many efforts reviewed in .

The purpose of this paper is to systematically search for subsets of complete sets of MU bases which we will call MU constellations. Essentially, a MU constellation consists of groups of $d$ or fewer vectors having scalar products as in (1). Three MU bases, known to exist in any dimension $d$, are a well-known example of a MU constellation. It has been conjectured that four MU bases, another MU constellation, do not exist in dimension six. The non-existence of a MU constellation consisting of three MU bases plus one additional vector, related to the Heisenberg-Weyl group, has been shown in . There are, however, many other entirely unexplored MU constellations.

We focus on MU constellations in dimension six, the smallest value for $d$ not equal to the power of a prime. We will find that many MU constellations with less than $42$ states are highly unlikely to exist. These missing MU constellations will provide the strongest numerical evidence so far that no seven MU bases exist in dimension six. Based on our findings, we will formulate a simple argument to explain the observed lack of MU constellations beyond three MU bases.

This paper is organised as follows. In the next section, we introduce the concept of MU constellations and embed them in well-defined searchable spaces. Then, in Section 3 the search for MU constellations is cast into the form of a numerical minimisation. Section 4 describes the results of the searches, and they will be discussed in the final section.

In this section we define mutually unbiased constellations of quantum states and we embed them in appropriate spaces to search for them.

The completion of $(d-1)$ orthonormal vectors into a basis is consistent with the conditions of mutual unbiasedness (1). The identity (3) implies that the state $|\psi_{\perp}\rangle$ is MU with respect to any vector $|v\rangle$ satisfying $|{\langle\psi_{j}|}{v\rangle}|=1/\sqrt{d}$, hence any MU constellation containing the states $\{|\psi_{j}\rangle\}$ remains MU if the state $|\psi_{\perp}\rangle$ is added to the set.

The ordering refers only to the number of vectors in each basis; it does not imply any relation between the subspaces spanned by the vectors in corresponding ’partial bases’ of the constellations $\{x\}_{d}$ and $\{y\}_{d}$. If (4) holds, we will say that $\{y\}_{d}$ contains $\{x\}_{d}$; alternatively, $\{x\}_{d}$ is said to be smaller than $\{y\}_{d}$. For example, the MU constellation $\{2^{2},1\}_{4}$ is contained in four MU bases $\{3^{4}\}_{4}$ because

is true. The ordering induced by (4) is only partial since constellations such as $\{3,1\}_{4}$ and $\{2^{2}\}_{4}$ cannot be compared to each other. Thus, MU constellations possess a lattice structure with a unique minimal element, $\emptyset$, and $(d+1)$ MU bases $\{(d-1)^{d+1}\}_{d}$, if existing, provide a unique maximal element.

Here is an important consequence of the lattice structure. A set of $k\in\{2,\ldots,d+1\}$ complete MU bases $\{(d-1)^{k}\}_{d}$ in dimension $d$ exists only if all smaller MU constellations $\{x\}_{d}$ exist, i.e. those with

Evidence for the non-existence of any small MU constellation is evidence for the non-existence of the corresponding complete set of MU bases. This observation is crucial for the main thrust of this paper.

2 Constellation spaces

which is a mild restriction allowing that allows considerable simplifications.

To associate an appropriate space with a given MU constellation $\{x\}_{d}$ of type (7), we will need to write it in dephased form. Once dephased, its first $(d-1)$ vectors are given by those of the standard basis ${\cal B}_{z}$, while the components of the first vector of the second basis and the first component of each remaining vector are equal to $1/\sqrt{d}$. For example, upon dephasing a MU constellation $\{2^{3},1\}_{3}$, it takes the form

with specific values for the eight angles $\alpha_{11},\ldots,\gamma_{21}$. It is shown in Appendix A that any given MU constellation of type (7) can be written in dephased form by applying transformations which leave invariant the conditions (1).

In general, each MU constellation $\{x\}_{d}$ is embedded in space ${\cal C}_{d}(x)$ of constellations $[x]_{d}$, defined in analogy to ${\cal C}_{4}(2^{3},1)$. Simply write down the dephased form of the MU constellation $\{x\}_{d}$ at hand; then, varying the angles $\alpha_{11},\dots,$ between 0 and $2\pi$, generates the space of constellations

The space ${\cal C}_{d}(x)$ has the structure of a multi-dimensional torus due to the periodicity of the angles used to parameterize it.

Let us now determine the dimension of the space ${\cal C}_{d}(x)$ associated with a MU constellation (7). It contains

is the number of states in all groups but the first one. Since each of these vectors except the first one brings $(d-1)$ phases, the entire constellation $[x]_{d}$ depends on

independent real parameters. For example, the constellation space ${\cal C}_{d}((d-1)^{d+1})$ associated with $(d+1)$ complete MU bases has dimension $(d-1)(d^{2}-d-1)$.

How many constraints does the requirement of mutual unbiasedness in (1) impose on the parameters of a constellation $[x]_{d}$? The states of a constellation are normalized, and the conditions on scalar products involving vectors of the first basis are satisfied by construction, so that there remains exactly one condition for each pair of different states taken from the last $d$ bases. Consequently, the number of constraints is given by

The number of free parameters equals the number of constraints,

whenever one considers a constellation with $s=2(d-1)$ states within the last $d$ groups. Constellations with $p_{d}=c_{d}$ will be called critical ones, denoted by $[{\bf x}]_{d}$. Constellations of type $[d-1,x_{1},\ldots,x_{{d}}]_{d}$ with more than $S=3(d-1)$ states are subjected to more constraints than they possess free parameters. These overdetermined constellations will be referred to as $[\underline{x}]_{d}$.

Numerical search for MU constellations

This section explains the numerical method we use to identify MU constellations. The basic idea is to define a continuous function on the space of constellations ${\cal C}$ that takes the value zero if and only if the input is a MU constellation. We then search for the zeros of this function in the neighborhood of a large number of randomly chosen points in ${\cal C}$, using standard numerical methods.

Suppose you want to find the MU constellation $\{x\}_{d}$. To do so, consider the associated space of constellations ${\cal C}_{d}(x)$ which can be parameterized by $p_{d}$ angles denoted by $\vec{\alpha}=(\alpha_{1},\ldots,\alpha_{p_{d}})^{T}$. Defining

equals zero if and only if the input $[x]_{d}$ coincides with a MU constellation $\{x\}_{d}$.

It is thus possible, in principle, to prove the (non-) existence of a MU constellation by determining whether the smallest value of the function $F(\vec{\alpha})$ is non-zero. This means to identify its (possibly degenerate) global minimum which, unfortunately, is not simple: the global minimisation of a nonlinear function such as a polynomial of fourth order in sufficiently many variables may already pose a NP-hard problem . A well-known strategy is to search for minima by starting from random initial points which, however, may turn out to be local ones. By repeating the process sufficiently often, one will detect global minima as well—if they exist.

A numerical search along similar lines has been reported in , restricted, however, to the MU constellations $\{5^{4}\}_{6}$ and $\{5^{7}\}_{6}$, that is, four or seven MU bases. This limitation allows for a different parametrization which exploits the fact that complete bases in dimension $d$ are associated with $d$-dimensional unitary matrices.

Note that the choice of the function $F(\vec{\alpha})$ is not unique.We have also considered an everywhere differentiable variant of (28) obtained by subtracting the square of $\chi_{jj^{\prime}}^{bb^{\prime}}$ from $|{\langle\psi_{j}^{b}|}{\psi_{j^{\prime}}^{b^{\prime}}\rangle}|^{2}$. We noticed, however, that the success rate to find existing MU constellations is systematically lower. The expression (28) is convenient because efficient minimisation tools are available for a sum of squares. In particular, the Levenberg-Marquardt algorithm , often used in Regressional Analysis, cleverly switches between the method of steepest descent and the Gauss-Newton algorithm to speed up convergence. To search for zeros of the function $F(\vec{\alpha})$, we use the function optimize.leastsq from the Open-Source Python package SciPy which implements the LM-algorithm.

The function $F(\vec{\alpha})$ achieves its maximum

if all states coincide, each having components equal to $1/\sqrt{d}$ only. For typical constellations such as $\{5^{2},4,1\}_{6}$ or $\{5,3^{3}\}_{6}$, one finds $F_{\mbox{\tiny max}}=33.2$ and $F_{\mbox{\tiny max}}=25.0$, respectively. The top image of Fig. 1 shows a two-dimensional contour plot of $F(\vec{\alpha})$ in the 45-dimensional constellation space ${\cal C}_{6}(5,4^{2},2)$. Ranging between 2.6 and 3.6, the function $F(\vec{\alpha})$ exhibits one maximum, one minimum, and two saddle points. This structure is consistent with (28) because $F(\vec{\alpha})$ reduces to a simple trigonometric polynomial of two variables if all but the first two angles $\alpha_{1}\equiv u,\alpha_{2}\equiv v$, are fixed.

Considering the range of the function $F$, it appears reasonable to say that a MU constellation $[x]_{d}$ parameterized by $\vec{\alpha}$ has been found if $F(\vec{\alpha})$ assumes a value below

This criterion, stronger than the one used in is entirely arbitrary, and smaller values could be used at the expense of computational time. The numerical data presented below will retrospectively justify the chosen value of the threshold for zeros of F.

2 Testing the numerical search

We begin by presenting searches for MU constellations which are known to exist. The data provide evidence that the numerical minimization of $F(\vec{\alpha})$ defined in Eq. (28) is a reliable tool to identify MU constellations.

The searches are successful in all dimensions. The rate of success systematically decreases for larger dimensions if even and odd dimensions are considered separately. This overall trend is not surprising in view of the constant number of samples taken in ever bigger spaces ${\cal C}_{d}$. The success rate is consistently higher in even dimensions which might be attributed to the possibility of constructing different types of triples of MU bases resulting from the factor of two in $d=4,6,8$.

2.2 MU constellations in dimension five

Next, we test the minimisation procedure by systematically searching for MU constellations of the form $\{4,x,y,z\}_{5}$, i.e. all MU constellations in dimension $d=5$ contained in four MU bases. The results from 1,000 searches for each MU constellation have been collected in Table 2. The success rate gradually decreases from 100% for MU constellations with 16 or fewer parameters to 10% for MU constellations with 44 parameters. All MU constellations are identified. In view of later developments the table also makes explicit the number of free parameters for each dephased constellation.

To judge the quality of the minimisation procedure, it is instructive to plot the distribution of the minimal values of $F(\vec{\alpha})$ obtained in the space ${\cal C}_{5}(4^{3},2)$, say. The histogram at the top of Fig. 2 shows that global minima, defined by $F<10^{-7}$, are separated from local minima by several orders of magnitude, justifying the criterion (30). For a random sample of these ’zeros,’ we have been able to reduce the value of $F(\vec{\alpha})$ to less than $10^{-20}$, simply by running the search for longer.

Note that by detecting one MU constellation in a particular run, all MU constellations contained in it have also been found. Thus, Table 2 does not only report 370 incidences of the MU constellation $\{4^{2},2^{2}\}_{5}$ but since MU constellations form a lattice due to (4), all successful searches to the right and below this entry also confirm its presence, adding a further 983 detected cases.

The bottom image of Fig. 1 plots the contours of the function $F(\vec{\alpha})$ in a two-dimensional neighbourhood of a zero, i.e. of a MU constellation of type $\{4^{3},2\}_{5}$. Qualitatively, it resembles the random cross-section depicted above it.

2.3 MU constellations in dimension seven

In dimension seven, a complete set of eight MU bases exists. Thus, we expect a numerical search to successfully identify all MU constellations with no more than four partial bases. The largest constellation, $\{6^{4}\}_{7}$, now depends on 102 parameters, more than double the number occurring in dimension five. Due to this substantial expansion of the parameter space, however, the search for zeros of the function $F(\vec{\alpha})$ is likely to succeed less frequently.

These expectations are confirmed by the results collected in Table 3. As in dimension five, the success rates decreases if MU constellations containing more states are being searched for. Although the spaces searched are considerably larger, we still find four out of five MU constellations of the form $\{6,x,y,z\}_{7}$ after 1,000 attempts. Overall, the success rates show a structure different from the one observed in dimension five: the high detection rate for small MU constellations drops sharply when the constellations approach any of the critical constellations $\{{\bf x}\}_{7}$. Importantly, all but one of the overdetermined MU constellations $\{\underline{x}\}_{7}$ beyond the ‘line’ of critical MU constellations have been identified. It is true that the success rate is small but the basin of attraction for global minima is likely to be only a tiny region in the high-dimensional search space.

The quality of the zeros is excellent: they correspond to values of $F(\vec{\alpha})$ below $10^{-12}$, being clearly different from the vast majority of local minima producing values in the order of $10^{-3}$. This is illustrated in the upper histogram of Fig. 3 which combines all the minima obtained for overdetermined constellations $\{\underline{x}\}_{7}$. We associate the clusters of values at $10^{-13}$ and at $10^{-3}$ with global and local minima, respectively.

It is straightforward to check that the numerically identified MU constellations reproduce the numbers $\chi_{jj^{\prime}}^{bb^{\prime}}$ in (27), correct to seven significant digits. We are thus confident to have identified these overdetermined MU constellations in dimension seven.

MU constellations in dimension six

Knowing that the numerical procedure to minimise $F(\vec{\alpha})$ defined in (28) generates reliable data, we now turn to the main findings of this paper which are related to dimension six.

In Table 4, we present the success rates to identify all MU constellations contained in four MU bases $\{5^{4}\}_{6}$, i.e.

We will proceed as in dimensions $d=5$ and $d=7$ but, in order to give our results additional weight, we have performed 10,000 searches for each MU constellation.

The results exhibit a structure which differs qualitatively from the findings in neighboring dimensions. The success rates decrease as before if the search aims at MU constellations with increasing numbers of free parameters. However, after dropping to zero on the line of critical constellations $\{{\bf x}\}_{6}$, there is no evidence for a single overdetermined MU constellation $\{\underline{x}\}_{6}$.

It is true that only a few of these MU constellations had been identified in dimension seven; considering their abundance in $d=5$, however, their complete absence in $d=6$ is a striking feature which we consider to be statistically relevant. Note that the lattice structure due to (4) allows us to conclude that unsuccessful searches for MU constellations contained in $\{5^{4}\}_{6}$ also count against its existence. Since none of the constellations it contains have been found, Table 4 effectively reports a total of 170,000 negative instances for the MU constellation $\{5^{4}\}_{6}$.

The minimal values of $F(\vec{\alpha})$ obtained for most of the constellations on and near the critical line are not below $1.1\times 10^{-4}$ except for $\{5,4,3,2\}_{6},\{5,4^{2},2\}_{6}$, and $\{5,3^{3}\}_{6}$, where values close to $10^{-6}$ have been obtained. We have not been able to push the these values below the threshold of $10^{-7}$, even by running the search considerably longer. The bottom histogram Fig. 2 shows that the minima obtained for $\{5,4^{2},2\}_{6}$ cluster at values of $10^{-3}$, orders of magnitude away from the criterion (30) for a global minimum. The second histogram in Fig. 3 combines the results for all overdetermined constellations $\{\underline{x}\}_{6}$, showing that throughout the minimal values found are well above the threshold of $10^{-7}$.

As an aside, the absence of the MU constellation $\{5^{2},4,1\}_{6}$ from Table 4 suggests, by the inclusion $\{5^{3},1\}_{6}$ $\geq$ $\{5^{2},4,1\}_{6}$, that no three complete MU bases plus one additional mutually unbiased state exist. This result generalizes the impossibility to extend two MU bases $\{5^{2}\}_{6}$ related to the Heisenberg-Weyl group to a MU constellation $\{5^{3},1\}_{6}$ .

Summary and Discussion

The results of the searches performed in dimension six provide strong evidence that not all MU constellations of the form $\{5,x,y,z\}_{6}$ exist. Here are our main conclusions drawn from Table 4:

the largest existing MU constellations are $\{5,4^{2},1\}_{6}$ and $\{5^{2},3,1\}_{6}$ both containing 15 ($\equiv S+1$) mutually unbiased states;

the smallest non-existing MU constellations are $\{5,3^{3}\}_{6}$ and $\{5,4,3,2\}_{6}$ each consisting of 14 ($\equiv S$) states;

only one critical MU constellation $\{{\bf x}\}_{6}$ exists, namely $\{5^{3}\}_{6}$ corresponding to three MU bases with 18 states;

no overdetermined MU constellation $\{\underline{x}\}_{6}$ exists.

We have been able to positively identify 18 out of 35 MU constellations in dimension six. On the basis of the numerical data, we consider it highly unlikely that the 15 unobserved critical and overdetermined MU constellations do exist, making the existence of four MU bases exceedingly improbable.

Let us discuss these results in a general framework. Critical constellations $[{\bf x}]_{d}$ have been defined by the equality $p_{d}=c_{d}$. If $p_{d}$ parameters need to satisfy $c_{d}\equiv p_{d}$ equations, one would expect some isolated solutions to exist in a generic situation. As three MU bases are critical constellations in any dimension $d$, they are expected to exist generically. In the overdetermined case, there are more constraints than free parameters, $c_{d}>p_{d}$, and no MU constellations are expected. This observation agrees with the fact that one can actually construct three MU bases without referring to the decomposition of $d$ into its prime factors.

The implications of counting parameters apply not only to $d=2$ where precisely three MU bases exist but they also agree with the data in Table 4: not a single overdetermined MU constellation of the form $\{5,x,y,z\}_{6}$ has been observed. Thus, it is natural to suspect that all overdetermined MU constellations $\{\underline{x}\}$ will be missing in dimension six. More generally, suppose it is the smallest prime in the decomposition of $d$ that limits the number of MU bases. Then, for dimensions that contain only a single factor of two, we also expect that no overdetermined MU constellations $\{\underline{x}\}_{2d}$ exist. For example, we consider it unlikely in dimension ten to find MU constellations of the form $\{9,x,y,z\}_{10}$ with $x+y+z=18$.

Discussions with the participants of the Quantum Information Seminar at the Department of Mathematics at the University of York are gratefully acknowledged, and with Tony Sudbery in particular. We would also like to thank Subhash Chaturvedi for asking if seven mutually unbiased states exist in dimension six (they do, as does the MU constellation $\{2^{7}\}_{6}$).

References

Appendix A Equivalence classes of MU constellations

Two complete sets of MU bases $\{{\cal B}_{0},\ldots,{\cal B}_{d}\}$ and $\{{\cal B}_{0}^{\prime},\ldots,{\cal B}_{d}^{\prime}\}$ are said to be equivalent,

if we can obtain one from the other by a succession of the following four transformations:

which leaves invariant the value of all scalar products;

$(d+1)$ simultaneous unitary transformations $D_{b}$ which multiply each vector with a phase factor,

exploiting the fact that the physically irrelevant overall phase of a quantum state drops out of the conditions (1);

$(d+1)$ simultaneous permutations $P_{b}$ of the members within each basis,

which amounts to relabeling the elements of each basis.

For simplicity, we have written $U{\cal B}_{b}\equiv\{U|\psi_{1}^{b}\rangle,\ldots,U|\psi_{d}^{b}\rangle\}$, that is, the unitary $U$ acts on each member of the basis ${\cal B}_{b}$; the expressions ${\cal B}_{b}D_{b}$ etc. are defined similarly.

These equivalence relations can be used to dephase a given complete set of MU bases $\{{\cal B}_{0},\ldots,{\cal B}_{d}\}$. Written in dephased form, its first basis is given by the standard basis ${\cal B}_{z}$, the components of the first vector of the second basis are equal to $1/\sqrt{d}$, as are the first components of the remaining $(d-1)(d+1)$ vectors. Let us illustrate the dephasing in dimension $d=3$ where a given complete set of four MU bases can be brought into the form

The three orthonormal states of each basis have been arranged into four unitary matrices. The second unitary matrix obtained here is (proportional to) a dephased complex Hadamard matrix motivating our terminology. Note that the vectors of the last three bases (except for $(1,1,1)^{T}/\sqrt{3}$) may be rearranged using (36).

Figures

Tables