In this post, we’ll explore an interesting connection between finite affine planes, a well-studied class of combinatorial designs, and mutually unbiased bases, linear algebraic objects which play an important role in quantum information theory. In particular, we’ll see how both can be described by a common framework through which we can derive shared properties and proofs. What follows is based off of joint work with Mihály Weiner and Zsombor Szilágyi from my year in Budapest (see our pre-print on arXiv for more details and results).
Mutually Unbiased Bases
Mutually unbiased bases (MUBs) are motivated by simple quantum measurement procedures. Don’t worry if you’re not familiar with quantum mechanics – we’ll only need some basic linear algebra. To start, a pure quantum state is represented by a complex unit vector \(\psi \in \mathbb{C}^d\), for some dimension \(d\). For each orthonormal basis \(\mathcal{B}= \{ b_1, \dots, b_d \} \in \mathbb{C}^d\), there exists a quantum measurement probing with respect to that basis, such that \[ \Pr[\psi \text{ observed in state } b_i \text{ after measurement w.r.t. } \mathcal{B}] = | \langle \psi | b_i \rangle |^2, \] where \(\langle \cdot | \cdot \rangle\) denotes the standard inner product (conjugate-linear in the first argument and linear in the second1). If this quantity is constant for all \(i\), then \[\begin{align*} | \langle \psi | b_1 \rangle |^2 = \dots = | \langle \psi | b_d \rangle |^2 &= \frac{1}{d} \sum_{j = 1}^d | \langle \psi| b_j \rangle |^2\\ &= \frac{1}{d} \bigg\langle \psi \,\Bigg| \sum_{j = 1}^d \langle \psi | b_j \rangle b_j \bigg\rangle\\ &= \frac{1}{d} \langle \psi | \psi \rangle = \frac{1}{d}, \end{align*}\] where the second to last inequality follows because \(\mathcal{B}\) is orthonormal. In this case, measurement with respect to \(\mathcal{B}\) reveals no information about \(\psi\). Mutual unbiasedness extends this notion to describe a relationship between different bases.
Definition (Mutually Unbiased Bases)
We say that orthonormal bases \(\mathcal{E} = \{ e_1, \dots, e_d \}\) and \(\mathcal{F} = \{ f_1, \dots, f_d \}\) for \(\mathbb{C}^d\) are mutually unbiased if \[ | \langle e_i | f_j \rangle |^2 = \frac{1}{d} \] for all \(i,j = 1, \dots, d\). Naturally, a collection of bases for \(\mathbb{C}^d\) are called mutually unbiased if they are pairwise mutually unbiased.
That is, if we prepare a state from one basis and perform a measurement with respect to the other, all outcomes are equally likely. MUBs arise naturally in several quantum information protocols for key distribution, error correction, and more.
Example
Here is a diagram of two MUBs in \(\mathbb{C}^2\) with no complex components.
2 MUBs in C2
These correspond to, say, \[ \color{#5b9bd5}{\mathcal{B}_1} = \left\{ \begin{pmatrix} 0 \\ 1 \end{pmatrix}, \begin{pmatrix} 1 \\ 0 \end{pmatrix} \right\} \quad \text{and} \quad \color{#ed7d31}{\mathcal{B}_2} = \left\{ \frac{1}{\sqrt{2}} \begin{pmatrix} 1 \\ 1 \end{pmatrix}, \frac{1}{\sqrt{2}} \begin{pmatrix} -1 \\ 1 \end{pmatrix} \right\}. \] If we allow complex components, \[ \mathcal{B}_3 = \left\{ \frac{1}{\sqrt{2}} \begin{pmatrix} 1 \\ i \end{pmatrix}, \frac{1}{\sqrt{2}} \begin{pmatrix} -1 \\ i \end{pmatrix} \right\} \] can be added as a third mutually unbiased basis2.
This example raises a natural question: for a fixed dimension \(d\), what is the maximum number of MUBs in \(\mathbb{C}^d\)? Denoting this count by \(\mathfrak{M}_1(d)\) (the reason for the subscript will be revealed soon), it is relatively straightforward to prove that \(\mathfrak{M}_1(d) \leq d + 1\). Hence, collections of \(d+1\) MUBs in \(\mathbb{C}^d\) are said to be complete. The following is conjectured.
Conjecture (Existence of Complete MUBs)
\(\mathfrak{M}_1(d) = d + 1\) if and only if \(d\) is a prime power.
Even the case of \(d = 6\) is unresolved, and this remains a primary open problem in quantum information theory. Personally, I find it quite interesting that such a condition might arise in this geometric setting.
Combinatorial \(k\)-Nets
Next, we’ll consider a class of combinatorial designs called \(k\)-nets, of which affine planes are a special case. We begin with a base set of \(d^2\) points. Each subset of \(d\) points is called a line, and a partition of the points into \(d\) disjoint lines is called a parallel class. Then, we define the following.
Definition (Combinatorial \(k\)-Net)
Two parallel classes of lines on \(d^2\) points \[ \mathcal{P} = \{ p_1, \dots, p_d \}, \quad \mathcal{Q} = \{ q_1, \dots, q_d \} \] are called mutually unbiased if \[ |p_i \cap q_j| = 1 \] for \(i,j = 1,\dots,d\). A system of \(k\) mutually unbiased parallel classes on \(d^2\) points is called a combinatorial \(k\)-net of order \(d\).
These definitions are slightly non-standard3, but I wanted to emphasize a connection to MUBs which will be detailed soon.
Example
Below is a \(2\)-net of order 2 and its extension to a 3-net.
2- and 3-nets of order 2
As before, this raises a question: for a fixed order \(d\), what is the maximum \(k\) for which a \(k\)-net of order \(d\) exists? Denoting this count by \(\mathfrak{M}_2(d)\), a simple counting argument reveals that \(\mathfrak{M}_2(d) \leq d + 1\). Complete \(k\)-nets of order \(d+1\) are called affine planes and have many applications in finite geometry and coding theory. Again, we have an existence conjecture.
Conjecture (Existence of Affine Planes)
\(\mathfrak{M}_2(d) = d + 1\) if and only if \(d\) is a prime power.
A bit more progress has been made towards this hypothesis; by the Bruck-Ryser-Chowla Theorem, we know that affine planes of order \(d\) cannot exist if \(d \equiv 1 \text{ or } 2 \pmod{4}\) and is not the sum of two squares (e.g. \(d=6\) is forbidden).
A Common Framework
As these similar definitions and conjectures suggest, researchers have discovered many connections between affine planes and complete collections of MUBs (although it’s not clear that these similarities are sufficient to translate existence results)4. In our paper, we introduce a common framework so that we can work with MUBs and \(k\)-nets simultaneously, the basis for which is a finite dimensional \(C^*\)-algebra. First, we recall the following.
Definition (*-Algebra)
A complex *-algebra is a vector space over \(\mathbb{C}\) equipped with an associative, bilinear product (written as multiplication) and a conjugate-linear anti-automorphic involution (written as \(x \mapsto x^*\)).
The canonical example of a *-algebra is the field of complex numbers \(\mathbb{C}\) under standard multiplication and conjugation. The details of the definition aren’t so important, as we will soon focus on two concrete cases.
A \(C^*\)-algebra is a *-algebra equipped with a norm obeying certain properties, but we will only use the following.
Proposition
Every finite-dimensional \(C^*\)-algebra is isomorphic to a \(*\)-subalgebra of the set \(M_d(\mathbb{C})\) of complex \(d \times d\) matrices, for some dimension \(d\), and all such isomorphisms are unitarily equivalent.
Remark
Hence, each finite-dimensional \(C^*\)-algebra \(\mathfrak{U}\) admits a unique identity element \(I\) such that \(AI = IA = A\) for all \(A \in \mathfrak{U}\). Furthermore, \(\mathfrak{U}\) can be equipped with a canonical normalized trace \(\tau\) by taking the standard matrix trace \(\operatorname{tr}\) and dividing by \(\operatorname{tr}(I)\) so that \(\tau(I) = 1\).
More details are provided on the Wikipedia page. Now, let’s get to the relevant examples.
Example
- \(M_d(\mathbb{C})\) under matrix multiplication and taking adjoints (e.g. \(\mathbb{C}\cong M_1(\mathbb{C})\))
- for \(A \in M_d(\mathbb{C})\), \(\tau(A) = \frac{1}{d}\operatorname{tr}(A)\)
- this is a non-commutative algebra for \(d > 1\)
- \(\mathbb{C}^X\), the space of complex functions on a finite set \(X\), under pointwise multiplication and conjugation
- for \(f \in \mathbb{C}^X\), \(\tau(f) = \frac{1}{d^2}\sum_{x \in X} f(x)\)
- this is a commutative algebra isomorphic to the algebra of diagonal matrices in \(M_{|X|^2}(\mathbb{C})\)
Next, we recall a final definition.
Definition (Orthogonal Projection)
An element \(P\) of a \(C^*\)-algebra is called an orthogonal projection if \(P^2 = P^* = P\).
This translates cleanly into our two settings.
Example
- For each subspace \(V \subseteq \mathbb{C}^d\), there is an orthogonal projection of \(M_d(\mathbb{C})\) mapping each vector in \(\mathbb{C}^d\) to its nearest point in \(V\) under the Euclidean metric. All orthogonal projections of \(M_d(\mathbb{C})\) are of this form.
- Each orthogonal projection of \(\mathbb{C}^X\) is an indicator function \(1_S\) for a set \(S \subseteq X\), where \(1_S(x) = 1\) if \(x \in S\) and \(0\) otherwise.
Finally, we are prepared to introduce our common framework. Let \(\mathfrak{U}\) be a \(d^2\)-dimensional \(C^*\)-algebra with canonical normalized trace \(\tau\). As I’ve hinted at so far, \(\mathfrak{U}= M_d(\mathbb{C})\) will correspond to the case of MUBs, and \(\mathfrak{U}= \mathbb{C}^X\) will correspond to combinatorial \(k\)-nets with point set \(X\). For a fixed order \(d\), we construct our generalization using a collection of familiar components. The first component is a (generalized) line, defined to be an orthogonal projection \(P = P^* = P^2 \in \mathfrak{U}\) with \(\tau(P) = \frac{1}{d}\).
Example
- Each basis vector \(e\) of a MUB corresponds to the line given by the rank-one orthogonal projection of \(M_d(\mathbb{C})\) onto its span given by \(P_e(v) = e \langle e | v \rangle\). This is often expressed in bra-ket notation as \(P_e = | e \rangle \langle e |\). Indeed, \(\tau(P_e) = \frac{1}{d}\operatorname{tr}(| e \rangle \langle e |)= \frac{1}{d} \langle e | e \rangle = \frac{1}{d}\).
- Each classical line \(p\) of a combinatorial \(k\)-net of order \(d\) with point set \(X\) corresponds to the line given by the indicator function \(1_p \in \mathbb{C}^X\) supported on \(p\). Indeed, \(\tau(1_p) = \frac{1}{d^2} \sum_{x \in X} 1_p(x) = \frac{d}{d^2} = \frac{1}{d}\).
Next, we define a parallel class to be a set of lines \(\mathcal{C} = P_1, \dots, P_d\) with \(P_iP_j = 0\) for \(i \neq j\).
Example
- Each orthonormal basis \(\{ b_1, \dots, b_d\}\) of a MUB corresponds to the parallel class of lines in \(M_d(\mathbb{C})\) corresponding to its basis vectors, i.e. \(\{ | b_1 \rangle \langle b_1 |, \dots, | b_d \rangle \langle b_d |\}\). Indeed, if \(i \neq j\), then \(P_{b_i}P_{b_j} = | b_i \rangle \langle b_i | b_j \rangle \langle b_j | = 0\).
- Each classical parallel class \(\{p_1, \dots, p_d\}\) of a combinatorial \(k\)-net corresponds to the parallel class of lines in \(\mathbb{C}^X\) given by \(\{ 1_{p_1}, \dots, 1_{p_d} \}\). Indeed, if \(i \neq j\), then \(1_{p_i} 1_{p_j} = 1_{p_i \cap p_j} = 1_{\emptyset} = 0\).
Then, we say that two parallel classes \(\mathcal{C}_1, \mathcal{C}_2\) are mutually unbiased if, for each \(P \in \mathcal{C}_1\) and \(Q \in \mathcal{C}_2\), \(\tau(PQ) = \frac{1}{d^2}\).
Example
- The parallel classes corresponding to MUBs \(\{ e_1, \dots, e_d \}\) and \(\{ f_1, \dots, f_d \}\) are mutually unbiased. Indeed, \(\tau(P_{e_i}P_{f_j}) = \tau(| e_i \rangle \langle e_i | f_j \rangle \langle f_j |) = \frac{1}{d} |\langle e_i | f_j \rangle|^2 = \frac{1}{d^2}\).
- The parallel classes corresponding to mutually unbiased parallel classes \(\{p_1, \dots, p_d\}\) and \(\{q_1, \dots, q_d\}\) of a combinatorial \(k\)-net are mutually unbiased (they’d better be with a name like that). Indeed, \(\tau(1_{p_i}1_{q_j}) = \tau(1_{p_i \cap q_j}) = \frac{1}{d^2} \sum_{x \in X} 1_{p_i \cap q_j}(x) = \frac{1}{d^2}\).
Finally, our full generalization is just a collection of mutually unbiased parallel classes.
Definition (\(k\)-Net over an algebra)
Let \(\mathfrak{U}\) be a \(d^2\)-dimensional \(C^*\)-algebra with canonical normalized trace \(\tau\). We say that a collection of orthogonal projections \(\mathcal{N} \subset \mathfrak{U}\) is a (generalized) \(k\)-net of order \(d\) over \(\mathfrak{U}\) if it is the union of \(k\) mutually unbiased parallel classes.
By our previous examples, it’s clear that systems of MUBs and combinatorial \(k\)-nets can both be realized in this new setting, and it’s not difficult to show that all generalized \(k\)-nets over \(M_d(\mathbb{C})\) and \(\mathbb{C}^X\), \(|X|=d^2\), are of this form5. Below, we summarize these correspondences.
| System of \(k\) MUBs in \(\mathbb{C}^d\) | Classical \(k\)-net of order \(d\) | |
|---|---|---|
| \(k\)-net over … | \(M_d(\mathbb{C})\) | \(\mathbb{C}^X\), \(|X|=d^2\) |
| line | basis vector | classical line |
| parallel class | orthonormal basis | classical parallel class |
| mutual unbiasedness | \(|\langle e_i | f_j \rangle|^2 =\) const | \(|p_i \cap q_j| =\) const |
This convention is standard in physics and quantum information but often reversed in mathematics.↩
You might recognize these three bases as the eigenvectors of the Pauli matrices. Pauli matrices have higher-dimensional generalizations which can also be used to generate MUBs, as we do in the final section of our paper.↩
Mutual unbiasedness is not standard terminology in finite geometry. Also, lines are usually not restricted to \(d\) points, though this is forced for the lines of a \(k\)-net when \(k \geq 3\).↩
See, for example, the section on affine planes of this survey.↩
I’m not aware of \(k\)-nets over any other algebras, though I haven’t disproved their existence.↩
R. H. Bruck. “Finite nets. II. Uniqueness and imbedding.”↩