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

Preprint · Chengu Wang

- Archive id: arxiv:2610.30052
- Published: 2026-10-21
- arXiv: https://arxiv.org/abs/2610.30052
- Citations: 0
- Source URL: https://arxiv.org/abs/2610.30052
- PDF: https://arxiv.org/pdf/2610.30052
- Provenance: arxiv

## 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.

_Abstract reproduced under CC0-1.0 (arXiv descriptive metadata)._

Topics: [Quantum Algorithms & Quantum Advantage](https://space-kitty.com/topics/quantum-algorithms-advantage)

---
Space Kitty Archive · https://space-kitty.com · API: https://space-kitty.com/api/v1 · MCP: https://space-kitty.com/mcp · Premium: $0.20/request via x402 (Base Sepolia (testnet)). Metadata: arXiv (CC0), OpenAlex (CC0), Europe PMC (CC BY/CC0 works), ClinicalTrials.gov.