Please use this identifier to cite or link to this item:
|Title:||The complexity of quantum disjointness||Authors:||Klauck, Hartmut||Keywords:||Communication Complexity
Quantum Proof Systems
|Issue Date:||2017||Source:||Klauck, H. (2017). The complexity of quantum disjointness. Leibniz International Proceedings in Informatics, 83, 15-. doi:10.4230/LIPIcs.MFCS.2017.15||Series/Report no.:||Leibniz International Proceedings in Informatics||Abstract:||We introduce the communication problem QNDISJ, short for Quantum (Unique) Non-Disjointness, 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 Vector-in-Subspace and Non-Disjointness 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 n-dimensional sphere of measure 2^-p must contain an ortho-normal set of points of size Omega(n/p). We also study a "small-spaces" version of the problem, and give upper and lower bounds for its randomized complexity that show that the QNDISJ problem is harder than Non-disjointness 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.||URI:||https://hdl.handle.net/10356/89407
|DOI:||http://dx.doi.org/10.4230/LIPIcs.MFCS.2017.15||Rights:||© 2017 Hartmut Klauck; licensed under Creative Commons License CC-BY.||Fulltext Permission:||open||Fulltext Availability:||With Fulltext|
|Appears in Collections:||SPMS Journal Articles|
Items in DR-NTU are protected by copyright, with all rights reserved, unless otherwise indicated.