Quantum Communication Lower Bounds for Search Problems via Matrix Discrepancy
The paper introduces a novel measurement-discrepancy method to establish one-way quantum communication lower bounds for search problems. By analyzing Bob's quantum strategy through positive operator-valued measures (POVMs) and matrix discrepancy estimates, the method yields tight bounds for collision finding and triangle finding, matching classical upper limits in certain regimes.