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

TY - GEN

T1 - Nondeterministic quantum communication complexity

T2 - 8th Innovations in Theoretical Computer Science Conference, ITCS 2017

AU - Buhrman, Harry

AU - Christandl, Matthias

AU - Zuiddam, Jeroen

PY - 2017

Y1 - 2017

N2 - 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.

AB - 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.

KW - Broadcast Channel

KW - Matrix Multiplication

KW - Number-Inhand

KW - Quantum Communication Complexity

KW - Support Rank

UR - http://www.scopus.com/inward/record.url?scp=85038565093&partnerID=8YFLogxK

U2 - 10.4230/LIPIcs.ITCS.2017.24

DO - 10.4230/LIPIcs.ITCS.2017.24

M3 - Article in proceedings

AN - SCOPUS:85038565093

T3 - Leibniz International Proceedings in Informatics, LIPIcs

SP - 1

EP - 18

BT - 8th Innovations in Theoretical Computer Science Conference, ITCS 2017

A2 - Papadimitriou, Christos H.

PB - Schloss Dagstuhl - Leibniz-Zentrum für Informatik

Y2 - 9 January 2017 through 11 January 2017

ER -