It has long been known that the existence of certain superquantum nonlocal correlations would cause communication complexity to collapse. The absurdity of a world in which any function could be evaluated by two players with a constant amount of communication in turn provides a tantalizing way to distinguish quantum mechanics from incorrect theories of physics; the statement “communication complexity is nontrivial” has even been conjectured to be a concise information-theoretic axiom for characterizing quantum mechanics. We directly address the viability of that perspective with two results. First, we exhibit a nonlocal game such that communication complexity collapses in any physical theory whose maximal winning probability exceeds the quantum value. Second, we consider the venerable CHSH game that initiated this line of inquiry. In that case, the quantum value is about 0.85 but it is known that a winning probability of approximately 0.91 would collapse communication complexity. We show that the 0.91 result is the best possible using a large class of proof strategies, suggesting that the communication complexity axiom is insufficient for characterizing CHSH correlations. Both results build on new insights about reliable classical computation. The first exploits our formalization of an equivalence between amplification and reliable computation, while the second follows from a rigorous determination of the threshold for reliable computation with formulas of noise-free XOR gates and noisy AND gates.
It has long been known that the existence of certain superquantum nonlocal correlations would cause communication complexity to collapse. The absurdity of a world in which any function could be evaluated by two players with a constant amount of communication in turn provides a tantalizing way to distinguish quantum mechanics from incorrect theories of physics; the statement “communication complexity is nontrivial” has even been conjectured to be a concise information-theoretic axiom for characterizing quantum mechanics. We directly address the viability of that perspective with two results. First, we exhibit a nonlocal game such that communication complexity collapses in any physical theory whose maximal winning probability exceeds the quantum value. Second, we consider the venerable CHSH game that initiated this line of inquiry. In that case, the quantum value is about 0.85 but it is known that a winning probability of approximately 0.91 would collapse communication complexity. We show that the 0.91 result is the best possible using a large class of proof strategies, suggesting that the communication complexity axiom is insufficient for characterizing CHSH correlations. Both results build on new insights about reliable classical computation. The first exploits our formalization of an equivalence between amplification and reliable computation, while the second follows from a rigorous determination of the threshold for reliable computation with formulas of noise-free XOR gates and noisy AND gates.
We study the impact of noise on the theories of quantum nonlocality and entanglement-assisted communication complexity. We consider non-local games and entanglement-assisted communication complexity in a model where Alice and Bob may share arbitrarily many noisy EPR pairs. We study four noise models: depolarizing noise, unital noise, biased reset noise, and erasure noise. Our results are as follows:
1. We upper bound the value of the CHSH game under all these noise models in terms of the noise parameter, without any assumptions on the measurements used in the strategy.
2. We prove a parallel repetition theorem for general non-local games under all noise models except biased reset noise; we prove an improved parallel repetition theorem for unique games. Our parallel repetition rate is smaller than the quantum parallel repetition rate for CHSH in a nontrivial noise regime.
3. Using our unique-game parallel repetition theorem and a relation defined by the CHSH game, we prove a separation between communication complexity with noisy vs noiseless entanglement. This implies an Ω(n) two-way communication lower bound for distilling n EPR pairs from noisy EPR pairs, in the same nontrivial noise regime.
4. We show that any interactive entanglement-assisted communication protocol can be simulated by an SMP communication protocol with noisy shared randomness, with an exponential blowup in communication. This generalizes a known result on the simulation of noiseless shared randomness with noisy shared randomness.
5. We show a polynomial lower bound on the number of copies of noisy EPR pairs required to compute the Equality function with constant communication, under all four noise models. The previous result gives a matching upper bound, and moreover, this answers an open question in the literature on whether logarithmically many noisy shared bits suffice for communication.
The main objective of this paper is to provide illustrative examples of distributed computing problems for which it is possible to design tight lower bounds for quantum algorithms without having to manipulate concepts from quantum mechanics, at all. As a case study, we address the following class of 2-player problems. Alice (resp., Bob) receives a boolean x (resp., y) as input, and must return a boolean a (resp., b) as output. A game between Alice and Bob is defined by a pair (?, f) of boolean functions. The objective of Alice and Bob playing game (?, f) is, for every pair (x, y) of inputs, to output values a and b, respectively, satisfying ?(a, b) = f(x, y), in absence of any communication between the two players, but in presence of shared resources. The ability of the two players to solve the game then depends on the type of resources they share. It is known that, for the so-called CHSH game, i.e., for the game a ? b = x ? y, the ability for the players to use entangled quantum bits (qubits) helps. We show that, apart from the CHSH game, quantum correlations do not help, in the sense that, for every game not equivalent to the CHSH game, there exists a classical protocol (using shared randomness) whose probability of success is at least as large as the one of any protocol using quantum resources. This result holds for both worst case and average case analysis. It is achieved by considering a model stronger than quantum correlations, the non-signaling model, which subsumes quantum mechanics, but is far easier to handle.
This thesis explores foundational aspects of quantum information theory and quantum cryptography. First, we investigate quantum correlations in interactive settings, including the CHSH and graph isomorphism games. We aim to distinguish quantum correlations from non-signaling correlations by leveraging the principle of communication complexity. To this end, we employ techniques such as distributed computation, majority-function-based distillation protocols, the algebraic and geometric properties of nonlocal box wirings, and variations of some graph properties such as isomorphism, transitivity, and equitable partitions. This inquiry advances our understanding of non-physical correlations. Second, we address a key open problem in cryptography: the feasibility of unclonable encryption. We aim to construct an encryption scheme that prevents two distant parties from simultaneously obtaining information about a shared encrypted message. We introduce a candidate for unclonable encryption in the plain model, i.e., without assumptions, in working towards an unconditional proof. Our protocol is based on Clifford algebra, utilizing complex Hermitian unitary matrices that anti-commute. For small key sizes, we rigorously prove security using sum-of-squares methods, while for larger key sizes, we provide strong numerical evidence via the NPA hierarchy.
This thesis explores foundational aspects of quantum information theory and quantum cryptography. First, we investigate quantum correlations in interactive settings, including the CHSH and graph isomorphism games. We aim to distinguish quantum correlations from non-signaling correlations by leveraging the principle of communication complexity. To this end, we employ techniques such as distributed computation, majority-function-based distillation protocols, the algebraic and geometric properties of nonlocal box wirings, and variations of some graph properties such as isomorphism, transitivity, and equitable partitions. This inquiry advances our understanding of non-physical correlations. Second, we address a key open problem in cryptography: the feasibility of unclonable encryption. We aim to construct an encryption scheme that prevents two distant parties from simultaneously obtaining information about a shared encrypted message. We introduce a candidate for unclonable encryption in the plain model, i.e. without assumptions, in working towards an unconditional proof. Our protocol is based on Clifford algebra, utilizing complex Hermitian unitary matrices that anti-commute. For small key sizes, we rigorously prove security using sum-of-squares methods, while for larger key sizes, we provide strong numerical evidence via the NPA hierarchy.
Abstract This paper considers the decidability of fully quantum nonlocal games with noisy maximally entangled states. Fully quantum nonlocal games are a generalization of nonlocal games, where both questions and answers are quantum and the referee performs a binary POVM measurement to decide whether they win the game after receiving the quantum answers from the players. The quantum value of a fully quantum nonlocal game is the supremum of the probability that they win the game, where the supremum is taken over all the possible entangled states shared between the players and all the valid quantum operations performed by the players. The seminal work MIP∗=RE~\cite{JNVWY'20,JNVWYuen'20} implies that it is undecidable to approximate the quantum value of a fully nonlocal game. This still holds even if the players are only allowed to share (arbitrarily many copies of) maximally entangled states. This paper investigates the case that the shared maximally entangled states are noisy. We prove that there is a computable upper bound on the copies of noisy maximally entangled states for the players to win a fully quantum nonlocal game with a probability arbitrarily close to the quantum value. This implies that it is decidable to approximate the quantum values of these games. Hence, the hardness of approximating the quantum value of a fully quantum nonlocal game is not robust against the noise in the shared states. This paper is built on the framework for the decidability of non-interactive simulations of joint distributions~\cite{7782969,doi:10.1137/1.9781611975031.174,Ghazi:2018:DRP:3235586.3235614} and generalizes the analogous result for nonlocal games in~\cite{qin2021nonlocal}. We extend the theory of Fourier analysis to the space of super-operators and prove several key results including an invariance principle and a dimension reduction for super-operators. These results are interesting in their own right and are believed to have further applications.
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.