Quantum Communication Lower Bounds for Search Problems via Matrix Discrepancy

Minbo Gao, Chenghua Liu, Guangxu Yang +1

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…