Characterizing Quantum Advantage for Generalizations of the Boolean Hidden Matching Problem

Mark Bun, Joao F. Doriguello, John Kallaugher +1

We study the one-way communication complexity of the $f$-Boolean Hidden Partition problem. Here, Alice is given an $n$-bit string and Bob is given $\Omega (n)$ disjoint blocks of its ind…