Challenges
Datasets
Workspaces
Papers
Discussions
Leaderboard
Log inSign up
Challenges
Datasets
Workspaces
Papers
Discussions
Leaderboard
Blog
Job Board
Q3AS

© 2026 Aqora Quantum S.A.S.

TermsPrivacyLegal Notice

arXiv:2610.30052

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

Chengu Wang

cs.CCquant-phSubmitted Oct 21, 2026• Announced Oct 22, 2026• 0 citations
arXivHTMLPDF

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.

AI Summary

Vector-in-Subspace asks Alice, given a unit vector $u\in\mathbb R^n$, and Bob, given an $n/2$-dimensional subspace $H$, to distinguish $u\in H$ from $u\in H^\perp$. The paper determines its public-coin randomized communication complexity, allowing arbitrary interaction: $R_{1/3}(\mathrm{VSP}_n)=\Theta(\sqrt n)$. The lower bound improves the previous unrestricted $\Omega(n^{1/3})$ bound, matches Raz’s classical upper bound, and removes the total-rank restriction from an earlier $\Omega(\sqrt n)$ result. An exact one-way quantum protocol uses $\lceil\log_2 n\rceil$ qubits. The main analytic result bounds Gaussian Wick-polynomial moments averaged over any complete partition into at most $2^d$ rectangles: $\mathbb E|\mathbb E[F_k\mid\mathsf T]|\le C^k k!(d+k^2)^k$. A complex Gaussian representation supplies a globally vanishing even moment. Conditioning on rectangles and decomposing Alice’s conditional Gaussian law into fixed coordinates and sub-Gaussian residual components permits control of signed moments around a real center. Crucially, cancellation is retained across the complete partition before taking absolute values. Polynomial-moment estimates provide both partition-norm and Frobenius-norm control of the residual Wick tensors. Spherical harmonic analysis, a Gaussian lift, and smoothing transfer this estimate to protocol advantage. The new estimate controls low harmonic levels, while hypercontractivity and the exact subspace-transform spectrum handle higher levels, establishing the lower bound for $d$ below a constant multiple of $\sqrt n$. The stated theorem concerns the exact membership promise and communication cost, not computational efficiency. The matching classical protocol may require substantial local computation.

No sign of AI-generated textAI use disclosed
The author used OpenAI Codex and Claude Code to assist with developing, checking, and simplifying proof arguments; researching related work and verifying citations; and drafting and revising the manuscript.

Written by gpt-6.1-sol from the paper's full text. Automated: it can be wrong.

Related papers

Exponential Separation of Quantum and Classical One-Way Communication Complexity

Ziv Bar-Yossef, T. S. Jayram, Iordanis Kerenidis

We give the first exponential separation between quantum and bounded-error randomized one-way communication complexity. Specifically, we define the Hidden Matching Problem HM$_n$: Alice gets as input a string ${\bf x}\in\{0, 1\}^n$, and Bob gets a perfect matching M on the n coordinates. Bob's goal is to output a tuple $\langle i,j,b \rangle$ such that the edge $(i,j)$ belongs to the matching M and $b=x_i\oplus x_j$. We prove that the quantum one-way communication complexity of HM$_n$ is $O(\log n)$, yet any randomized one-way protocol with bounded error must use $\Omega({\sqrt{n}})$ bits of communication. No asymptotic gap for one-way communication was previously known. Our bounds also hold in the model of Simultaneous Messages (SM), and hence we provide the first exponential separation between quantum SM and randomized SM with public coins. For a Boolean decision version of HM$_n$, we show that the quantum one-way communication complexity remains $O(\log n)$ and that the 0-error randomized one-way communication complexity is $\Omega(n)$. We prove that any randomized linear one-way protocol with bounded error for this problem requires $\Omega(\sqrt[3]{n \log n})$ bits of communication.

SIAM Journal on Computing•Jan 1, 2008•57 citations

The Communication Complexity of Approximating Matrix Rank

Alexander A. Sherstov, Andrey A. Storozhenko

