Abstract
In this work we revisit the Boolean Hidden Matching communication problem, which was the first communication problem in the oneway model to demonstrate an exponential classicalquantum 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 the final bitstring is equal either to another bitstring Bob holds, or its complement. The problem is to decide which case is the correct one. Here we generalize the Boolean Hidden Matching problem by replacing the parity function with an arbitrary function f. Efficient communication protocols are presented depending on the signdegree of f. If its signdegree is less than or equal to 1, we show an efficient classical protocol. If its signdegree is less than or equal to 2, we show an efficient quantum protocol. We then completely characterize the classical hardness of all symmetric functions f of signdegree greater than or equal to 2, except for one family of specific cases. We also prove, via Fourier analysis, a classical lower bound for any function 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 a large family of new exponential classicalquantum communication separations.
BibTeX  Entry
@InProceedings{doriguello_et_al:LIPIcs:2020:12060,
author = {Jo{\~a}o F. Doriguello and Ashley Montanaro},
title = {{Exponential Quantum Communication Reductions from Generalizations of the Boolean Hidden Matching Problem}},
booktitle = {15th Conference on the Theory of Quantum Computation, Communication and Cryptography (TQC 2020)},
pages = {1:11:16},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {9783959771467},
ISSN = {18688969},
year = {2020},
volume = {158},
editor = {Steven T. Flammia},
publisher = {Schloss DagstuhlLeibnizZentrum f{\"u}r Informatik},
address = {Dagstuhl, Germany},
URL = {https://drops.dagstuhl.de/opus/volltexte/2020/12060},
URN = {urn:nbn:de:0030drops120601},
doi = {10.4230/LIPIcs.TQC.2020.1},
annote = {Keywords: Communication Complexity, Quantum Communication Complexity, Boolean Hidden Matching Problem}
}
Keywords: 

Communication Complexity, Quantum Communication Complexity, Boolean Hidden Matching Problem 
Collection: 

15th Conference on the Theory of Quantum Computation, Communication and Cryptography (TQC 2020) 
Issue Date: 

2020 
Date of publication: 

08.06.2020 