Nondeterministic quantum communication complexity: The cyclic equality game and iterated matrix multiplication

Research output: Chapter in Book/Report/Conference proceedingArticle in proceedingsResearchpeer-review

Documents

We study nondeterministic multiparty quantum communication with a quantum generalization of broadcasts. We show that, with number-in-hand classical inputs, the communication complexity of a Boolean function in this communication model equals the logarithm of the support rank of the corresponding tensor, whereas the approximation complexity in this model equals the logarithm of the border support rank. This characterisation allows us to prove a log-rank conjecture posed by Villagra et al. for nondeterministic multiparty quantum communication with message passing. The support rank characterization of the communication model connects quantum communication complexity intimately to the theory of asymptotic entanglement transformation and algebraic complexity theory. In this context, we introduce the graphwise equality problem. For a cycle graph, the complexity of this communication problem is closely related to the complexity of the computational problem of multiplying matrices, or more precisely, it equals the logarithm of the support rank of the iterated matrix multiplication tensor. We employ Strassen's laser method to show that asymptotically there exist nontrivial protocols for every odd-player cyclic equality problem. We exhibit an efficient protocol for the 5-player problem for small inputs, and we show how Young flattenings yield nontrivial complexity lower bounds.

Original languageEnglish
Title of host publication8th Innovations in Theoretical Computer Science Conference, ITCS 2017
EditorsChristos H. Papadimitriou
PublisherSchloss Dagstuhl - Leibniz-Zentrum für Informatik
Publication date2017
Pages1-18
Article number24
ISBN (Electronic)9783959770293
DOIs
Publication statusPublished - 2017
Event8th Innovations in Theoretical Computer Science Conference, ITCS 2017 - Berkeley, United States
Duration: 9 Jan 201711 Jan 2017

Conference

Conference8th Innovations in Theoretical Computer Science Conference, ITCS 2017
LandUnited States
ByBerkeley
Periode09/01/201711/01/2017
SponsorSimons Institute for the Theory of Computing
SeriesLeibniz International Proceedings in Informatics, LIPIcs
Volume67
ISSN1868-8969

    Research areas

  • Broadcast Channel, Matrix Multiplication, Number-Inhand, Quantum Communication Complexity, Support Rank

Number of downloads are based on statistics from Google Scholar and www.ku.dk


No data available

ID: 210833678