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

Chengu Wang

Source-linked AI summary

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

Chengu Wang

arXiv:2610.30052v1Oct 21, 2026cs.CCquant-ph

TL;DR

Vector-in-Subspace asks how much classical communication is needed to distinguish whether a unit vector lies in a given half-dimensional subspace or its orthogonal complement. The proof uses global cancellation in Gaussian moments and combines moment bounds with estimates on the protocol’s advantage. It establishes a square-root randomized communication complexity bound, matching the stated upper bound.

Problem
Vector-in-Subspace asks how much classical communication is needed to distinguish whether a unit vector lies in a half-dimensional subspace or its orthogonal complement, a problem illustrating a classical–quantum communication separation.
Source: §1 · pp. 1–2
Method
The proof exploits global cancellation in a vanishing even moment around a random real center, then uses spectral estimates to bound the protocol’s advantage.
Source: §1.3 · pp. 3–4
Results
R1/3(VSPn) = Θ(√n), matching Raz’s O(√n) upper bound and improving the Ω(n^1/3) lower bound to Ω(√n).
Source: §1.2 · p. 3, §3.4 · p. 12
Takeaways & Limitations
The square-root lower bound removes the total-rank restriction in Grupel’s square-root lower bound.
Source: §1.2 · p. 3
The cap example limits only the specific one-subspace sampling estimate at the cube-root scale; it does not preclude stronger arguments using the complete partition.
Source: §1.1 · p. 2

Abstract

from arXiv · show

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.

1 Introduction

Vector-in-Subspace asks whether a unit vector lies in a given half-dimensional subspace or its orthogonal complement; an exact one-way quantum protocol contrasts with the classical communication question. The paper proves a square-root randomized classical bound and outlines a Gaussian-moment and spherical-harmonic proof.

1 Introduction

Alice has a unit vector and Bob a half-dimensional subspace, and they must distinguish membership from membership in its orthogonal complement; Alice can send an exact quantum state using ⌈log2 n⌉ qubits.Source: §1 · pp. 1–2, §1.1 · p. 2

1.1 Previous results

Raz’s O(√n)-bit classical protocol gives the existing upper bound, leaving open whether interaction could reduce the communication scale [Raz99].Its public-coin protocol selects a Gaussian vector with the largest input inner product and sends its index.Source: §1.1 · p. 2
Klartag and Regev’s Ω(n1/3) lower bound used spherical sampling, hypercontractivity, the Radon transform, and a martingale argument.Source: §1.1 · p. 2
A spherical cap can make the particular one-subspace sampling estimate used by Klartag and Regev sharp at the cube-root scale, but does not rule out arguments using a complete protocol partition [KR11].Source: §1.1 · p. 2
Grupel proved an Ω(√n) lower bound only for protocols whose total Alice decision rank is at most α√n, whereas this paper removes that restriction [Gru17].Total rank measures how many linear functionals of Alice’s input decisions use along an execution.Source: §1.1 · pp. 2–3, §1.2 · p. 3

1.2 Our result

R1/3(VSPn) = Θ(√n), improving the Ω(n1/3) lower bound, matching Raz’s O(√n) upper bound, and removing Grupel’s total-rank restriction [Gru17].Source: §1.2 · p. 3

1.3 Proof overview

The proof reduces protocols to complete partitions of product Gaussian space and uses imaginary Gaussians to obtain Wick-corrected moments whose cancellation holds globally across the partition.The identity need not hold inside any individual rectangle.Source: §1.3 · p. 3
Conditional Gaussian measures are decomposed into fixed coordinates and sub-Gaussian components, while polynomial-moment induction controls the remainder and its tensor norms.The fixed coordinates supply a real center; taking absolute moments of the complex variable too early would introduce unwanted dimension dependence.Source: §1.3 · p. 4

2 Preliminaries

The preliminaries fix the promise distribution and protocol reductions, then establish Gaussian, tensor, and cell-surprise conventions used in the proof. They also introduce Gaussian kernels whose imaginary components implement the Wick corrections.

2.1 Protocols, measures, and constants

A deterministic cost-d protocol yields a complete partition into at most 2^d rectangles, and fixing its coins gives the corresponding deterministic reduction.The fair promise law defines success as 1/2 plus the protocol's advantage.Source: §2.1 · p. 5

