Klauck, Hartmut ;
de Wolf, Ronald
Fooling OneSided Quantum Protocols
Abstract
We use the venerable "fooling set" method to prove new lower bounds on the quantum communication complexity of various functions. Let f : X x Y > {0,1} be a Boolean function, fool^1(f) its maximal fooling set size among 1inputs, Q_1^*(f) its onesidederror quantum communication complexity with prior entanglement, and NQ(f) its nondeterministic quantum communication complexity (without prior entanglement; this model is trivial with shared randomness or entanglement). Our main results are the following, where logs are to base 2:
 If the maximal fooling set is "upper triangular" (which is for instance the case for the equality, disjointness, and greaterthan functions), then we have Q_1^*(f) >= 1/2 log fool^1(f)  1/2, which (by superdense coding) is essentially optimal for functions like equality, disjointness, and greaterthan. No superconstant lower bound for equality seems to follow from earlier techniques.
 For all f we have Q_1^*(f) >= 1/4 log fool^1(f)  1/2.
 NQ(f) >= 1/2 log fool^1(f) + 1. We do not know if the factor 1/2 is needed in this result, but it cannot be replaced by 1: we give an example where NQ(f) \approx 0.613 log fool^1(f).
BibTeX  Entry
@InProceedings{klauck_et_al:LIPIcs:2013:3953,
author = {Hartmut Klauck and Ronald de Wolf},
title = {{Fooling OneSided Quantum Protocols}},
booktitle = {30th International Symposium on Theoretical Aspects of Computer Science (STACS 2013)},
pages = {424433},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {9783939897507},
ISSN = {18688969},
year = {2013},
volume = {20},
editor = {Natacha Portier and Thomas Wilke},
publisher = {Schloss DagstuhlLeibnizZentrum fuer Informatik},
address = {Dagstuhl, Germany},
URL = {http://drops.dagstuhl.de/opus/volltexte/2013/3953},
URN = {urn:nbn:de:0030drops39539},
doi = {10.4230/LIPIcs.STACS.2013.424},
annote = {Keywords: Quantum computing, communication complexity, fooling set, lower bound}
}
2013
Keywords: 

Quantum computing, communication complexity, fooling set, lower bound 
Seminar: 

30th International Symposium on Theoretical Aspects of Computer Science (STACS 2013)

Issue date: 

2013 
Date of publication: 

2013 