Deterministic algorithm solves matrix sign assignment for kadison singer problem
Rank-One Matrix Discrepancy and Algorithmic Kadison--Singer
Data Structures and AlgorithmsDiscrete Mathematics
Summary
The Kadison–Singer problem is a famous mathematical question about breaking up vectors in a balanced way. The authors provide a guaranteed method to assign plus or minus signs to special matrices to keep the combined effect controlled. They offer an algorithm that finds these signs efficiently and deterministically, meaning it always produces the same answer quickly. This work connects a complex theoretical problem to a clear, step-by-step solution.
What this means in practice
- •For signal processing engineers: Design balanced signal partitions with guaranteed bounds for noise and distortion control using a deterministic matrix sign assignment algorithm.
- •For quantum computing developers: Efficiently separate quantum states represented by rank-one projectors to maintain system stability using deterministic sign assignments.
A theory result. No direct application yet.
Authors
Ekene Ezeunala, Haotian Jiang
Abstract
We give a deterministic polynomial-time algorithm that, given rational Hermitian matrices $H_1,\dots,H_N$ of rank at most one, finds signs $s\in\{\pm1\}^N$ with $\|\sum_i s_i H_i\|\le 13\|\sum_i H_i^2\|^{1/2}$. As a corollary, for vectors $v_i$ with $\sum_i v_iv_i^*=I$ and $\|v_i\|^2\leδ$, the signs yield a partition $[N] = S_1 \cup S_2$ such that each part satisfies $\|\sum_{i \in S_j} v_i v_i^* - \frac{I}{2}\| \leq \frac{13}{2}\sqrtδ$ for $j = 1,2$. This gives a deterministic polynomial-time algorithm for the Kadison--Singer problem, in Weaver's equivalent discrepancy-theoretic $\mathsf{KS}_2$ formulation, with a universal constant.