Mutually Unbiased Bases, ETFs, and Zauner's Conjecture (problems 22-24)

Mutually Unbiased Bases

Finite frame theory is the source of many beautiful questions. A remarkable example concerns the existence of Mutually Unbiased Bases, and object of interest in Quantum Physics (see (McNulty & Weigert, 2024) for a review).

Definition (MUB)

Two orthonormal bases $\{v_1, \dots, v_d\}, \{w_1, \dots, w_d\} \subset \mathbb{C}^d$ are called \emph{mutually unbiased} if $|\langle v_i, w_j \rangle| = 1 / \sqrt{d}$ for all $i, j$.
Let $\mathrm{MUB}(d)$ denote the largest possible number of (simultaneously) mutually unbiased bases (MUBs) in $\mathbb{C}^d$.

In (Bandyopadhyay et al., 2002) it is shown that $MUB(d)\leq d+1$ and that equality is achieved when $d$ is a prime power. For $d$ not a prime power, the problem of determining $\mathrm{MUB}(d)$ is still open. The smallest open instance is particularly well known for being a tantalizing open problem that has remained open (see Open Problem 6.2 in (Bandeira, 2016)).

Conjecture 22 ($\mathrm{MUB}(6)<7$)

Let $\mathrm{MUB}(d)$ denote the largest possible number of (simultaneously) mutually unbiased bases (MUBs) in $\mathbb{C}^d$. We have $\mathrm{MUB}(6)<7$.

It is known that $\mathrm{MUB}(6)\geq 3$ (see, e.g., (Bandeira et al., 2022)). Note that for $\mathbb{R}^d$ the existence of two mutually unbiased basis is equivalent to the existence of Hadamard Matrices, Conjeture 14 in this blog (Bandeira et al., 2025).

An interesting approach to this problem is to try to build Sum-of-Squares proofs of $\mathrm{MUB}(6)<7$. In (Bandeira et al., 2022) it was shown that a certain relaxation related to degree-2 Sum-of-Squares cannot prove that $M(6) < 7$. It is however unclear whether higher degree levels of Sum-of-Squares can provide such a proof.

Open Problem 23 (Sum-of-Squares proof of $\mathrm{MUB}(6)<7$?)

Is there a Sum-of-Squares degree 4 proof that there are no $7$ Mutually Unbiased Bases in $\mathbb{C}^6$?

