Renyi-entropic bounds on quantum communication

Abstract

In this article we establish new bounds on the quantum communication complexity of distributed problems. Specifically, we consider the amount of communication that is required to transform a bipartite state into another, typically more entangled, state. We obtain lower bounds in this setting by studying the Renyi entropy of the marginal density matrices of the distributed system. The communication bounds on quantum state transformations also imply lower bounds for the model of communication complexity where the task consists of the the distributed evaluation of a function f(x,y). Our approach encapsulates several known lower bound methods that use the log-rank or the von Neumann entropy of the density matrices involved. The technique is also effective for proving lower bounds on problems involving a promise or for which the "hard" distributions of inputs are correlated. As examples, we show how to prove a nearly tight bound on the bounded-error quantum communication complexity of the inner product function in the presence of unlimited amounts of EPR-type entanglement and a similarly strong bound on the complexity of the shifted quadratic character problem.

16 pages

References in corpus (12)

• Concentrating Partial Entanglement by Local Operations
• Conditions for a class of entanglement transformations
• Substituting Quantum Entanglement for Communication
• Entanglement-assisted local manipulation of pure quantum states
• Separable states are more disordered globally than locally
• Distinguishability and Accessible Information in Quantum Theory
• Embezzling Entangled Quantum States
• Approximate transformations and robust manipulation of bipartite pure state entanglement
• Multiparty Quantum Communication Complexity
• On the communication cost of entanglement transformations
• Lower bounds for quantum communication complexity
• Quantum Entanglement and the Communication Complexity of the Inner Product Function

Cited by in corpus (14)

• Quantum mechanical evolution towards thermal equilibrium
• alpha-z-relative Renyi entropies
• Renyi Entropy and Free Energy
• Quantum state transformations and the Schubert calculus
• Strong converse theorems using Rényi entropies
• New Quantum Algorithms for Computing Quantum Entropies and Distances
• Digital Discovery of 100 diverse Quantum Experiments with PyTheus
• Equilibration of Small and Large Subsystems in Field Theories and Matrix Models
• Tight uniform continuity bound for a family of entropies
• The measurement postulates of quantum mechanics are not redundant
• A strong converse for the quantum state merging protocol
• Quantum channels and some absolute properties of quantum states
• Entropies and IPR as Markers for a Phase Transition in a Two-Level Model for Atom-Diatomic Molecule Coexistence
• Sketching and Streaming Entropy via Approximation Theory