English (United Kingdom)

https://curated-unify.zendy.io/wp-json/zendy-region/v1/featured_content/oa?rat=en

https://curated-unify.zendy.io/wp-json/zendy-region/v1/highlighted_journal/

Global: Zendy Plus annual

Presents the access of premium content as premium feature

Premium Content

Presents the keyphrase highlighting as premium feature

Keyphrase Highlighting

Presents the summarisation as premium feature

Summarisation

Insights

Presents the pdf analysis as premium feature

PDF Analysis

Presents the zaia usage as premium feature

ZAIA

Global: Zendy Tools annual

Global: Zendy Free Plan

Global: Zendy Tools monthly

Global: Zendy Plus monthly

In this work we revisit the Boolean Hidden Matching communication problem,which was the first communication problem in the one-way model to demonstratean exponential classical-quantum communication separation. In this problem,Alice's bits are matched into pairs according to a partition that Bob holds.These pairs are compressed using a Parity function and it is promised that thefinal bit-string is equal either to another bit-string Bob holds, or itscomplement. The problem is to decide which case is the correct one. Here wegeneralize the Boolean Hidden Matching problem by replacing the parity functionwith an arbitrary Boolean function $f$. Efficient communication protocols arepresented depending on the sign-degree of $f$. If its sign-degree is less thanor equal to 1, we show an efficient classical protocol. If its sign-degree isless than or equal to $2$, we show an efficient quantum protocol. We thencompletely characterize the classical hardness of all symmetric functions $f$of sign-degree greater than or equal to $2$, except for one family of specificcases. We also prove, via Fourier analysis, a classical lower bound for anyfunction $f$ whose pure high degree is greater than or equal to $2$. Similarly,we prove, also via Fourier analysis, a quantum lower bound for any function $f$whose pure high degree is greater than or equal to $3$. These results give alarge family of new exponential classical-quantum communication separations.

Exponential quantum communication reductions from generalizations of the Boolean Hidden Matching problem