We fully determine the communication complexity of approximating matrix rank, over any finite field F. We study the most general version of this problem, where$0\leqslant r < R\leqslant n$are given integers and Alice and Bob need to determine whether their respective matrices$A, B\in \mathbb{F}^{n\times n}$satisfy rk$(A+B)=r$versus rk$(A+B)=R$. We show that this problem has commu-nication cost$\Omega(r^{2}\log\vert \mathbb{F}\vert)$, which is optimal. Our lower bound holds even for quantum protocols and even for error probability$\frac{1}{2}(1-\vert \mathbb{F}\vert ^{-r/3})$, which too is optimal because this problem has a two-bit classical protocol with error$\frac{1}{2}(1-\vert \mathbb{F}\vert ^{-\Theta(r)})$. Prior to our work, lower bounds were known only for constant-error protocols and only for consecutive integers$r$and$R$, with no implication for the approximation of matrix rank. We also settle an analogous question for subspaces, where Alice has a subspace$S$, Bob has a subspace$T$) and they need to approximate the dimension of the subspace$S+T$generated by$S$and$T$(equivalently, approximate the dimension of$S\cap T$). As an application, we obtain an$\Omega(n^{2}\log\vert \mathbb{F}\vert)/k$memory lower bound for any streaming algorithm with$k$passes that approximates the rank of an input matrix$M\in \mathbb{F}^{n\times n}$within a factor of$\sqrt{2}-\delta$, for any$\delta > 0$. Our result is an exponential improvement in$k$over previous work.

arXiv:2410.20094•Annual Symposium on Foundations of Computer Science•Oct 27, 2024•6 citations

The communication complexity of distributed estimation

Parikshit Gopalan, Raghu Meka, Prasad Raghavendra +2 more

We study an extension of the standard two-party communication model in which Alice and Bob hold probability distributions $p$ and $q$ over domains $X$ and $Y$, respectively. Their goal is to estimate \[ \mathbb{E}_{x \sim p,\, y \sim q}[f(x, y)] \] to within additive error $\varepsilon$ for a bounded function $f$, known to both parties. We refer to this as the distributed estimation problem. Special cases of this problem arise in a variety of areas including sketching, databases and learning. Our goal is to understand how the required communication scales with the communication complexity of $f$ and the error parameter $\varepsilon$. The random sampling approach -- estimating the mean by averaging $f$ over $O(1/\varepsilon^2)$ random samples -- requires $O(R(f)/\varepsilon^2)$ total communication, where $R(f)$ is the randomized communication complexity of $f$. We design a new debiasing protocol which improves the dependence on $1/\varepsilon$ to be linear instead of quadratic. Additionally we show better upper bounds for several special classes of functions, including the Equality and Greater-than functions. We introduce lower bound techniques based on spectral methods and discrepancy, and show the optimality of many of our protocols: the debiasing protocol is tight for general functions, and that our protocols for the equality and greater-than functions are also optimal. Furthermore, we show that among full-rank Boolean functions, Equality is essentially the easiest.

arXiv:2511.21015•Nov 26, 2025•0 citations

Exponential separation of quantum and classical one-way communication complexity

Ziv Bar-Yossef, T. S. Jayram, Iordanis Kerenidis

We give the first exponential separation between quantum and bounded-error randomized one-way communication complexity. Specifically, we define the Hidden Matching Problem HMn: Alice gets as input a string x ∈ (0, 1)n and Bob gets a perfect matching M on the n coordinates. Bob's goal is to output a tuple [i,j,b] such that the edge (i,j) belongs to the matching M and b = xi ⊕ xj. We prove that the quantum one-way communication complexity of HMn is O(log n), yet any randomized one-way protocol with bounded error must use Ω(√n) bits of communication. No asymptotic gap for one-way communication was previously known. Our bounds also hold in the model of Simultaneous Messages (SM) and hence we provide the first exponential separation between quantum SM and randomized SM with public coins.For a Boolean decision version of HMn, we show that the quantum one-way communication complexity remains O(log n) and that the 0-error randomized one-way communication complexity is Ω(n). We prove that any randomized linear one-way protocol with bounded error for this problem requires Ω(√[3] n log n) bits of communication.

ACM Symposium on Theory of Computing (STOC)•Jun 13, 2004•111 citations

The one-way communication complexity of the Boolean Hidden Matching Problem

Iordanis Kerenidis, Ran Raz

We give a tight lower bound of Omega(\sqrt{n}) for the randomized one-way communication complexity of the Boolean Hidden Matching Problem [BJK04]. Since there is a quantum one-way communication complexity protocol of O(\log n) qubits for this problem, we obtain an exponential separation of quantum and classical one-way communication complexity for partial functions. A similar result was independently obtained by Gavinsky, Kempe, de Wolf [GKdW06]. Our lower bound is obtained by Fourier analysis, using the Fourier coefficients inequality of Kahn Kalai and Linial [KKL88].