2.2 Gaussian and tensor conventions

Hermite tensors and partition norms provide the Gaussian and tensor conventions, while SG(B) bounds uncentered linear projections by B√q.The GOE Euclidean inner product and complex Wick representation are specified for later calculations.Source: §2.2 · pp. 5–6

2.3 Change of density and the probability of a cell

For a complete partition with at most 2^d rectangles, the total surprise exceeds d log 2 by v with probability at most e^-v.The surprise is the sum of the log reciprocal probabilities of the rectangle's two parts.Source: §2.3 · p. 6

2.4 The Gaussian kernels

Averaging over imaginary Gaussian variables supplies Wick corrections, as illustrated by F1(y, G) = yT Gy − tr G.The correction subtracts the Gaussian mean, and higher degrees receive the corresponding corrections.Source: §2.4 · pp. 6–7

3 Spherical reduction and the main theorem

The section reduces the communication lower bound to a Gaussian moment estimate over complete partitions, using spherical harmonic analysis and a Gaussian lift. Local smoothing extracts the needed coefficient, and the resulting lower bound matches the classical upper bound.

3 Spherical reduction and the main theorem

Theorem 3.1 reduces the communication lower bound to a Gaussian moment estimate for every complete partition with at most 2^d cells.The estimate is stated for every integer k ≥ 1.Source: §3 · p. 7

3.1 The subspace-transform spectrum

The subspace transforms act diagonally on spherical harmonics: odd degrees vanish, and degree-2k kernels are themselves degree-2k harmonics.Images of distinct degrees are orthogonal.Source: §3.1 · pp. 7–8

3.2 The Gaussian lift and its leading coefficient

Lifting the sphere and subspace to a Gaussian vector and an independent GOE matrix preserves the reference law and rectangle structure.The resulting conditional polynomial has degree at most k in the subspace coordinate t = XT SHX.Source: §3.2 · p. 9

3.3 Local smoothing and coefficient extraction

Poisson smoothing makes the protocol's advantage a polynomial in the smoothing parameter, whose forward differences extract its leading coefficient.The smoothed protocols are comparison objects in a coefficient identity, not sequential executions that multiply communication cost.Source: §3.3 · p. 11

3.4 Proof of the communication theorem

The randomized communication complexity is Ω(√n), matching Raz's O(√n) protocol [Raz99, Theorem 3.8].The lower bound follows by converting a low-cost randomized protocol into a deterministic one that contradicts the advantage bound.Source: §3.4 · p. 12

4 Cancellation over complete rectangle partitions

A vanishing complex even moment controls conditional moments around a real center, with the cancellation retained across a complete rectangle partition. The proof bounds fluctuations by separating fixed coordinates from sub-Gaussian bulk components.

4.1 One complex random variable

If EQ2k = 0, a real conditional center and bounds on signed centered moments control the conditional kth moment.The lemma bounds the center using the vanishing even moment without requiring a dimension-free bound on E|Q − α|2k.Source: §4.1 · pp. 12–13

4.2 Flats, bulks, and the two kinds of fluctuation

Conditional Gaussian measures are decomposed into fixed coordinates and a sub-Gaussian bulk, whose signed moments preserve cancellation without dimension-dependent absolute-moment bounds.The flat fluctuation is controlled by Gaussian hypercontractivity, while the bulk is controlled by signed moments.Source: §4.2 · pp. 13–14

4.3 Proof of the complete-partition estimate

Sampling a rectangle and its components from the complete partition preserves the original product Gaussian marginal and allows the centered-moment bound to be averaged over the partition.The resulting estimate is bounded by C^k k! (d + k^2)^k.Source: §4.3 · p. 15

5 Flats and sub-Gaussian components

The section decomposes bounded-density Gaussian laws into affine slices with sub-Gaussian residuals. A single potential controls the decomposition’s combined cost and proves it terminates.

Construction and termination

A single potential controls residual density, fixed coordinates, and dimension, and its expected decrease proves almost-sure termination.At every nonterminal state, each split decreases its conditional expectation by at least 1/6; the expected number of splits is at most 6e^(a/2).Source: §5 · pp. 16–17

Decomposition into flats and sub-Gaussian bulks