Note that this is a statement about the existence, or not, of $7\times 6$ vectors $v_{i}^{(k)}\in \mathbb{C}^6$ for $i=1,\dots,6$ and $k=1,\dots,7$ satisfying \(\left| \left\langle v_{i}^{(k)},v_{j}^{(\ell)}\right\rangle \right|^2 = \left\{ \begin{array}{ccl} 1 & \text{if} & k= \ell \text{ and } i= j\\ 0 & \text{if} & k= \ell \text{ and } i\neq j\\ \frac{1}{\sqrt{6}} & \text{if} & k\neq \ell. \end{array} \right.\) These can for example be encoded with quartic relations on the real and imaginary parts of the vectors components (since $\left(v^\ast u\right)\left(u^\ast v\right) = |\langle u, v \rangle|^2$). An alternative encoding can be written by noting that the constraints for $k=\ell$ are quadratic and that, since $1/\sqrt{6}$ is the smallest possible value for the largest inner-product between vectors in different basis, one can rewrite the $k\neq \ell$ constraints as $| \langle v_{i}^{(k)},v_{j}^{(\ell)}\rangle |\leq 1/\sqrt{6}$ which are semidefinite constraints (on $2\times 2$ Hermitian matrices) involving a quadratic quantity: \(\begin{bmatrix}1/\sqrt{6} & \langle v_{i}^{(k)},v_{j}^{(\ell)}\rangle \\ \langle v_{j}^{(\ell)},v_{i}^{(k)}\rangle & 1/\sqrt{6}\end{bmatrix}\succeq 0.\)

Equiangular Tight Frames (ETFs) Another very interesting object in this field is an Equiangular Tight Frame (ETF). In $\mathbb{C}^d$ a frame is a set of spanning vectors $\phi_1,\dots,\phi_n\in \mathbb{C}^d$. A frame is called unit-normed if all vectors have unit-norm and it is called a tight frame if $\sum_{i=1}^n \phi_i\phi_i^\ast$ is a multiple of the $d\times d$ identity matrix. In general the smallest eigenvalue of this matrix is called the lower frame bound, and the largest the upper frame bound, a tight frame corresponds to a frame for which these match (see $\S$ 11 in (Bandeira, 2025)). The worst-case coherence $\mu$ of a unit-norm frame $\phi_1,\dots,\phi_n$ is given by $\mu:=\max_{i\neq j} |\langle \phi_i,\phi_j\rangle|$ (note that Mutually Unbiased Bases, described above, have worst-case coherence $1/\sqrt{d}$). Equiangular tight frames are the unit-norm frames with the smallest worst-case coherence among frames with the same size and dimension (see \S 12 in (Bandeira, 2025)).

Definition (ETF)

A frame $\phi_1,\dots,\phi_n\in \mathbb{C}^d$ is an Equiangular Tight Frame (ETF) if:
(i) It is unit-normed: $\|\phi_i\|=1$ for all $i=1,\dots,n$.
(ii) It is a tight frame: $\sum_{i=1}^n \phi_i\phi_i^\ast$ is a multiple of the $d\times d$ identity matrix.
(iii) It is equiangular: there exists $\mu\geq 0$ such that $|\langle \phi_i,\phi_j\rangle|=\mu$ for all $i\neq j$.

Note that $\mu$ needs to match the Welch bound, meaning that $\mu = \sqrt{(N-d)/(N-1)}/\sqrt{d}$.

With a tensoring argument (see \S 12 in (Bandeira, 2025)) one can show that $n\leq d^2$. ETFs in $\mathbb{C}^d$ with $n=d^2$ vectors are particularly important in Quantum Physics and are known as SIC-POVMs (Symmetric, Informationally Complete, Positive Operator-Valued Measures). It is a well known conjecture that they exist for all dimensions $d$, known as Zauner’s Conjecture (Zauner, 1999).

Conjecture 24 (Zauner's Conjecture)

For each dimension $d$, there exists an ETF in $\mathbb{C}^d$ with $n=d^2$ vectors.

There has been fascinating recent progress (Appleby et al., 2025): a proposed construction (corresponding to an orbit of the Weyl–Heisenberg group acting on $\mathbb{C}^d$) has been conditionally proven to indeed be a SIC-POVM assuming a couple of conjectures in Number Theory, examples of so-called Stark Conjectures. This shows that these conjectures imply Zauner’s Conjecture. A unconditional proof of Zauner’s Conjecture remains unavailable.

References

1. McNulty, D., & Weigert, S. (2024). Mutually Unbiased Bases in Composite Dimensions – A Review. ArXiv Preprint ArXiv:2410.23997. https://arxiv.org/abs/2410.23997
2. Bandyopadhyay, S., Boykin, P. O., Roychowdhury, V. P., & Vatan, F. (2002). A New Proof for the Existence of Mutually Unbiased Bases. Algorithmica, 34(4), 512–528. https://doi.org/10.1007/s00453-002-0980-7
3. Bandeira, A. S. (2016). Ten Lectures and Forty-Two Open Problems in the Mathematics of Data Science. https://people.math.ethz.ch/ abandeira//TenLecturesFortyTwoProblems.pdf
4. Bandeira, A. S., Doppelbauer, N., & Kunisky, D. (2022). Dual bounds for the positive definite functions approach to mutually unbiased bases. Sampling Theory, Signal Processing, and Data Analysis, 20(2), 18.
5. Bandeira, A. S., Kireeva, A., Maillard, A., & Rödder, A. (2025). Randomstrasse101: Open Problems of 2024. ArXiv Preprint ArXiv:2504.20539.
6. Bandeira, A. S. (2025). A Tour Through the Mathematics of Signals, Networks, and Learning. https://people.math.ethz.ch/ abandeira//MathofSNLnotes2025.pdf
7. Zauner, G. (1999). Quantendesigns: Grundzüge einer nichtkommutativen Designtheorie [Ph.D. thesis, Universität Wien]. https://www.gerhardzauner.at/documents/gz-quantumdesigns.pdf
8. Appleby, M., Flammia, S. T., & Kopp, G. S. (2025). A Constructive Approach to Zauner’s Conjecture via the Stark Conjectures. https://arxiv.org/abs/2501.03970