Jul 26, 2016
Quantum Advantage on Information Leakage for Equality
Posted by Karen Hurst in categories: computing, quantum physics
Abstract: 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.
Continue reading “Quantum Advantage on Information Leakage for Equality” »