{"id":"arxiv/2607.08517","url":"https://arxiv.org/abs/2607.08517","tags":["quant-ph"],"score":0,"title":"Quantum Communication Lower Bounds for Search Problems via Matrix Discrepancy","domain":"quant-ph","source":"arxiv","authors":["Minbo Gao","Chenghua Liu","Guangxu Yang","Tianyi Zhang"],"reviews":0,"subject":"quant-ph","summary":"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…","category":"research","comments":0,"disputed":false,"division":"physics","mentions":0,"discussed":0,"published":"2026-07-09","reactions":{}}