This thesis studies the consequences of 'super-quantum non-local correlations', which are hypothetical violations of Bell/CHSH inequalities that are stronger - more nonlocal - than quantum mechanics allows, yet weak enough to respect special relativity in prohibiting faster-than-light communication. Understanding the power of such correlations will yield insight into the non-locality of quantum mechanics. Whereas previous studies of super-quantum correlations have demonstrated enhancements in cryptography and computation of distributed functions, this work opens up a new direction of research by showing that they can also enhance the capacity of classical communication over a noisy channel. Our results exhibit a trifecta of proof-of-concept channels: first, we show an interference channel between two sender-receiver pairs where the senders are not allowed to communicate, for which a shared super-quantum bit allows perfect classical communication. This feat is not achievable with the best classical (senders share no resources) or quantum-assisted (senders share entanglement) strategies. We next show two examples that are conjectured to demonstrate the following capacity separations: an interference channel that strictly separates super-quantum from quantum-assisted strategies, and quantum-assisted from classical strategies; and, lastly, a multiple-access channel that strictly separates super-quantum- assisted strategies from classical ones. At the heart of some of these examples is a novel connection between multi-sender channels and multi-player XOR and pseudo-telepathy games.
This thesis studies the consequences of 'super-quantum non-local correlations', which are hypothetical violations of Bell/CHSH inequalities that are stronger - more nonlocal - than quantum mechanics allows, yet weak enough to respect special relativity in prohibiting faster-than-light communication. Understanding the power of such correlations will yield insight into the non-locality of quantum mechanics. Whereas previous studies of super-quantum correlations have demonstrated enhancements in cryptography and computation of distributed functions, this work opens up a new direction of research by showing that they can also enhance the capacity of classical communication over a noisy channel. Our results exhibit a trifecta of proof-of-concept channels: first, we show an interference channel between two sender-receiver pairs where the senders are not allowed to communicate, for which a shared super-quantum bit allows perfect classical communication. This feat is not achievable with the best classical (senders share no resources) or quantum-assisted (senders share entanglement) strategies. We next show two examples that are conjectured to demonstrate the following capacity separations: an interference channel that strictly separates super-quantum from quantum-assisted strategies, and quantum-assisted from classical strategies; and, lastly, a multiple-access channel that strictly separates super-quantum- assisted strategies from classical ones. At the heart of some of these examples is a novel connection between multi-sender channels and multi-player XOR and pseudo-telepathy games.
We study the consequences of superquantum nonlocal correlations as represented by the PR-box model of Popescu and Rohrlich, and show that PR boxes can enhance the capacity of noisy interference channels between two senders and two receivers. PR-box correlations violate Bell and CHSH inequalities and are thus stronger---more nonlocal---than quantum mechanics, yet weak enough to respect special relativity in prohibiting faster-than-light communication. Understanding their power will yield insight into the nonlocality of quantum mechanics. We exhibit two proof-of-concept channels: First, we show a channel between two sender-receiver pairs where the senders are not allowed to communicate, for which a shared superquantum bit (a PR box) allows perfect communication. This feat is not achievable with the best classical (senders share no resources) or quantum-entanglement-assisted (senders share entanglement) strategies. Second, we demonstrate a class of channels for which a tunable parameter $\ensuremath{\epsilon}$ achieves a double separation of capacities; for some range of $\ensuremath{\epsilon}$, the superquantum-assisted strategy does better than the entanglement-assisted strategy, which in turn does better than the classical one.
Quantum computing is the study of what we can and cannot do with quantum computers: computers operating based on the laws of quantum mechanics. This thesis is a collection of seven papers, dealing with three aspects of quantum computing: non-locality, cryptography and complexity.
Nonlocality. Quantum nonlocality refers to the fact that, using a resource called quantum entanglement, two participants who are physically separated and unable to communicate can exhibit correlations that cannot be produced without entanglement. This gives rise to nonlocal games, which are multi-player cooperative games for which quantum players (who share entanglement) have an advantage over classical players (who share only classical information). A pseudo-telepathy game is a special case of a nonlocal game for which quantum players have a perfect winning strategy. The first paper in this thesis, On the power of non-local boxes, is a study of quantum correlations (which are non-signalling, i.e. they do not allow faster-than-light communication), as well as superquantum correlations (which are also non-signalling, but stronger than those predicted by quantum mechanics). We consider the simulation of pseudo-telepathy winning strategies with the nonlocal box (which can be seen as the most basic superquantum correlation), revealing that nonlocality and entanglement are different resources. Before our work, it was common to equate these two notions. The second paper, Classical, quantum and non-signalling resources in bipartite games, shows that the problem of deciding if a fixed game has a perfect classical winning strategy is NP-complete, while deciding if a perfect strategy exists with superquantum correlations is in P. We also establish links with the Bell-Kochen-Specker theorem, orthogonality graphs and two-prover interactive proofs.
Quantum nonlocality is a phenomenon that we can, in theory, witness in the laboratory. Many experiments have been performed, but none so far have simultaneously closed all experimental loopholes. There is currently a substantial scientific effort to achieve the perfect laboratory experiment. Yet not all experimental setups are created equally: the third and fourth paper of this thesis, Entanglement swapping, light cones and elements of reality and On the logical structure of Bell theorems, show that recent proposals have classical explanations, and thus do nothing to aid in our comprehension of the quantum world. This work is scientifically valuable, since it tells us that we should not invest in the proposed lines of research.
Classical and quantum cryptography. The groundbreaking work of Peter Shor in 1995 established that quantum computers can efficiently factor large integers, thus rendering most modern cryptographic systems insecure. But what quantum computers break, they also fix: Bennett and Brassard had already given in 1984 a protocol for key distribution whose security is based only on the laws of quantum mechanics.
In a world with quantum computers, it seems like the only way to ensure perfect security in cryptographic tasks is to do away with computational assumptions (such as the apparent difficulty of factoring): this is the realm of information-theoretic security. In the fifth paper of this thesis, Information-theoretic security without an honest majority we give protocols to accomplish a series of six private distributed tasks (in particular, vote and anonymous message transmission), while ensuring information-theoretic security. Then, in Anonymous quantum communication, we give a protocol which, within a group, allows a sender to transfer a quantum message to a receiver ofhis choosing. The protocol ensures information-theoretic anonymity for the sender and the receiver as well as information-theoretic privacy for the message.
Complexity in the measurement-based model. Finally, in Parallelizing quantum circuits, we study the depth complexity of quantum circuits, giving an automated technique for the parrallelization of quantum circuits. The development of parallel (low-depth) quantum circuits seems almost essential if we wish to implement quantum algorithms in the near future with available technology. Quantum information is usually unstable, hence we can only operate on it for a very short period of time. Parallel circuits maximize the use of this fragile quantum information. Our method is based on the recent paradigm for quantum computing called the measurement-based model.
Key words: quantum information processing, pseudo-telepathy, nonlocal boxes, Bell's theorem, multi-party computation, information-theoretic security, anonymity, quantum depth complexity, measurement-based quantum computing, measurement calculus.
Quantum mechanics is nonlocal, meaning it cannot be described by any classical local hidden variable model. In this thesis we study two aspects of quantum nonlocality. Part I addresses the question of what classical resources are required to simulate nonlocal quantum correlations. We start by constructing new local models for noisy entangled quantum states. These constructions exploit the connection between nonlocality and Grothendieck's inequality, first noticed by Tsirelson. Next, we consider local models augmented by a limited amount of classical communication. After generalizing Bell inequalities to this setting, we show that (i) one bit of communication is sufficient to simulate the correlations of projective measurements on a maximally entangled state of two qubits, and (ii) five bits of communication are sufficient to simulate the joint correlation of two-outcome measurements on any bipartite quantum state. The latter result can be interpreted as a stronger (constrained) version of Grothendieck's inequality. In part II, we investigate the monogamy of nonlocal correlations. In a setting where three parties, A, B, and C, share an entangled quantum state of arbitrary dimension, we: (i) bound the trade-off between AB's and AC's violation of the CHSH inequality, obtaining an intriguing generalization of Tsirelson's bound, and (ii) demonstrate that forcing B and C to be classically correlated prevents A and B from violating certain Bell inequalities. We study not only correlations that arise within quantum theory, but also arbitrary correlations that do not allow signaling between separate groups of parties. These results are based on new techniques for obtaining Tsirelson bounds, or bounds on the quantum value of a Bell inequality, and have applications to interactive proof systems and cryptography.
We study various super-activation effects in the following zero-error communication scenario: One sender wants to send classical or quantum information through a noisy quantum channel to one receiver with zero probability of error. First we show that there are quantum channels of which a single use is not able to transmit classical information perfectly yet two uses can. This is achieved by employing entangled input states between different uses of the given channel and thus cannot happen for classical channels. Second we exhibit a class of quantum channel with vanishing zero-error classical capacity such that when a noiseless qubit channel or one ebit shared entanglement are available, it can be used to transmit log2d noiseless qubits, where 2d is the dimension of input state space. Third we further construct quantum channels with vanishing zero-error classical capacity when assisted with classical feedback can be used to transmit both classical and quantum information perfectly. These striking findings not only indicate both the zero-error quantum and classical capacities of quantum channels satisfy a strong super-additivity beyond any classical channels, but also highlight the activation power of auxiliary physical resources in zero-error communication.
Entanglement is at the heart of quantum mechanics. The nonlocal correlations that can be obtained from space-time separated measurements on an entangled state are a central feature which provably distinguish it from local theories. This dissertation studies entanglement through a computational viewpoint. We develop new insights into the complex nature of entanglement by studying its role in multiplayer games, in which cooperating, but non-communicating, players interact with a referee in an attempt to win a pre-specified game. On the one hand, the nonlocal correlations that entanglement allows may enable players using it to develop new colluding strategies, defeating previously secure protocols. On the other, the richness of this new resource may also be exploited in order to design new protocols, providing solutions to problems previously deemed impossible. We explore both aspects of this dual nature of entanglement, putting limits on its strength while at the same time showing how it can be put to profit to solve new computational problems. A major unresolved question on the computational complexity of multiplayer entangled games is the power of MIP*, the class of languages having entangled multi-prover interactive proofs: how does it relate to its purely classical analogue MIP, which was completely characterized through the fundamental equation MIP=NEXP? Since the players may use entanglement to increase their odds at colluding against the verifier, MIP* could potentially be a much weaker class than MIP. Indeed, for a long time it has been an open question whether two entangled provers are more useful than a single prover. In this thesis we resolve this question by showing that the class of languages having multiprover interactive proofs with entangled provers is at least as large as its classical counterpart: NEXP is included in MIP*. At the heart of this result is an analysis of the multilinearity test of Babai, Fortnow, and Lund in the presence of entanglement. The fact that this test remains sound gives a systematic way for a verifier to impose strong limits on the ability of entangled provers to collude against the verifier.Gap amplification is a fundamental primitive in the study of classical multiplayer games. While sequential repetition of a game always decreases the prover's maximum success probability at an exponential rate, the fact that parallel repetition also achieves a gap amplification is a highly non-trivial fact. We show that gap amplification can be performed in parallel even in the presence of entanglement between the provers. We adapt a technique which was originally introduced by Feige and Kilian and results in a polynomial rate of amplification.The phenomenon of monogamy of entanglement states, in first approximation, that if two parties are maximally entangled then they cannot simultaneously be entangled with a third party. We use this phenomenon in two distinct results. In the first, we show that the bits generated in our randomness-expansion protocol are certifiably random even from the point of view of a quantum adversary who may share prior entanglement with the provers. In addition, we prove the security against quantum adversaries of a randomness-efficient extractor construction originally due to Trevisan. This lets us transform the high-entropy bits that are generated in our protocol into ones that are almost indistinguishable from uniform by any adversary. More generally, we show how the monogamy of entanglement can be exploited to design multi-prover interactive proof systems that are partially entanglement-resistant. Quantitative bounds on the monogamy of entanglement have generally been elusive, and the analysis of our protocol demonstrates such a bound in a new context. The nonlocal correlations that can be created by entangled players provide a statistical means of differentiating them from classical, unentangled players. This is the main idea behind Bell inequalities, the violation of which demonstrates the nonlocality of quantum mechanics. We show how this phenomenon may be exploited to design a protocol in which the bits produced by successful players necessarily contain a large quantity of fresh randomness. The presence of randomness is guaranteed irrespective of the provers' actual strategy, as long as the sole constraint of no signaling is respected. Hence a statistical certification for the presence of randomness, a feat easily seen to be impossible to achieve classically. In order to manipulate the random bits produced in our protocol, and make them useful in cryptography, we give the first proof of security of a poly-logarithmic seed extractor secure against quantum adversaries. To achieve this we adapt the reconstruction paradigm originally introduced by Trevisan to the quantum setting. We study other ways in which entanglement may be used in interactive proof systems by also allowing a quantum interaction between the referee and the players. We show that, using entanglement, the class of QMIP* proof systems can be parallelized to only three rounds of interaction, and made public-coin, a property that does not hold in the absence of entanglement between the provers.
The zero-error capacity of a noisy classical channel quantifies its ability to transmit information with absolute certainty, i.e., without any error. Unlike Shannon's standard channel capacity, which remains unaffected by pre-shared correlations, zero-error capacity can be enhanced through nonlocal correlations. In this work, we investigate zero-error communication utility of such correlations arising in the 2-2-m Bell scenario, where two parties have two inputs and m possible outcomes per input. For all m\geq2, we construct examples of noisy classical channels with zero zero-error capacity that, when assisted by extremal 2-2-m nonlocal correlations, can transmit one bit of information. While nonlocal correlations arising from quantum entangled states cannot achieve a positive zero-error capacity for these channels, they significantly enhance the probability of successfully transmitting a classical bit in a single use. Extending this analysis to the 2-m-2 Bell scenario, we identify channels with zero zero-error capacity that can nonetheless perfectly transmit log m bits of information when assisted by corresponding extremal nonlocal correlations. Our findings underscore the versatile utility of Bell nonlocal correlations in achieving zero-error communication.