🔢 mathematics

Degree-Four Vector-Coordinate SoS Cannot Detect the MUB Upper Bound

This paper establishes that degree-four Sum-of-Squares relaxations using vector-coordinate formulations fail to detect the known upper bound on the number of mutually unbiased bases (even for $m > d+1$ ), whereas projector-coordinate formulations successfully recover this bound at the same degree.

Original authors: Shreyhaan Sarkar

Published 2026-06-15

📖 5 min read🧠 Deep dive

CC BY 4.0

Original authors: Shreyhaan Sarkar

Original paper licensed under CC BY 4.0 (http://creativecommons.org/licenses/by/4.0/). ✨ This is an AI-generated explanation of the paper below. It is not written or endorsed by the authors. For technical accuracy, refer to the original paper. Read full disclaimer

The Big Picture: A Game of "Perfectly Unbiased" Friends

Imagine you are trying to organize a party in a high-dimensional room (a space with $d$ dimensions). You want to invite groups of people (bases) to stand in specific patterns.

The rule for a "Mutually Unbiased Basis" (MUB) is a bit like a game of perfect balance:

Inside a group: Everyone must stand at perfect right angles to each other (orthonormal).
Between groups: If you pick one person from Group A and one from Group B, the "angle" between them must be exactly the same for every possible pair. They are "unbiased" toward each other.

Mathematicians know a hard limit on this game: You can never have more than $d + 1$ such groups. For example, in a 6-dimensional room ( $d=6$ ), you can have at most 7 groups. It is a famous open mystery whether you can actually reach that limit of 7 in a 6-dimensional room, or if the rules break down before you get there.

The Problem: Can a Computer "See" the Limit?

The paper asks a specific question about a type of computer algorithm called Sum-of-Squares (SoS). Think of SoS as a very smart, but slightly myopic, detective. It tries to prove that a certain arrangement of people is impossible by looking at the math equations that describe their positions.

The detective has a "degree" limit. A degree-4 detective can only look at relationships involving up to four variables at a time (like looking at how four people's positions interact).

The specific question (from "Open Problem 23") was: Can a degree-4 detective prove that 7 groups of people cannot exist in a 6-dimensional room?

The Discovery: The Detective is Using the Wrong Map

The author, Shreyhaan Sarkar, found that the answer depends entirely on how you describe the people to the detective.

1. The "Vector" Map (The Failure)

In the first method, the detective is given the raw coordinates of every person's head, hands, and feet (the real and imaginary parts of the vectors).

The Trick: The author constructed a "fake reality" using random, independent groups of people. In this fake world, the groups aren't perfectly unbiased in the strict sense, but if you only look at them through the "degree-4 lens," they look perfectly unbiased.
The Analogy: Imagine looking at a blurry photo of a crowd. From far away (degree 4), the crowd looks perfectly balanced and random. The detective checks the math, sees everything adds up to zero, and says, "Hey, this arrangement is possible!"
The Result: Because the detective can be fooled by this "fake reality" (called a pseudoexpectation), it cannot prove that 7 groups are impossible. It fails to see the limit of $d+1$ . It thinks 100 groups might be possible in a 6D room, even though we know that's false.

2. The "Projector" Map (The Success)

The author then tried a different way of describing the people. Instead of giving the detective the coordinates of their limbs, they gave the detective a description of the shadow or projection each person casts (mathematically, $P = vv^*$ ).

The Difference: In this "Projector" language, the rules for "unbiasedness" become much simpler (quadratic instead of quartic).
The Result: When the detective uses this map, the "fake reality" trick no longer works. The degree-4 detective can now clearly see the math contradiction. It successfully proves that you cannot have more than $d+1$ groups.

The Main Takeaway

The paper concludes that the failure to solve the problem isn't because the math is too hard; it's because the description was too weak.

Vector Coordinates: Like trying to solve a puzzle by looking at individual puzzle pieces one by one. The degree-4 detective gets confused and thinks the puzzle is solvable when it's not.
Projector Coordinates: Like looking at the picture on the puzzle box. The degree-4 detective can immediately see the pattern and realize the puzzle is impossible.

Why This Matters for the Specific Question

The paper specifically addresses the "Randomstrasse101 Open Problem 23," which asked about the two "Vector" methods.

Answer: No. A degree-4 Sum-of-Squares proof using those specific vector descriptions cannot prove that 7 Mutually Unbiased Bases don't exist in 6 dimensions.
Caveat: This doesn't mean no proof exists. It just means this specific, direct way of writing the problem is too weak for a degree-4 algorithm. If you switch to the "Projector" way of writing the problem, the algorithm becomes strong enough to find the limit.

In short: The paper shows that if you describe the problem using raw coordinates, a computer with limited "vision" (degree 4) will be tricked into thinking the impossible is possible. But if you describe the problem using "shadows" (projectors), that same computer can see the truth.

Technical Summary: Degree-Four Vector-Coordinate SoS Cannot Detect the MUB Upper Bound

Problem Statement
The paper addresses Randomstrasse101 Open Problem 23, which asks whether a degree-four Sum-of-Squares (SoS) proof exists to demonstrate that seven mutually unbiased bases (MUBs) do not exist in $\mathbb{C}^6$ . The problem is framed using two specific vector-coordinate encodings:

Quartic Equality Formulation: Constraints are encoded as quartic relations on the real and imaginary parts of vector components, specifically $|\langle v, w \rangle|^2 = 1/d$ .
$2 \times 2$ Hermitian Semidefinite Formulation: Cross-basis conditions are encoded as semidefinite constraints on $2 \times 2$ Hermitian matrices involving the quadratic inner product $\langle v, w \rangle$ .

The broader context involves the known upper bound $m \le d + 1$ for the number of MUBs in dimension $d$ . While equality holds for prime power dimensions, the case $d=6$ remains open, with the conjecture that $m=7$ is impossible.

Methodology
The authors analyze the power of degree-four SoS relaxations by constructing degree-four pseudoexpectations. A degree-four pseudoexpectation is a linear functional $\tilde{\mathbb{E}}$ on polynomials of degree at most four that satisfies positivity ( $\tilde{\mathbb{E}}[f^2] \ge 0$ ) and consistency with constraints. If such a pseudoexpectation exists for a system, no degree-four SoS refutation (proof of infeasibility) exists.

The core methodology involves:

Haar-Random Construction: The authors define a pseudoexpectation based on the expectation over independent Haar-random unitary matrices. Specifically, for $m$ bases in $\mathbb{C}^d$ , the vectors are taken as columns of independent random unitary matrices.
Verification of Constraints:
- Same-basis constraints: Orthonormality holds pointwise (exactly) for the random construction.
- Cross-basis constraints: For independent Haar-random unit vectors $x, y$ , the expectation $\mathbb{E}[|\langle x, y \rangle|^2] = 1/d$ .
Affine Multiplier Analysis: For the semidefinite formulation, the authors prove a specific bound on the operator norm of multiplication by the inner product $z = \langle x, y \rangle$ acting on affine-linear functions. They show that $|\mathbb{E}[p z q]| \le \frac{1}{d} \sqrt{\mathbb{E}[|p|^2]\mathbb{E}[|q|^2]}$ .
Formulation Comparison: The paper contrasts the vector-coordinate formulation with a projector-coordinate formulation where variables are rank-one projectors $P = vv^*$ . In this setting, the cross-unbiasedness condition becomes quadratic ( $\text{Tr}(P_i^{(k)} P_j^{(\ell)}) = 1/d$ ).

Key Contributions and Results

Lower Bound for Vector-Coordinate Formulations:
The primary result (Theorems 5.1 and 7.1) establishes that for any dimension $d$ and any proposed number of bases $m$ , the standard vector-coordinate MUB system admits a degree-four pseudoexpectation derived from independent Haar-random bases.
- Quartic Equality: The pseudoexpectation satisfies the quartic constraints because the expected value of the quartic term $|\langle x, y \rangle|^2 - 1/d$ is zero. Since the constraints are degree four, a degree-four refutation can only multiply them by constants, which the pseudoexpectation annihilates.
- Semidefinite Formulation: Using the affine multiplier bound (Theorem 6.1), the authors show the pseudoexpectation satisfies the degree-four localizing constraints for the $2 \times 2$ Hermitian matrices.
- Consequence: Degree-four SoS in these vector-coordinate formulations cannot refute the existence of $m$ MUBs, even when $m > d + 1$ (where MUBs are known or conjectured to be impossible). Specifically, for $d=6, m=7$ , no degree-four SoS proof of non-existence exists in these encodings.
Formulation Separation (Projector vs. Vector):
The paper demonstrates that this failure is specific to the vector-coordinate encoding. In a projector-coordinate formulation (Theorem 8.1), where variables are centered projectors $Q = P - I/d$ , the cross-unbiasedness constraints are quadratic.
- The authors construct a degree-four SoS refutation for the projector system whenever $m > d + 1$ .
- This refutation relies on a Gram matrix identity involving the trace of squared sums of projectors, which yields a negative constant modulo the constraints when $m > d + 1$ .
- Result: Degree-four SoS can recover the elementary upper bound $m \le d + 1$ in the projector formulation.

Significance and Claims
The paper claims a formulation-dependent separation in the power of low-degree SoS hierarchies for the MUB problem:

Negative Answer to Open Problem 23: For the two specific vector-coordinate encodings described in the problem statement (quartic equations and $2 \times 2$ LMIs), the answer is negative. Degree-four SoS is intrinsically too weak to detect the basic counting obstruction ( $m \le d + 1$ ).
Formulation Sensitivity: The inability of degree-four SoS to solve the problem is not a universal limitation of the method but a limitation of the direct vector-coordinate relaxation. The same degree of relaxation is strictly stronger when applied to projector coordinates, where it successfully recovers the known upper bound.
Implication for $d=6$ : While the projector formulation recovers $m \le 7$ for $d=6$ , the paper notes that the $d=6, m=7$ case is the "tight" boundary of this bound. Therefore, the separation result does not definitively answer whether a stronger projector-variable degree-four proof can rule out exactly seven MUBs in $\mathbb{C}^6$ , only that it can rule out eight or more.

The work isolates a specific degree-four obstruction for vector-coordinate SoS, suggesting that any successful low-degree SoS approach to the dimension-six MUB problem must utilize a lifted formulation (such as projectors) rather than the direct vector coordinates.