Quantum Communication Lower Bounds for Search Problems via Matrix Discrepancy
Abstract
We study one-way quantum communication lower bounds for search problems. Unlike decision problems, search problems can have many valid outputs, which pose a fundamental barrier to standard quantum lower-bound techniques. We overcome this by developing a novel method based on matrix discrepancy, which allows us to bound the output measurements of a quantum protocol jointly. As applications of our method, we establish the first tight quantum lower bounds for two fundamental search problems in some natural parameter regimes: collision finding and triangle finding. For collision finding, we prove a tight Ω(N1/4) one-way quantum communication lower bound. Previously, the best-known quantum communication lower bound for collision finding was Ω(N1/12) due to Göös and Jain (RANDOM 2022), and no stronger bound was known even under the one-way restriction. For triangle finding in graph streams, we prove a one-pass quantum streaming space lower bound of Ω(√(ΔV)) for graphs with m edges, Θ(m) triangles, and constant ΔE, where ΔV and ΔE denote the maximum number of triangles sharing a common vertex and edge, respectively, under the condition that 1≤ ΔV≤ m2/3. This constitutes the first nontrivial quantum space lower bound in this regime, matching the classical upper bound of Jayaram and Kallaugher (RANDOM 2021) up to logarithmic factors. Notably, our method also recovers the classical lower bound of Kallaugher and Price (SODA 2017) through an entirely different argument, avoiding their Boolean-Hidden-Matching reduction that breaks down for quantum protocols.
Related
- Tight Communication Bounds for Distributed Algorithms in the Quantum Routing Model
- Quantum lower bounds for convex optimization and real matrix-vector query problems
- Gaussian entanglement and quantum communication: geodesic optimization and multimode bounds
- Quantum Lower Bounds for Collision Problems
- Pauli-ball discrepancy and stability of quantum codes
BibTeX
@misc{gao2026quantum,
title = {{Quantum Communication Lower Bounds for Search Problems via Matrix Discrepancy}},
author = {Minbo Gao and Chenghua Liu and Guangxu Yang and Tianyi Zhang},
howpublished = {arXiv},
year = {2026},
month = oct,
doi = {10.48550/arxiv.2607.08517},
eprint = {2607.08517},
archivePrefix = {arXiv},
url = {https://arxiv.org/abs/2607.08517},
}
RIS
TY - UNPB
TI - Quantum Communication Lower Bounds for Search Problems via Matrix Discrepancy
AU - Minbo Gao
AU - Chenghua Liu
AU - Guangxu Yang
AU - Tianyi Zhang
PY - 2026
DA - 2026/10/04
PB - arXiv
DO - 10.48550/arxiv.2607.08517
UR - https://arxiv.org/abs/2607.08517
AB - We study one-way quantum communication lower bounds for search problems. Unlike decision problems, search problems can have many valid outputs, which pose a fundamental barrier to standard quantum lower-bound techniques. We overcome this by developing a novel method based on matrix discrepancy, which allows us to bound the output measurements of a quantum protocol jointly. As applications of our method, we establish the first tight quantum lower bounds for two fundamental search problems in some natural parameter regimes: collision finding and triangle finding. For collision finding, we prove a tight Ω(N^1/4) one-way quantum communication lower bound. Previously, the best-known quantum communication lower bound for collision finding was Ω(N^1/12) due to Göös and Jain (RANDOM 2022), and no stronger bound was known even under the one-way restriction. For triangle finding in graph streams, we prove a one-pass quantum streaming space lower bound of Ω(√(Δ_V)) for graphs with m edges, Θ(m) triangles, and constant Δ_E, where Δ_V and Δ_E denote the maximum number of triangles sharing a common vertex and edge, respectively, under the condition that 1≤ Δ_V≤ m^2/3. This constitutes the first nontrivial quantum space lower bound in this regime, matching the classical upper bound of Jayaram and Kallaugher (RANDOM 2021) up to logarithmic factors. Notably, our method also recovers the classical lower bound of Kallaugher and Price (SODA 2017) through an entirely different argument, avoiding their Boolean-Hidden-Matching reduction that breaks down for quantum protocols.
ER -