Showing quant-phShow all
3 papers · 1 filter
quant-ph2026
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…
quant-ph2026
Exponential Separation of Quantum and Classical One-Way Numbers-on-Forehead Communication
Guangxu Yang, Jiapeng Zhang
Numbers-on-Forehead (NOF) communication model is a central model in communication complexity. As a restricted variant, one-way NOF model is of particular interest. Establishing str…
quant-ph2025
Quantum versus Classical Separation in Simultaneous Number-on-Forehead Communication
Guangxu Yang, Jiapeng Zhang
Quantum versus classical separation plays a central role in understanding the advantages of quantum computation. In this paper, we present the first exponential separation between…