Abstract
We introduce the communication problem QNDISJ, short for Quantum (Unique) NonDisjointness, and study its complexity under different modes of communication complexity. The main motivation for the problem is that it is a candidate for the separation of the quantum communication complexity classes QMA and QCMA. The problem generalizes the VectorinSubspace and NonDisjointness problems. We give tight bounds for the QMA, quantum, randomized communication complexities of the problem. We show polynomially related upper and lower bounds for the MA complexity. We also show an upper bound for QCMA protocols, and show that the bound is tight for a natural class of QCMA protocols for the problem. The latter lower bound is based on a geometric lemma, that states that every subset of the ndimensional sphere of measure 2^p must contain an orthonormal set of points of size Omega(n/p).
We also study a "smallspaces" version of the problem, and give upper and lower bounds for its randomized complexity that show that the QNDISJ problem is harder than Nondisjointness for randomized protocols. Interestingly, for quantum modes the complexity depends only on the dimension of the smaller space, whereas for classical modes the dimension of the larger space matters.
BibTeX  Entry
@InProceedings{klauck:LIPIcs:2017:8101,
author = {Hartmut Klauck},
title = {{The Complexity of Quantum Disjointness}},
booktitle = {42nd International Symposium on Mathematical Foundations of Computer Science (MFCS 2017)},
pages = {15:115:13},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {9783959770460},
ISSN = {18688969},
year = {2017},
volume = {83},
editor = {Kim G. Larsen and Hans L. Bodlaender and JeanFrancois Raskin},
publisher = {Schloss DagstuhlLeibnizZentrum fuer Informatik},
address = {Dagstuhl, Germany},
URL = {http://drops.dagstuhl.de/opus/volltexte/2017/8101},
URN = {urn:nbn:de:0030drops81010},
doi = {10.4230/LIPIcs.MFCS.2017.15},
annote = {Keywords: Communication Complexity, Quantum Proof Systems}
}
Keywords: 

Communication Complexity, Quantum Proof Systems 
Seminar: 

42nd International Symposium on Mathematical Foundations of Computer Science (MFCS 2017) 
Issue Date: 

2017 
Date of publication: 

22.11.2017 