arXiv:quant-ph/0607173•Jul 25, 2006•21 citations

Communication Complexity of Integer Matrix Singularity

Chengu Wang

Alice and Bob hold complementary halves of the columns of an $n\times n$ matrix of $k$-bit integers and decide whether it is singular over $\mathbb Q$. Up to constant-factor dimension growth, this partitioned problem is equivalent to additive singularity, where Alice and Bob hold $n\times n$ matrices $A,B$ of $k$-bit integers and test the singularity of $A+B$ over $\mathbb Q$. We prove a bounded-error quantum lower bound $Ω(\min\{n^{3/2}\sqrt{k\log n},n^2\log(nk)\})$ and a randomized upper bound $O(n^2\min\{k,\log(k+\log n)\})$. The bounds match at $Θ(n^2\log(nk))$ for $k\ge n\log n$. The lower bound holds even under the promise of rank $n-1$ versus $n$. Its proof combines an integer witness with a local digit encoding, while the upper-bound protocol lifts modular kernel relations using short messages. Bitwise sharing changes how the communication complexity depends on the entry bit length $k$. If Alice and Bob instead hold $n\times n$ matrices $A,B$ of $k$-bit integers and test whether their entrywise bitwise XOR $A\oplus B$ is singular over $\mathbb Q$, we prove a quantum lower bound $Ω(n^2k)$, matching the trivial upper bound. This lower bound holds even under the promise of rank $n-1$ versus $n$. Our proof uses a dense weighted equation and a signed Fourier witness whose exceptional dyadic frequencies can be removed at small variation cost.

