2004/12/11 by Hartmut Klauck, Klauck, Hartmut
Computer Science · Physics and Astronomy · #Complexity and Algorithms in Graphs #Computational Complexity (cs.CC) #Cryptography and Data Security #FOS: Computer and information sciences #FOS: Physical sciences #Quantum Computing Algorithms and Architecture #Quantum Physics (quant-ph) #cs.CC #quant-ph
paper · pdf · doi:10.48550/arxiv.quant-ph/0412088
17 pages, appears at FSTTCS '04
arxiv created 2004/12/11 · openalex publication_date 2004/12/11 · arxiv updated 2016/09/08 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
We derive lower bounds for tradeoffs between the communication C and space S for communicating circuits. The first such bound applies to quantum circuits. If for any function f with image Z the multicolor discrepancy of the communication matrix of f is 1/2d, then any bounded error quantum protocol with space S, in which Alice receives some l inputs, Bob r inputs, and they compute f(xi,yj) for the lr pairs of inputs (xi,yj) needs communication C=Ω(lrd log |Z|/S). In particular, n× n-matrix multiplication over a finite field F requires C=Θ(n3log2 |F|/S). We then turn to randomized bounded error protocols, and derive the bound C=Ω(n3/S2) for Boolean matrix multiplication, utilizing a new direct product result for the one-sided rectangle lower bound on randomized communication complexity. This implies a separation between quantum and randomized protocols.