MUBs from bent functions

This paper presents a simple construction of complete sets of mutually unbiased bases (MUBs) by utilizing bent functions to express the new basis vectors as explicit linear combinations of the standard basis.

The Gist

Imagine you are trying to organize a massive library of information, but you need to do it in a way that ensures no two ways of organizing the books ever look the same, yet they all fit together perfectly. This is the core challenge of Mutually Unbiased Bases (MUBs), a concept used in quantum physics and mathematics.

In this paper, mathematician William M. Kantor presents a new, simple "recipe" for creating these perfect organizational systems. He does this by using a special type of mathematical function called a bent function.

Here is a breakdown of his ideas using everyday analogies:

1. The Goal: The Perfect Shuffle

Think of a deck of cards. You can organize them by Suit (Hearts, Diamonds, etc.) or by Rank (Ace, 2, 3, etc.).

• If you know a card is the "Ace of Hearts," you know exactly where it is in the "Suit" list.
• But if you look at the "Rank" list, knowing it's an "Ace" tells you nothing about which suit it belongs to; it could be any of the four.

In the quantum world, scientists want to create many different "lists" (bases) where knowing the position of an item in one list gives you zero information about its position in any other list. They want to create as many of these totally different lists as possible. Kantor calls a "complete set" of these lists a Complete Set of MUBs.

2. The Secret Ingredient: Bent Functions

To build these lists, Kantor uses "bent functions."

• The Analogy: Imagine a function is a machine that takes an input (like a number) and spits out a result. A "bent" function is a machine that is perfectly "twisted" or "bent."
• The Property: If you change the input just a tiny bit, the output changes in a way that is completely unpredictable and evenly distributed. It's like a fair coin toss that never gets stuck on "heads" or "tails" no matter how many times you flip it.
• The "Mubent" Set: Kantor needs a whole team of these bent functions. The rule is that if you take any two functions from the team and subtract one from the other, the result must also be a perfectly bent function. He calls this a "mubent set."

3. The Construction: Two Different Recipes

Kantor shows how to use these teams of functions to build the lists, but he has to use two slightly different recipes depending on the size of the system (specifically, whether the number of items is an odd prime number or a power of 2).

Recipe A: For Odd Numbers (The "Odd Characteristic" Case)

• The Setup: Imagine you have a grid of points. You have a standard list (the "standard basis").
• The Magic: For every bent function in your "mubent set," you create a new list. You do this by taking the standard list and mixing the items together using a specific formula involving the bent function.
• The Result: Kantor proves mathematically that if you start with your standard list and add all the new lists created by your bent functions, you get a complete set. Every list is perfectly "unbiased" against every other list.
• The Catch: This recipe works great for odd numbers, but it breaks down if you try to use it for the number 2 (powers of 2).

Recipe B: For Powers of 2 (The "Characteristic 2" Case)

• The Problem: The first recipe fails for powers of 2 because the "bent" functions don't behave the same way.
• The Fix: Kantor changes the rules slightly. Instead of using numbers from a simple list (0, 1, 2...), he uses numbers from a "modulo 4" system (0, 1, 2, 3).
• The New Bent Definition: In this system, a function is "bent" if the differences between its outputs are distributed in a very specific, balanced way (equal numbers of 0s and 2s, and equal numbers of 1s and 3s).
• The Result: Using this modified definition and a special type of matrix (a grid of numbers) called a "spread set," he builds the new lists. Just like the first recipe, this creates a complete set of perfectly unbiased lists.

4. Why This Matters (According to the Paper)

• Simplicity: Previous methods for building these sets often relied on complex group theory or geometry. Kantor's method is "elementary" and direct: it writes the new lists as simple combinations of the old ones.
• Completeness: He proves that these methods generate the maximum number of possible lists (N + 1 lists for a system of size N).
• Limitations: The paper notes that while this construction is simple, it mostly uses "quadratic" functions (a specific, simple type of bent function). It doesn't solve the mystery of whether there are other, stranger types of bent functions that could create even more unique sets, but it provides a solid, working foundation.

Summary

Kantor's paper is like a cookbook. He says: "If you want to create a perfect set of totally different ways to organize a quantum system, here is a simple recipe.

1. Gather a team of 'bent' functions (functions that are perfectly twisted).
2. If your system is an odd number, use Recipe A.
3. If your system is a power of 2, use Recipe B (which requires a slightly different kind of bent function).
4. Mix them with your standard list, and you get a complete, perfect set of unbiased bases."

The paper is a mathematical proof that this recipe always works, providing a clear and explicit way to generate these complex structures.

Technical Summary

Technical Summary: MUBs from Bent Functions

Problem Statement
The paper addresses the construction of complete sets of Mutually Unbiased Bases (MUBs) in the complex vector space $\mathbb{C}^N$, where $N = p^n$ for a prime $p$. Two orthonormal bases are mutually unbiased if the magnitude of the inner product between any vector from one basis and any vector from the other is exactly $1/\sqrt{N}$. A complete set consists of $N+1$ such pairwise unbiased bases. While group-theoretic and geometric approaches to this problem exist (referenced as [WoF, Wo, CCKS, Ka]), this note aims to provide a distinct, elementary construction that explicitly expresses the new basis vectors as linear combinations of the standard basis using bent functions.

Methodology
The author, William M. Kantor, proposes a unified construction based on "mubent" sets of functions. The methodology differs based on the characteristic of the field:

