Quantum Information Complexity and Amortized Communication

Abstract

We define a new notion of information cost for quantum protocols, and a corresponding notion of quantum information complexity for bipartite quantum channels, and then investigate the properties of such quantities. These are the fully quantum generalizations of the analogous quantities for bipartite classical functions that have found many applications recently, in particular for proving communication complexity lower bounds. Our definition is strongly tied to the quantum state redistribution task. Previous attempts have been made to define such a quantity for quantum protocols, with particular applications in mind; our notion differs from these in many respects. First, it directly provides a lower bound on the quantum communication cost, independent of the number of rounds of the underlying protocol. Secondly, we provide an operational interpretation for quantum information complexity: we show that it is exactly equal to the amortized quantum communication complexity of a bipartite channel on a given state. This generalizes a result of Braverman and Rao to quantum protocols, and even strengthens the classical result in a bounded round scenario. Also, this provides an analogue of the Schumacher source compression theorem for interactive quantum protocols, and answers a question raised by Braverman. We also discuss some potential applications to quantum communication complexity lower bounds by specializing our definition for classical functions and inputs. Building on work of Jain, Radhakrishnan and Sen, we provide new evidence suggesting that the bounded round quantum communication complexity of the disjointness function is Ω(n/M + M), for M-message protocols. This would match the best known upper bound.

v1, 38 pages, 1 figure

References in corpus (11)

• Substituting Quantum Entanglement for Communication
• Authentication of Quantum Messages
• The mother of all protocols: Restructuring quantum information's family tree
• Faithful Squashed Entanglement
• Embezzling Entangled Quantum States
• The exact cost of redistributing multipartite quantum states
• Optimal quantum source coding with quantum information at the encoder and decoder
• Renyi generalizations of the conditional quantum mutual information
• Lower bounds on information complexity via zero-communication protocols and applications
• Information Equals Amortized Communication
• A lower bound for bounded round quantum communication complexity of set disjointness

Cited by in corpus (7)

• Quantum conditional mutual information and approximate Markov chains
• Renyi generalizations of the conditional quantum mutual information
• Approximate reversibility in the context of entropy gain, information gain, and complete positivity
• The Fidelity of Recovery is Multiplicative
• Rényi generalizations of quantum information measures
• Privacy in Quantum Communication Complexity
• Direct Sum Theorem for Bounded Round Quantum Communication Complexity