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.
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.
Quantum mechanics has been a paradigm shift and a revolutionary framework in our understanding of the physical world. The theory has been able to describe a wide variety of phenomena and has been experimentally verified with great precision. Despite that, to this day, the seemingly ad hoc formulation of quantum theory and several of its features still elude an intuitive understanding. At the same time, the applications of quantum mechanics in information theory have emerged as a promising avenue. Namely, its potential advantages in computation, in the so-called nascent field of quantum computation and in communication and information processing tasks such as quantum teleportation and super-dense coding. In all these endeavours, a significant effort has been made in understanding the maximum extent to which quantum mechanics can provide an advantage. This thesis explores an intersection of these two research lines, i.e. to have a physical explanation of some of the features of quantum mechanics and at the same time, study the outer limits of quantum mechanics. The combining insight rests on a newer foundational idea: that information itself is physical rather than an abstract entity and thus, is subject to physical laws. In this thesis, we explore the principle of information causality, which states that in any communication scenario, the amount of information carried is bounded by the degrees of freedom of the carrier. Information causality was initially proposed as a physical principle aimed at deriving the predictions of quantum mechanics on the type of correlations observed in a Bell scenario, which is a communication scenario involving multiple parties with access to a shared randomness resource. This principle has been proposed to recover some of the well-known features of quantum mechanics, specifically Tsirelson’s bound of the Clauser-Horne-Shimony-Holt inequality. Earlier results found limited generalisations due to the difficulty of deducing implications of the information causality principle. In this thesis, we greatly expand the scope of applicability of the principle. We develop a general-purpose algorithm to derive constraints on the set of quantum correlations. We extend the principle to be applicable to a wider variety of Bell scenarios, derive new families of quantum Bell inequalities and prove new bounds on the success probabilities of Entanglement Assisted Random Access Codes. We introduce an extension of the principle which applies to any distributed computing scenario. Using this extension, we improve on several previously known results in the field, and in certain cases, we even recover part of the quantum set as well. This extension provides rich insights into the communication complexity of distributed functions, using which we prove theory-independent randomised communication complexity bounds for several well-known functions and provide another general-purpose algorithm to bound the randomised quantum communication complexity of any function. As a consequence of the extension, we also establish that the extension supersedes the principle of non-trivial communication complexity.
Information causality (IC) was introduced as a physical principle constraining correlations in non-signaling theories. Whether it can recover the exact quantum correlation boundary, beyond Uffink's inequality, has remained an open question. Here, we combine its generalized formulation for correlated inputs with a new communication protocol to derive quantum Bell inequalities that exactly characterize the quantum correlations in the simplest bipartite Bell scenario, with two binary measurements. In particular, we derive the Tsirelson-Landau-Masanes criterion directly from IC. Thus, the generalized IC implies macroscopic locality, while we also present macroscopically local correlations that violate the generalized IC. This establishes that generalized IC is a strictly stronger principle in this scenario. Together with our earlier result that generalized IC implies a nontrivial communication complexity principle, these findings strengthen the role of information causality in explaining the limits of quantum nonlocality and provide a systematic route to deriving tighter bounds on the set of quantum correlations in more general Bell scenarios.
Information causality was initially proposed as a physical principle aimed at deriving the predictions of quantum mechanics on the type of correlations observed in the Bell experiment. In the same work, information causality was famously shown to imply the Uffink inequality that approximates the set of quantum correlations and rederives Tsirelson's bound of the Clauser-Horne-Shimony-Holt inequality. This result found limited generalizations due to the difficulty of deducing implications of the information causality principle on the set of nonlocal correlations. In this paper, we present a simple technique for obtaining polynomial inequalities from information causality, bounding the set of physical correlations in any Bell scenario. To demonstrate our method, we derive a family of inequalities which non-trivially constrains the set of nonlocal correlations in Bell scenarios with binary outcomes and equal number of measurement settings. Finally, we propose an improved statement of the information causality principle, obtain tighter constraints for the simplest Bell scenario that goes beyond the Uffink inequality, and recovers a part of the boundary of the quantum set.
Information Causality was introduced as a physical principle for constraining the set of nonlocal correlations. In recent work, we proposed an extension of Information Causality that allows correlations among Alice's inputs. This extended principle yields tighter constraints than the original formulation and recovers part of the quantum boundary in certain Bell scenarios. In this work, we further investigate the implications of extended Information Causality and apply it to scenarios beyond binary inputs and outputs. We derive a family of quantum Bell inequalities that strengthen previously known constraints on quantum correlations. Using these inequalities, we obtain an improved analytical bound for the Collins-Gisin family of Bell inequalities. We also apply Information Causality to entanglement-assisted random access codes and derive new theory-independent analytical bounds on the winning probability. For this latter task, we prove that, despite being stronger in general, the extended principle does not improve the bounds obtained from the original Information Causality principle. This suggests that the existing Information Causality bounds are optimal for this class of random access codes.
Bell's theorem asserts that no local hidden variable theory can explain the predictions of quantum theory in an experiment where spacelike separated measurements are performed in distant laboratories. Loophole-free Bell tests performed in the last decade demonstrate Bell nonlocality as a property of Nature. However, the amount of nonlocality allowed in quantum theory is limited, compared to the sole restriction of no-signaling, meaning the impossibility of faster-than-light communication implied by special relativity. Information causality is a physical principle that generalizes no-signaling and is satisfied by quantum theory. It is based on the idea that shared quantum entanglement cannot enable a receiver to obtain more classical information than how much was sent by a distant sender. Remarkably, the principle was shown to imply the maximal quantum bound for the violation of the most well-known Bell inequality. The aim of this thesis is to widen our understanding of information causality and compare its predictions with other known outer approximations of the quantum set of correlations. We build upon the recent realization that most of the known consequences of information causality can be derived with a single copy of the shared systems, whereas before it was thought that many copies were necessary. We develop a novel optimization framework which bounds the possible violations of information causality by other sets of correlations, allowing us to certify when violations are not possible. We generalize the statement of information causality and reach a precise definition for the set of correlations satisfying this principle. We show that when searching for violations of information causality by physical theories, considering many copies is not necessary. Our aforementioned optimization framework approximates the information causality set from the outside. Conversely, we propose a different approach which allows us to approximate this set from the inside.
Information causality (IC) posits that communicating m classical bits cannot give the receiver access to more than m bits of information about the sender's independent data. Although IC holds in quantum theory and excludes a broad class of supra-quantum correlations, its validity for the almost-quantum set has remained open. This semidefinite relaxation of the quantum set satisfies nontrivial communication complexity, no advantage for non-local computation, macroscopic locality, local orthogonality, and numerical evidence has suggested that it may also satisfy IC. Here we show that almost-quantum correlations violate IC, and do so without bound. Unlike earlier violations of IC, which rely on biased guesses, ours is driven by zero-error certificates: each is rare but never wrong, carries information linear in its probability, and vouches for many of the sender's bits at once. This establishes a sharp dichotomy: either IC is a valid physical principle that excludes these correlations, or any nonsignalling theory realizing them admits no mutual information obeying consistency, data processing and the chain rule. In the latter case, we discuss why the chain rule is the natural property to relinquish, and how this possibility relates to histories-based formulations and to locality defined relative to the state rather than presupposed in a fixed spacetime.