A density ρ ≤ e^a relative to Gaussian measure is a measurable mixture of affine slices whose residual densities are SG(5).For each component, the cost is the residual log-density bound plus |y|^2 and the dimension of the fixed-coordinate space.Source: §5 · p. 16
The component cost c satisfies E[e^(c/8)] ≤ e^(a/2), Pr(c > 4a + 8t) ≤ e^(−t), and ||c||_u ≤ 4a + 8u for t ≥ 0 and u ≥ 1.These bounds control the density, offset, and number of fixed coordinates together.Source: §5 · p. 16

Construction and termination

The construction splits failing one-dimensional tails, either retaining a normalized off-tail bulk or fixing the violating coordinate and updating the residual density.The transitions preserve the represented law by disintegration.Source: §5 · p. 16

6 Gaussian chaos estimates

The section develops Gaussian chaos moment bounds using partition norms and a derivative expansion stopped partway through. Separating the Hilbert–Schmidt contribution from the remaining partition terms improves the degree dependence of that contribution.

Moment growth of partial tensors

The moment-growth argument bounds partial tensor moments by combining Gaussian log-Sobolev estimates with gradient bounds from the next partial tensor.The partition-norm framework is attributed to Latała [Lat06], and the moment-growth method to Aida–Stroock.Source: §6 · pp. 17–18

One Gaussian slot

A one-Gaussian-slot inequality controls the injective norm after conditioning on all but one Gaussian slot, using a Gaussian shift and tail integration.The argument adapts Aden-Ali [AA25] directly to moments.Source: §6 · pp. 18–19

Role in later estimates

The proof keeps the Hilbert–Schmidt and other partition-norm terms separate because they play different roles in the later estimates.The Hilbert–Schmidt term is paired with the Frobenius bound, while the other term is paired with partition norms.Source: §6 · pp. 17, 20

Complex split bound

The complex split bound follows by decoupling the slots and applying the real split bound to the real and imaginary parts.The conversion of partition norms and the real-imaginary decomposition contribute factors bounded by 2^k.Source: §6 · p. 20

7 Polynomial moments of sub-Gaussian components

This section derives polynomial and mixed-moment estimates for sub-Gaussian components. One induction yields both partition-norm bounds and a stronger Frobenius bound, under assumptions that allow dependent coordinates.

Bulk estimate

One induction in weighted polynomial moments gives both partition-norm bounds and a stronger Frobenius bound for laws with sub-Gaussian linear marginals and bounded Gaussian-relative density.The coordinates may be dependent; the argument does not assume the functional inequalities on the law used by Adamczak–Wolff.Source: §7 · p. 20

Polynomial moment bounds

The polynomial-moment induction fixes kp = μ and uses duality and Hölder to bound moments of degree k for 1 ≤ k ≤ μ.It uses Σ = σ + 2μ^2 + μ.Source: §7 · p. 21

Partition norms

Partition norms of the Wick tensor are bounded using the polynomial estimates, with each block contributing a factor r/Σ_r relative to the trivial scale.Here Σ_r = σ + 2r^2 + r.Source: §7 · p. 22

Frobenius bound

A separate Frobenius estimate supplies the Hilbert–Schmidt control required alongside the partition norms in the final bulk estimate.The proof notes that this separate estimate is essential to the final step.Source: §7 · pp. 22–23

Mixed moments

The mixed-moment estimate handles a Gaussian orthogonal ensemble matrix and an independent Gaussian vector through a decoupled form of the mixed chaos.The setup identifies tensor order r = 2m + c and Gaussian degree j = m + c.Source: §7 · pp. 22–23

AI Disclosure

The author discloses using OpenAI Codex and Claude Code in developing and revising the manuscript, while taking full responsibility for its content.

AI Disclosure

OpenAI Codex and Claude Code assisted with developing, checking, and simplifying proof arguments.The author takes full responsibility for the proofs.Source: AI Disclosure · p. 23
The tools also assisted with researching related work and verifying citations.The author takes full responsibility for the references and attribution.Source: AI Disclosure · p. 23
The tools assisted with drafting and revising the manuscript, while the author retains responsibility for correctness and originality.The disclosure also assigns responsibility for all content to the author.Source: AI Disclosure · p. 23