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.
Rights: © 2017 Hartmut Klauck; licensed under Creative Commons License CC-BY.
Fulltext Permission: open
Fulltext Availability: With Fulltext
Appears in Collections:SPMS Journal Articles

Files in This Item:
File Description SizeFormat 
The complexity of quantum disjointness.pdf431.94 kBAdobe PDFThumbnail

Google ScholarTM



Items in DR-NTU are protected by copyright, with all rights reserved, unless otherwise indicated.