pipette
ENEnglish

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

Chengu Wang

Preprint

En palabras de los autores

We prove that the randomized communication complexity of Vector-in-Subspace in with error at most is . Alice holds a unit vector and Bob holds an -dimensional subspace ; they must distinguish from . An exact one-way quantum protocol uses qubits, making the problem a geometric example of an exponential quantum advantage over interactive classical communication. Our lower bound matches Raz's upper bound, improves the lower bound of Klartag and Regev, and removes the total-rank restriction in Grupel's 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.

Resultado principalEl resumen no menciona limitaciones.

Apareció: jueves, 22 de octubre. arXiv. Preprint, todavía sin revisión por pares.