Communication cost for vector and subspace test scales with square root of dimension

Tight Bounds on the Randomized Communication Complexity of Vector-in-Subspace

Computational Complexity

Summary

The paper studies how much communication is needed between two parties to decide if a vector lies inside a particular subspace or is orthogonal to it. One person has the vector, the other has the subspace, and they want to figure out if the vector is within the subspace using random communication with some error allowed. The authors prove that the minimum amount of communication grows roughly with the square root of the vector’s dimension, confirming prior upper bounds and improving previous lower bounds. This also shows a big gap between classical communication and quantum communication, since a quantum protocol can solve it with very few qubits.

What this means in practice

A theory result. No direct application yet.

Authors

Chengu Wang

Abstract

We prove that the randomized communication complexity of Vector-in-Subspace in $\mathbb R^n$ with error at most $1/3$ is $Θ(\sqrt n)$. Alice holds a unit vector $u$ and Bob holds an $n/2$-dimensional subspace $H$; they must distinguish $u\in H$ from $u\in H^\perp$. An exact one-way quantum protocol uses $O(\log n)$ qubits, making the problem a geometric example of an exponential quantum advantage over interactive classical communication. Our lower bound matches Raz's $O(\sqrt n)$ upper bound, improves the $Ω(n^{1/3})$ lower bound of Klartag and Regev, and removes the total-rank restriction in Grupel's $Ω(\sqrt n)$ result. The proof establishes a Gaussian moment bound over complete rectangle partitions. A complex Gaussian representation yields a vanishing even moment whose cancellation is preserved when averaging over the partition. We control the signed conditional moments around a real center by decomposing conditional Gaussian measures into fixed coordinates and sub-Gaussian components. Combining this estimate with spherical harmonic analysis gives the communication lower bound.
View PDFOpen arXiv