Large sets of mutually orthogonal quantum Latin squares

Technical Summary: Large Sets of Mutually Orthogonal Quantum Latin Squares

Problem Statement
The paper addresses the fundamental existence problem regarding Mutually Orthogonal Quantum Latin Squares (MOQLS). Specifically, it investigates the maximum number $t$ of MOQLS of order $n$ that can exist, denoted as $M(n)$. While the classical case (Mutually Orthogonal Latin Squares, MOLS) is well-studied, the quantum generalization introduces non-classical sets where entries are vectors in $\mathbb{C}^n$ rather than scalars. The primary focus is on determining the upper bound for non-classical sets (where $M(n) > 0$) and constructing large non-classical sets for specific orders. Previous work established that a set of $n-1$ MOQLS is necessarily classical, implying $M(n) \le n-2$, and provided various lower bounds for small $n$.

Methodology
The authors employ a combination of combinatorial arguments, linear algebra, and algebraic structures over finite rings.

1. Upper Bound Derivation (Section 3):
   The proof that a set of $n-2$ MOQLS is classical relies on analyzing the "patterns" (supports) of the quantum entries. The authors utilize "quantum sudoku rules" derived from orthogonality and unitarity constraints:

   • Standard Form: Assuming the first row is in a specific standard basis form.
   • Support Disjointness: Orthogonality constraints force the supports of entries in non-first rows to be pairwise disjoint across the set of squares.
   • Weight Reduction: By applying Lemma 10, the authors demonstrate that any quantum Latin square with entries of weight $\ge 2$ can be transformed into a classical one while preserving orthogonality with other squares, provided the set size is $n-2$.
   • Contradiction: They show that if $n-2$ squares exist with at least one non-classical, the constraints on the supports of the entries in the second row and column force a contradiction when attempting to extend the set to $n-1$ classical squares (using Theorem 9 regarding MOLS).

2. Construction of Large Sets (Section 4):
   To construct large non-classical sets, the authors generalize the index set from $\{1, \dots, n\}$ to a finite Frobenius ring $R$ of order $n$.

   • Algebraic Construction: They define a quantum Latin square $\Psi(f)$ associated with a permutation $f: R \to R$ using a generating character $\chi$ of the ring:
     $$\psi(f)_{ij} = \frac{1}{\sqrt{n}} \sum_{x \in R} \chi(if(x) + jx) |x\rangle$$
   • Orthogonality Conditions: They prove that $\Psi(f)$ is classical if and only if $f$ is the sum of an additive map and a constant. Conversely, if $f$ is not of this form, $\Psi(f)$ is non-classical.
   • Counting Orthogonal Squares: The number of classical squares orthogonal to $\Psi(f)$ is determined by the number of $m \in R^*$ such that the map $x \mapsto f(x) - mx$ is a permutation. This relates to the concept of "directions determined by a function."
   • Finite Fields: For $R = \mathbb{F}_q$ (a finite field), the authors utilize known results on functions determining few directions (specifically, functions related to multiplicative subgroups) to maximize the number of such $m$, thereby maximizing the size of the MOQLS set.

Key Contributions and Results

1. Improved Upper Bound (Theorem 5):
   The paper proves that for $n \ge 3$, a set of $n-2$ MOQLS is necessarily classical. Consequently, the upper bound for the size of a non-classical set is tightened from $n-2$ to $n-3$.

   • Significance: This narrows the gap between the known existence of non-classical sets and the theoretical maximum.

2. General Construction Theorem (Theorem 6):
   The authors provide a general construction for $t$ MOQLS of order $n$ over a finite Frobenius ring $R$. If $f$ is a permutation not of the form $x \mapsto ax+b$, and $t = 1 + |\{m \in R^* : x \mapsto f(x)-mx \text{ is a permutation}\}|$, then there exist $t$ MOQLS, exactly one of which is non-classical.

3. Corollary for Prime Powers (Corollary 7):
   Applying the construction to finite fields $\mathbb{F}_q$ where $q$ is a prime power, the paper shows that if $q-1$ has a proper divisor $d \neq 1$, there exist $d-1$ MOQLS($q$), exactly one of which is non-classical. This utilizes functions that determine few directions (specifically those related to the largest proper subgroup of the multiplicative group).

4. Updated Bounds for Small $n$:
   The paper presents a revised table of bounds for $M(n)$ for $2 \le n \le 17$.

   • For $n=7$, the lower bound improves from 2 to 2 (unchanged lower bound, but the upper bound tightens).
   • For $n=8$, the lower bound improves from 2 to 3.
   • For $n=9$, the lower bound improves from 2 to 3.
   • For $n=16$, the lower bound improves from 3 to 4.
   • For $n=17$, the lower bound improves from 3 to 7.
     (Note: The summary reflects the specific improvements listed in Table 2 of the text, where the lower bounds are raised for several values of $n$).

Significance and Open Problems
The paper claims to improve both the lower and upper bounds on the maximum size of non-classical MOQLS sets. The upper bound reduction ($n-2 \to n-3$) is a theoretical tightening of the existence limit. The construction method provides a systematic way to generate large non-classical sets for prime power orders, significantly improving the known lower bounds for many small $n$.

The authors conclude by posing two open problems:

1. Whether a set of $n-3$ MOQLS($n$) (for $n \neq 4$) is necessarily classical.
2. Whether there exist integers $t$ and $n$ such that $t$ MOQLS($n$) exist but $t$ MOLS($n$) do not. The case $n=10$ is highlighted as the smallest open instance for this question, specifically regarding the existence of 7 MOQLS(10).

The work relies on existing literature regarding MOLS, quantum Latin squares, and the combinatorial properties of functions over finite fields, without proposing new experimental implementations or applications beyond the theoretical bounds of existence.