Tight Bounds on the Randomized Communication Complexity of Vector-in-Subspace
Abstract
We prove that the randomized communication complexity of Vector-in-Subspace in ℝn with error at most 1/3 is Θ(√n). Alice holds a unit vector u and Bob holds an n/2-dimensional subspace H; they must distinguish u∈ H from u∈ H⊥. 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(√n) upper bound, improves the Ω(n1/3) lower bound of Klartag and Regev, and removes the total-rank restriction in Grupel's Ω(√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.
Related
- Towards exascale fully relativistic pseudopotential density functional theory calculations enabled by mixed-precision computation and compressed-communication using residual based subspace iteration
- On the quantum communication complexity of total functions
- Constant-round quantum advantage in communication complexity for total functions
- Improved Separations between Quantum and Classical Communication Complexity of Total Functions
- Tight Communication Bounds for Distributed Algorithms in the Quantum Routing Model
BibTeX
@misc{wang2026tight,
title = {{Tight Bounds on the Randomized Communication Complexity of Vector-in-Subspace}},
author = {Chengu Wang},
howpublished = {arXiv},
year = {2026},
month = oct,
doi = {10.48550/arxiv.2610.30052},
eprint = {2610.30052},
archivePrefix = {arXiv},
url = {https://arxiv.org/abs/2610.30052},
}
RIS
TY - UNPB
TI - Tight Bounds on the Randomized Communication Complexity of Vector-in-Subspace
AU - Chengu Wang
PY - 2026
DA - 2026/10/21
PB - arXiv
DO - 10.48550/arxiv.2610.30052
UR - https://arxiv.org/abs/2610.30052
AB - We prove that the randomized communication complexity of Vector-in-Subspace in ℝ^n with error at most 1/3 is Θ(√n). Alice holds a unit vector u and Bob holds an n/2-dimensional subspace H; they must distinguish u∈ H from u∈ H^⊥. 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(√n) upper bound, improves the Ω(n^1/3) lower bound of Klartag and Regev, and removes the total-rank restriction in Grupel's Ω(√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.
ER -