2016/07/26 by Juan Miguel Arrazola, Arrazola, Juan Miguel, Dave Touchette +1 · 1 citation
Computer Science · Engineering · Physics and Astronomy · #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) #Wireless Communication Security Techniques #cs.CC #quant-ph
paper · pdf · doi:10.48550/arxiv.1607.07516
23 pages, 2 figures
arxiv created 2016/07/26 · openalex publication_date 2016/07/26 · arxiv updated 2016/07/27 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
We prove a lower bound on the information leakage of any classical protocol computing the equality function in the simultaneous message passing (SMP) model. Our bound is valid in the finite length regime and is strong enough to demonstrate a quantum advantage in terms of information leakage for practical quantum protocols. We prove our bound by obtaining an improved finite size version of the communication bound due to Babai and Kimmel, relating randomized communication to deterministic communication in the SMP model. We then relate information leakage to randomized communication through a series of reductions. We first provide alternative characterizations for information leakage, allowing us to link it to average length communication while allowing for shared randomness (pairwise, with the referee). A Markov inequality links this with bounded length communication, and a Newman type argument allows us to go from shared to private randomness. The only reduction in which we incur more than a logarithmic additive factor is in the Markov inequality; in particular, our compression method is essentially tight for the SMP model with average length communication.