1. Odd Characteristic ($p > 2$):

   • Let $V = \mathbb{Z}_p^n$. A mubent set $\mathfrak{B}$ is defined as a set of $|V|$ functions $V \to \mathbb{Z}_p$ such that the difference between any two distinct functions in the set is a bent function.
   • A function $B: V \to \mathbb{Z}_p$ is bent if, for any non-zero $u \in V$, the difference function $v \mapsto B(v+u) - B(v)$ takes every value in $\mathbb{Z}_p$ exactly $|V|/p$ times.
   • The construction defines a standard basis $M_\infty = \{e_a \mid a \in V\}$ and a family of bases $M_B = \{ \frac{1}{\sqrt{N}} e_{a,B} \mid a \in V \}$ for each $B \in \mathfrak{B}$.
   • The vectors $e_{a,B}$ are constructed as explicit linear combinations: $e_{a,B} = \sum_{v \in V} \zeta^{a \cdot v + B(v)} e_v$, where $\zeta$ is a primitive $p$-th root of unity.

2. Characteristic 2 ($p = 2$):

   • The construction is adapted to use functions $V \to \mathbb{Z}_4$ rather than $\mathbb{Z}_2$, as the standard definition of bent functions over $\mathbb{Z}_2$ does not yield complete sets of size $N+1$ (the maximum size is limited to $2^{n-1} + 1$).
   • Here, a mubent set $\mathfrak{B}$ consists of $|V|$ functions $V \to \mathbb{Z}_4$ such that the difference of any two is a bent function $V \to \mathbb{Z}_4$.
   • A function $B: V \to \mathbb{Z}_4$ is bent if, for $0 \neq u \in V$, the counts $n(u, k) = |\{v \in V \mid B(v+u) - B(v) = k\}|$ satisfy $n(u, 0) = n(u, 2)$ and $n(u, 1) = n(u, 3)$.
   • The basis vectors are defined similarly using $i$ (the imaginary unit) as the root of unity: $e_{a,B} = \sum_{v \in V} (-1)^{a \cdot v} i^{B(v)} e_v$.

Key Results and Theorems
The paper establishes two primary theorems proving the validity of this construction:

• Theorem 2.1 (Odd Characteristic): If $\mathfrak{B}$ is a mubent set of functions $V \to \mathbb{Z}_p$, then the collection $\{M_\infty\} \cup \{M_B \mid B \in \mathfrak{B}\}$ forms a complete set of MUBs in $\mathbb{C}^N$. The proof relies on calculating the inner product magnitude squared, showing it equals $1/N$ for distinct bases by utilizing the distribution properties of bent functions.
• Theorem 3.1 (Characteristic 2): If $\mathfrak{B}$ is a mubent set of functions $V \to \mathbb{Z}_4$, then $\{M_\infty\} \cup \{M_B \mid B \in \mathfrak{B}\}$ forms a complete set of MUBs in $\mathbb{C}^N$. The proof similarly demonstrates that the cross-correlation terms vanish due to the specific balance conditions ($n(u,0)=n(u,2)$ and $n(u,1)=n(u,3)$) inherent to bent functions over $\mathbb{Z}_4$.

Concrete Constructions and Examples
The paper provides specific instances of mubent sets to demonstrate the existence of such constructions:

• Quadratic Functions: For odd $p$, the simplest examples use the trace map and quadratic functions of the form $x \mapsto \text{Tr}(ax^2)$. The mubent condition corresponds to the set of associated matrices forming a "spread set" (a set of matrices where all pairwise differences are nonsingular).
• Characteristic 2 Adaptation: For $p=2$, the paper utilizes symmetric matrices over $\mathbb{Z}_4$. Lemma 3.2 proves that any symmetric matrix $M$ over $\mathbb{Z}_4$ whose reduction modulo 2 is nonsingular generates a quadratic bent function $B_M(v) = \hat{v}M\hat{v}^T$. Proposition 3.3 shows that any spread set of symmetric matrices over $\mathbb{Z}_2$ produces a mubent set of quadratic functions $V \to \mathbb{Z}_4$, thereby generating a complete set of MUBs.
• Familiar Sets: The paper notes that Examples 2.2 and 3.4 recover the most familiar complete sets of MUBs previously known in the literature.

Significance and Claims
The author presents this work as a "short, elementary construction" that offers a different point of view from the dominant group-theoretic and geometric approaches. The primary significance lies in:

1. Explicitness: The new basis vectors are written explicitly as linear combinations of the standard basis, derived directly from bent functions.
2. Unification: It provides a coherent framework for both odd and even characteristics, with the characteristic 2 case requiring the specific modification to $\mathbb{Z}_4$ to overcome the limitations of $\mathbb{Z}_2$ bent functions.
3. Modesty on Novelty: The author explicitly states that while the approach is different, it "has not led to the construction of any new complete sets of MUBs." The known sets generated (via quadratic functions and spread sets) are consistent with existing literature.
4. Limitations: The paper acknowledges that the method does not currently resolve questions regarding the unitary equivalence of complete sets of MUBs, a problem that the group-theoretic approach handles via Heisenberg groups and finite affine planes. Furthermore, it notes that for $p=2$, the number of known complete sets is not bounded by a polynomial in $N$, whereas for $p>2$, the number of known sets is $O(N)$.

In summary, the paper serves as a concise technical note demonstrating how bent functions can be systematically used to generate complete sets of MUBs, validating the construction through elementary algebraic proofs without claiming to discover previously unknown sets of bases.