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

2026-10-22 · arXiv Quantum Physics

arXiv:2610.30052v1 Announce Type: cross

Abstract: We prove that the randomized communication complexity of Vector-in-Subspace in $\mathbb R^n$ with error at most $1/3$ is $\Theta(\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 $\Omega(n^{1/3})$ lower bound of Klartag and Regev, and removes the total-rank restriction in Grupel's $\Omega(\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.

原文链接：https://arxiv.org/abs/2610.30052

查看更多资讯请见 AI 行业资讯。