Quantum 2025 – wissenschaftliches Programm
Bereiche | Tage | Auswahl | Suche | Aktualisierungen | Downloads | Hilfe
THU: Thursday Contributed Sessions
THU 7: Entanglement and Complexity: Contributed Session to Symposium II
THU 7.3: Vortrag
Donnerstag, 11. September 2025, 14:45–15:00, ZHG008
Communication Complexity Bounds using Information Causality — •Prabhav Jain1, Nikolai Miklin2, and Mariami Gachechiladze1 — 1Technische Universität Darmstadt — 2Technische Universität Hamburg
In a distributed computing scenario, two parties (say Alice and Bob) aim to compute a given function with as minimum communication as possible. The communication cost or the complexity depends not only on the function itself but the shared resources to which both parties have access to such as public randomness or entangled Bell pairs. In this work, we aim to study communication complexity in theories satisfying the information causality principle. The principle essentially states that the information potentially available to Bob about Alice's data cannot be higher than the amount of information Alice sends to Bob. We formulate an extension of the information causality principle which is valid for any distributed computation scenario and apply it to several well known functions. We show a reduction for some of these problems to known functions and hence derive one-way communication complexity bounds in a theory independent manner. Finally, we prove that the information causality principle is at least as strong as the principle of non-trivial communication complexity.
Keywords: communication complexity; nonlocality; quantum correlations; physical principle; quantum foundations