cs.CCCross-listedarXiv:2610.33521•Oct 27, 2026•0 citations
We prove that the randomized communication complexity of Vector-in-Subspace in Rn\mathbb R^nRn with error at most 1/31/31/3 is Θ(n)Θ(\sqrt n)Θ(n​). Alice holds a unit vector uuu and Bob holds an n/2n/2n/2-dimensional subspace HHH; they must distinguish u∈Hu\in Hu∈H from u∈H⊥u\in H^\perpu∈H⊥. An exact one-way quantum protocol uses O(log⁡n)O(\log n)O(logn) qubits, making the problem a geometric example of an exponential quantum advantage over interactive classical communication. Our lower bound matches Raz's O(n)O(\sqrt n)O(n​) upper bound, improves the Ω(n1/3)Ω(n^{1/3})Ω(n1/3) lower bound of Klartag and Regev, and removes the total-rank restriction in Grupel's Ω(n)Ω(\sqrt n)Ω(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.
Vector-in-Subspace asks Alice, given a unit vector u∈Rnu\in\mathbb R^nu∈Rn, and Bob, given an n/2n/2n/2-dimensional subspace HHH, to distinguish u∈Hu\in Hu∈H from u∈H⊥u\in H^\perpu∈H⊥. The paper determines its public-coin randomized communication complexity, allowing arbitrary interaction: R1/3(VSPn)=Θ(n)R_{1/3}(\mathrm{VSP}_n)=\Theta(\sqrt n)R1/3​(VSPn​)=Θ(n​). The lower bound improves the previous unrestricted Ω(n1/3)\Omega(n^{1/3})Ω(n1/3) bound, matches Raz’s classical upper bound, and removes the total-rank restriction from an earlier Ω(n)\Omega(\sqrt n)Ω(n​) result. An exact one-way quantum protocol uses ⌈log⁡2n⌉\lceil\log_2 n\rceil⌈log2​n⌉ qubits.
The main analytic result bounds Gaussian Wick-polynomial moments averaged over any complete partition into at most 2d2^d2d rectangles: E∣E[Fk∣T]∣≤Ckk!(d+k2)k\mathbb E|\mathbb E[F_k\mid\mathsf T]|\le C^k k!(d+k^2)^kE∣E[Fk​∣T]∣≤Ckk!(d+k2)k. A complex Gaussian representation supplies a globally vanishing even moment. Conditioning on rectangles and decomposing Alice’s conditional Gaussian law into fixed coordinates and sub-Gaussian residual components permits control of signed moments around a real center. Crucially, cancellation is retained across the complete partition before taking absolute values. Polynomial-moment estimates provide both partition-norm and Frobenius-norm control of the residual Wick tensors.
Spherical harmonic analysis, a Gaussian lift, and smoothing transfer this estimate to protocol advantage. The new estimate controls low harmonic levels, while hypercontractivity and the exact subspace-transform spectrum handle higher levels, establishing the lower bound for ddd below a constant multiple of n\sqrt nn​.
The stated theorem concerns the exact membership promise and communication cost, not computational efficiency. The matching classical protocol may require substantial local computation.
We give the first exponential separation between quantum and bounded-error randomized one-way communication complexity. Specifically, we define the Hidden Matching Problem HMn_nn​: Alice gets as input a string x∈{0,1}n{\bf x}\in\{0, 1\}^nx∈{0,1}n, and Bob gets a perfect matching M on the n coordinates. Bob's goal is to output a tuple ⟨i,j,b⟩\langle i,j,b \rangle⟨i,j,b⟩ such that the edge (i,j)(i,j)(i,j) belongs to the matching M and b=xi⊕xjb=x_i\oplus x_jb=xi​⊕xj​. We prove that the quantum one-way communication complexity of HMn_nn​ is O(log⁡n)O(\log n)O(logn), yet any randomized one-way protocol with bounded error must use Ω(n)\Omega({\sqrt{n}})Ω(n​) bits of communication. No asymptotic gap for one-way communication was previously known. Our bounds also hold in the model of Simultaneous Messages (SM), and hence we provide the first exponential separation between quantum SM and randomized SM with public coins. For a Boolean decision version of HMn_nn​, we show that the quantum one-way communication complexity remains O(log⁡n)O(\log n)O(logn) and that the 0-error randomized one-way communication complexity is Ω(n)\Omega(n)Ω(n). We prove that any randomized linear one-way protocol with bounded error for this problem requires Ω(nlog⁡n3)\Omega(\sqrt[3]{n \log n})Ω(3nlogn​) bits of communication.
We fully determine the communication complexity of approximating matrix rank, over any finite field F. We study the most general version of this problem, where0⩽r<R⩽n0\leqslant r < R\leqslant n0⩽r<R⩽nare given integers and Alice and Bob need to determine whether their respective matricesA,B∈Fn×nA, B\in \mathbb{F}^{n\times n}A,B∈Fn×nsatisfy rk(A+B)=r(A+B)=r(A+B)=rversus rk(A+B)=R(A+B)=R(A+B)=R. We show that this problem has commu-nication costΩ(r2log⁡∣F∣)\Omega(r^{2}\log\vert \mathbb{F}\vert)Ω(r2log∣F∣), which is optimal. Our lower bound holds even for quantum protocols and even for error probability12(1−∣F∣−r/3)\frac{1}{2}(1-\vert \mathbb{F}\vert ^{-r/3})21​(1−∣F∣−r/3), which too is optimal because this problem has a two-bit classical protocol with error12(1−∣F∣−Θ(r))\frac{1}{2}(1-\vert \mathbb{F}\vert ^{-\Theta(r)})21​(1−∣F∣−Θ(r)). Prior to our work, lower bounds were known only for constant-error protocols and only for consecutive integersrrrandRRR, with no implication for the approximation of matrix rank. We also settle an analogous question for subspaces, where Alice has a subspaceSSS, Bob has a subspaceTTT) and they need to approximate the dimension of the subspaceS+TS+TS+Tgenerated bySSSandTTT(equivalently, approximate the dimension ofS∩TS\cap TS∩T). As an application, we obtain anΩ(n2log⁡∣F∣)/k\Omega(n^{2}\log\vert \mathbb{F}\vert)/kΩ(n2log∣F∣)/kmemory lower bound for any streaming algorithm withkkkpasses that approximates the rank of an input matrixM∈Fn×nM\in \mathbb{F}^{n\times n}M∈Fn×nwithin a factor of2−δ\sqrt{2}-\delta2​−δ, for anyδ>0\delta > 0δ>0. Our result is an exponential improvement inkkkover previous work.
We study an extension of the standard two-party communication model in which Alice and Bob hold probability distributions ppp and qqq over domains XXX and YYY, respectively. Their goal is to estimate Ex∼p, y∼q[f(x,y)] \mathbb{E}_{x \sim p,\, y \sim q}[f(x, y)] Ex∼p,y∼q​[f(x,y)] to within additive error ε\varepsilonε for a bounded function fff, known to both parties. We refer to this as the distributed estimation problem. Special cases of this problem arise in a variety of areas including sketching, databases and learning. Our goal is to understand how the required communication scales with the communication complexity of fff and the error parameter ε\varepsilonε. The random sampling approach -- estimating the mean by averaging fff over O(1/ε2)O(1/\varepsilon^2)O(1/ε2) random samples -- requires O(R(f)/ε2)O(R(f)/\varepsilon^2)O(R(f)/ε2) total communication, where R(f)R(f)R(f) is the randomized communication complexity of fff. We design a new debiasing protocol which improves the dependence on 1/ε1/\varepsilon1/ε to be linear instead of quadratic. Additionally we show better upper bounds for several special classes of functions, including the Equality and Greater-than functions. We introduce lower bound techniques based on spectral methods and discrepancy, and show the optimality of many of our protocols: the debiasing protocol is tight for general functions, and that our protocols for the equality and greater-than functions are also optimal. Furthermore, we show that among full-rank Boolean functions, Equality is essentially the easiest.
We give the first exponential separation between quantum and bounded-error randomized one-way communication complexity. Specifically, we define the Hidden Matching Problem HMn: Alice gets as input a string x ∈ (0, 1)n and Bob gets a perfect matching M on the n coordinates. Bob's goal is to output a tuple [i,j,b] such that the edge (i,j) belongs to the matching M and b = xi ⊕ xj. We prove that the quantum one-way communication complexity of HMn is O(log n), yet any randomized one-way protocol with bounded error must use Ω(√n) bits of communication. No asymptotic gap for one-way communication was previously known. Our bounds also hold in the model of Simultaneous Messages (SM) and hence we provide the first exponential separation between quantum SM and randomized SM with public coins.For a Boolean decision version of HMn, we show that the quantum one-way communication complexity remains O(log n) and that the 0-error randomized one-way communication complexity is Ω(n). We prove that any randomized linear one-way protocol with bounded error for this problem requires Ω(√[3] n log n) bits of communication.
We give a tight lower bound of Omega(\sqrt{n}) for the randomized one-way communication complexity of the Boolean Hidden Matching Problem [BJK04]. Since there is a quantum one-way communication complexity protocol of O(\log n) qubits for this problem, we obtain an exponential separation of quantum and classical one-way communication complexity for partial functions. A similar result was independently obtained by Gavinsky, Kempe, de Wolf [GKdW06]. Our lower bound is obtained by Fourier analysis, using the Fourier coefficients inequality of Kahn Kalai and Linial [KKL88].
Alice and Bob hold complementary halves of the columns of an n×nn\times nn×n matrix of kkk-bit integers and decide whether it is singular over Q\mathbb QQ. Up to constant-factor dimension growth, this partitioned problem is equivalent to additive singularity, where Alice and Bob hold n×nn\times nn×n matrices A,BA,BA,B of kkk-bit integers and test the singularity of A+BA+BA+B over Q\mathbb QQ. We prove a bounded-error quantum lower bound Ω(min⁡{n3/2klog⁡n,n2log⁡(nk)})Ω(\min\{n^{3/2}\sqrt{k\log n},n^2\log(nk)\})Ω(min{n3/2klogn​,n2log(nk)}) and a randomized upper bound O(n2min⁡{k,log⁡(k+log⁡n)})O(n^2\min\{k,\log(k+\log n)\})O(n2min{k,log(k+logn)}). The bounds match at Θ(n2log⁡(nk))Θ(n^2\log(nk))Θ(n2log(nk)) for k≥nlog⁡nk\ge n\log nk≥nlogn. The lower bound holds even under the promise of rank n−1n-1n−1 versus nnn. Its proof combines an integer witness with a local digit encoding, while the upper-bound protocol lifts modular kernel relations using short messages. Bitwise sharing changes how the communication complexity depends on the entry bit length kkk. If Alice and Bob instead hold n×nn\times nn×n matrices A,BA,BA,B of kkk-bit integers and test whether their entrywise bitwise XOR A⊕BA\oplus BA⊕B is singular over Q\mathbb QQ, we prove a quantum lower bound Ω(n2k)Ω(n^2k)Ω(n2k), matching the trivial upper bound. This lower bound holds even under the promise of rank n−1n-1n−1 versus nnn. Our proof uses a dense weighted equation and a signed Fourier witness whose exceptional dyadic frequencies can be removed at small variation cost.