Communication complexity bounds from information causality

• URL: http://arxiv.org/abs/2602.10206v1
• Date: Tue, 10 Feb 2026 19:01:02 GMT
• Title: Communication complexity bounds from information causality
• Authors: Nikolai Miklin, Prabhav Jain, Mariami Gachechiladze,
• Abstract summary: Communication complexity quantifies the minimum communication required for distributed computation.<n>We introduce an information-theoretic approach to study one-way communication complexity based solely on the axioms of mutual information.<n>We prove that the extended information causality principle is at least as strong as the principle of non-trivial communication complexity.
• Score: 0.0
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: Communication complexity, which quantifies the minimum communication required for distributed computation, offers a natural setting for investigating the capabilities and limitations of quantum mechanics in information processing. We introduce an information-theoretic approach to study one-way communication complexity based solely on the axioms of mutual information. Within this framework, we derive an extended statement of the information causality principle, which recovers known lower bounds on the communication complexities for a range of functions in a simplified manner and leads to new results. We further prove that the extended information causality principle is at least as strong as the principle of non-trivial communication complexity in bounding the strength of quantum correlations attainable in Bell experiments. Our study establishes a new route for exploring the fundamental limits of quantum technologies from an information-theoretic viewpoint.

Related papers

• The Silence that Speaks: Neural Estimation via Communication Gaps [1.7332551623907755]
  CALM is a novel learning-based framework that jointly addresses the dual challenges of communication scheduling and estimator design.<n>We show that CALM is able to decode the implicit coordination between the estimator and the scheduler to extract information from the instances of'silence' and enhance the estimation accuracy.
  arXiv  Detail & Related papers  (2025-11-30T19:58:21Z)
• Structure-Fair Quantum Circuit Complexity: An Auditable Information-Theoretic Lower Bound [0.2606834301724095]
  This paper introduces the Reference-Contingent Complexity (RCC), an information-theoretic measure calibrated by the available quantum operations.<n>Our central result is a key theorem that rigorously proves the RCC serves as a lower bound for the complexity of any universal quantum circuit.<n>This work provides a "ruler" for quantum technology that is structure-fair and enables cross-platform comparison.
  arXiv  Detail & Related papers  (2025-09-20T14:58:34Z)
• Quantum-Accelerated Wireless Communications: Concepts, Connections, and Implications [59.0413662882849]
  Quantum computing is poised to redefine the algorithmic foundations of communication systems.<n>This article outlines the fundamentals of quantum computing in a style familiar to the communications society.<n>We highlight a mathematical harmony between quantum and wireless systems, which makes the topic more enticing to wireless researchers.
  arXiv  Detail & Related papers  (2025-06-25T22:25:47Z)
• Quantum Information Processing, Sensing and Communications: Their Myths, Realities and Futures [61.25494706587422]
  The state-of-the-art, knowledge gaps and future evolution of quantum machine learning are discussed.<n>We conclude with a set of promising future research ideas in the field of ultimately secure quantum communications.
  arXiv  Detail & Related papers  (2024-12-01T22:28:02Z)
• On the Complexity of Quantum Field Theory [0.0]
  We show that from minimal assertions, one is naturally led to measure complexity by two integers, called format and degree.<n>We discuss the physical interpretation of our approach in the context of perturbation theory, symmetries, and the renormalization group.
  arXiv  Detail & Related papers  (2024-10-30T18:00:00Z)
• Separable Power of Classical and Quantum Learning Protocols Through the Lens of No-Free-Lunch Theorem [70.42372213666553]
  The No-Free-Lunch (NFL) theorem quantifies problem- and data-independent generalization errors regardless of the optimization process. We categorize a diverse array of quantum learning algorithms into three learning protocols designed for learning quantum dynamics under a specified observable. Our derived NFL theorems demonstrate quadratic reductions in sample complexity across CLC-LPs, ReQu-LPs, and Qu-LPs. We attribute this performance discrepancy to the unique capacity of quantum-related learning protocols to indirectly utilize information concerning the global phases of non-orthogonal quantum states.
  arXiv  Detail & Related papers  (2024-05-12T09:05:13Z)
• Unbounded quantum advantage in communication complexity measured by distinguishability [0.0]
  We measure the complexity of a task by the minimal distinguishability required to accomplish it.<n>We show that the classical-to-quantum ratio of minimal distinguishability required to achieve the same success metric escalates exponentially.
  arXiv  Detail & Related papers  (2024-01-23T16:48:59Z)
• An operational definition of quantum information scrambling [0.0]
  Quantum information scrambling (QIS) is a characteristic feature of several quantum systems. We propose a novel and computationally efficient QIS quantifier based on a formulation of QIS in terms of quantum state discrimination. We show that the optimal guessing probability, which reflects the degree of QIS induced by an isometric quantum evolution, is directly connected to the accessible min-information.
  arXiv  Detail & Related papers  (2023-12-18T19:00:01Z)
• Quantum Semantic Communications for Resource-Efficient Quantum Networking [52.3355619190963]
  This letter proposes a novel quantum semantic communications (QSC) framework exploiting advancements in quantum machine learning and quantum semantic representations. The proposed framework achieves approximately 50-75% reduction in quantum communication resources needed, while achieving a higher quantum semantic fidelity.
  arXiv  Detail & Related papers  (2022-05-05T03:49:19Z)
• Entanglement in prepare-and-measure scenarios: many questions, a few answers [0.0]
  Entanglement and quantum communication are paradigmatic resources in quantum information science. Correlations due to entanglement when communication is absent have been studied in Bell scenarios. We focus on entanglement-assisted prepare-and-measure scenarios.
  arXiv  Detail & Related papers  (2021-08-01T12:22:00Z)
• Quantum communication complexity beyond Bell nonlocality [87.70068711362255]
  Efficient distributed computing offers a scalable strategy for solving resource-demanding tasks. Quantum resources are well-suited to this task, offering clear strategies that can outperform classical counterparts. We prove that a new class of communication complexity tasks can be associated to Bell-like inequalities.
  arXiv  Detail & Related papers  (2021-06-11T18:00:09Z)
• Tracing Information Flow from Open Quantum Systems [52.77024349608834]
  We use photons in a waveguide array to implement a quantum simulation of the coupling of a qubit with a low-dimensional discrete environment. Using the trace distance between quantum states as a measure of information, we analyze different types of information transfer.
  arXiv  Detail & Related papers  (2021-03-22T16:38:31Z)

This list is automatically generated from the titles and abstracts of the papers in this site.

This site does not guarantee the quality of this site (including all information) and is not responsible for any consequences.