Characterizing Quantum Advantage for Generalizations of the Boolean Hidden Matching ProblemResearch Paper
One-way communication complexity asks how much information Alice must send when Bob has a different input and must decide a joint property. It provides a setting in which classical and quantum information can be compared without imposing restrictions on local computation. The Boolean Hidden Matching problem is an established example: a short quantum message…