Challenges
Datasets
Workspaces
Papers
Discussions
Leaderboard
Log inSign up
Challenges
Datasets
Workspaces
Papers
Discussions
Leaderboard
Blog
Job Board
Q3AS

© 2026 Aqora Quantum S.A.S.

TermsPrivacyLegal Notice

Quantum nonlocality, cryptography and complexity

Anne Broadbent

Published Jan 1, 2008• 0 citations
Publisher

Abstract

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.

DOI
10.71781/9977

Related papers

The Complexity of Entangled Games

Thomas Vidick

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.

•Jan 1, 2011•10 citations

Resources for quantum information tasks: from the bipartite to the multipartite scenario

Mafalda L. Almeida

Quantum physics provides results at information processing tasks that are unattainable by any classical theory. The aim of this thesis is to identify and characterize quantum entanglement and quantum nonlocality, the key resources used at quantum information protocols. We consider the problem of finding better experimental schemes to detect entangled states. For that, we study approximate physical realizations to non-physical processes, which provide the most efficient method to identify entanglement. We prove that many of these physical approximations have a simple experimental implementation. We then study characterization of quantum nonlocality. We introduce a method using the multipartite scenario, where more than two parties are involved, which provides several results on bipartite and multipartite quantum nonlocality. First, we prove that there exist quantum states which contain full multipartite nonlocality, which consist of the strongest kind of nonlocality. then, we prove that the combined use of several copies of a state can activate its nonlocal properties. In particular, this holds for bipartite and genuine multipartite nonlocality. Finally, we characterize quantum nonlocality by distinguishing it from stronger-than-quantum nonlocality. We construct a multipartite game for which classical and quantum players perform equally well, but for which supre-quantum players can sometimes provide an advantage. Our results suggest that physical resources might obbey a generalized no-signaling principle ( according to which ther's no instantaneous communication).

•Jan 1, 2010•0 citations

An introduction to quantum: computing, communication complexity protocols, nonlocality and graph parameters

Lucas Silva Arenstein

What are the advantages quantum computing can provide when compared to classical computing? In this thesis, we aim to answer this question from different perspectives. To achieve this goal we divided this work into three parts. In Part I we start by studying the basic principles of quantum computing. Next, we introduce two quantum algorithms: the Deutsch-Jozsa and Grovers algorithms. The first algorithm has a lower query complexity and the second has a lower time complexity when compared with the best classical algorithm for the same problems. The final topic of this initial part is a detailed explanation and example of how to use Grovers algorithm to solve a Boolean formula in conjunctive normal form. In the second part, we focus on communication complexity problems. These problems are usually stated as follows: two spatially separated parties Alice and Bob receive an input from a referee. Their goal is to compute the value of a function that depends on both of their inputs with the least amount of communication between them. In Part II we will introduce protocols in which the transmission of quantum bits (qubits), instead of bits, can reduce the amount of communication necessary to solve these problems. We also study how Alice and Bob can use quantum entanglement to solve two communication complexity problems without communicating something that can not be done classically. In Part III we study nonlocal games inspired by standard graph theory parameters. A nonlocal game is usually defined as a game in which players that can share and do computations in an entangled state have some sort of advantage over classical players. We begin this final part by introducing the quantum chromatic number of a graph, which is the minimal number of colors necessary in a nonlocal game in which Alice and Bob can convince a referee with certainty that they have a proper coloring of the graph. We end this thesis by introducing other two quantum graph parameters, one related to graph homomorphism and the other to the independence number of a graph.

•Dec 12, 2022•0 citations

Programming Telepathy: Implementing Quantum Non-Locality Games

Anya Tafliovich, Eric C. R. Hehner

Quantum pseudo-telepathy is an intriguing phenomenon which results from the application of quantum information theory to communication complexity. To demonstrate this phenomenon researchers in the field of quantum communication complexity devised a number of quantum non-locality games. The setting of these games is as follows: the players are separated so that no communication between them is possible and are given a certain computational task. When the players have access to a quantum resource called entanglement, they can accomplish the task: something that is impossible in a classical setting. To an observer who is unfamiliar with the laws of quantum mechanics it seems that the players employ some sort of telepathy; that is, they somehow exchange information without sharing a communication channel. This paper provides a formal framework for specifying, implementing, and analysing quantum non-locality games.

arXiv:0707.1527•Jul 11, 2007•2 citations

Super-quantum and quantum enhancements of two-sender channels

Yihui Quek

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.

•Jan 1, 2016•0 citations

Nonlocality in multipartite correlation networks

Lars Erik Würflinger

Despite the success of quantum mechanics in predicting the outcomes of experiments in many branches of physics, the foundations of the theory have remained subject of research and dispute. At the basis of this struggle with the theory lie the phenomena of nonlocality and entanglement. Since it was first predicted by Bell in 1964, nonlocality was not only verified in numerous experiments, but also identified as a useful resource for quantum information processing. Thus, the study of nonlocality is important both from a fundamental point of view and with respect to new applications in quantum information theory, such as secure cryptography and randomness generation. The identification of entanglement as a resource for quantum information led to a strong theoretical effort devoted to its characterisation and detection. Many of the resulting mathematical tools find application in several domains of physics. Although the only known way to create nonlocal correlations is to measure entangled quantum systems, it has been shown that entanglement and nonlocality constitute two inequivalent properties. Therefore, in the light of the success of entanglement theory, it is of interest to also devise a resource theory of nonlocality. The task of this thesis is to develop such a theoretical framework for the characterisation of nonlocality as a resource. To gain a better understanding of nonlocal correlations it will be necessary to investigate correlation scenarios that go beyond the situation originally considered by Bell. In doing so, this thesis provides new description of nonlocality that also have implications for the characterisation of quantum correlations and the detection of new forms of nonlocality. The first question we address is how nonlocality can consistently be defined in a scenario of arbitrarily many parties that may collaborate among each other. To this end we recognise which are the allowed physical operations in this situation and then define nonlocality as the resource that cannot be created by these operations. Our approach shows that the conventional definition of multipartite nonlocality, adopted by the community so far, is inconsistent with this operational definition; we further propose and analyse new models that do not suffer from these inconsistencies. Furthermore, we show that our findings have implications for the characterisation of quantum correlations. A recent approach to describe the set of quantum correlation consists in using principles inspired from information theory. By using a special instance of the models we defined earlier we show a fundamental limitation of this approach: no bipartite information principle is sufficient to single out the set of quantum correlations from the set of nonsignalling correlations. We then developed a description of nonlocality in an even more generalised scenario of several parties. Motivated by a result of Popescu we study scenarios where the parties are allowed to perform not only a single but sequences of measurements on their systems. Characterising nonlocality also in this scenario in operational terms and defining local models compatible with this definition, we show that a new form of nonlocality can be detected Lastly, we examine the problem of detecting the presence of nonlocality in a multipartite scenario when one is given only partial access to the global system. We find that one can verify that the total system must display nonlocality, even though the accessible subsystems only exhibit local correlations.

•Sep 18, 2013•0 citations
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.
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.
Quantum physics provides results at information processing tasks that are unattainable by any classical theory. The aim of this thesis is to identify and characterize quantum entanglement and quantum nonlocality, the key resources used at quantum information protocols. We consider the problem of finding better experimental schemes to detect entangled states. For that, we study approximate physical realizations to non-physical processes, which provide the most efficient method to identify entanglement. We prove that many of these physical approximations have a simple experimental implementation. We then study characterization of quantum nonlocality. We introduce a method using the multipartite scenario, where more than two parties are involved, which provides several results on bipartite and multipartite quantum nonlocality. First, we prove that there exist quantum states which contain full multipartite nonlocality, which consist of the strongest kind of nonlocality. then, we prove that the combined use of several copies of a state can activate its nonlocal properties. In particular, this holds for bipartite and genuine multipartite nonlocality. Finally, we characterize quantum nonlocality by distinguishing it from stronger-than-quantum nonlocality. We construct a multipartite game for which classical and quantum players perform equally well, but for which supre-quantum players can sometimes provide an advantage. Our results suggest that physical resources might obbey a generalized no-signaling principle ( according to which ther's no instantaneous communication).
What are the advantages quantum computing can provide when compared to classical computing? In this thesis, we aim to answer this question from different perspectives. To achieve this goal we divided this work into three parts. In Part I we start by studying the basic principles of quantum computing. Next, we introduce two quantum algorithms: the Deutsch-Jozsa and Grovers algorithms. The first algorithm has a lower query complexity and the second has a lower time complexity when compared with the best classical algorithm for the same problems. The final topic of this initial part is a detailed explanation and example of how to use Grovers algorithm to solve a Boolean formula in conjunctive normal form. In the second part, we focus on communication complexity problems. These problems are usually stated as follows: two spatially separated parties Alice and Bob receive an input from a referee. Their goal is to compute the value of a function that depends on both of their inputs with the least amount of communication between them. In Part II we will introduce protocols in which the transmission of quantum bits (qubits), instead of bits, can reduce the amount of communication necessary to solve these problems. We also study how Alice and Bob can use quantum entanglement to solve two communication complexity problems without communicating something that can not be done classically. In Part III we study nonlocal games inspired by standard graph theory parameters. A nonlocal game is usually defined as a game in which players that can share and do computations in an entangled state have some sort of advantage over classical players. We begin this final part by introducing the quantum chromatic number of a graph, which is the minimal number of colors necessary in a nonlocal game in which Alice and Bob can convince a referee with certainty that they have a proper coloring of the graph. We end this thesis by introducing other two quantum graph parameters, one related to graph homomorphism and the other to the independence number of a graph.
Quantum pseudo-telepathy is an intriguing phenomenon which results from the application of quantum information theory to communication complexity. To demonstrate this phenomenon researchers in the field of quantum communication complexity devised a number of quantum non-locality games. The setting of these games is as follows: the players are separated so that no communication between them is possible and are given a certain computational task. When the players have access to a quantum resource called entanglement, they can accomplish the task: something that is impossible in a classical setting. To an observer who is unfamiliar with the laws of quantum mechanics it seems that the players employ some sort of telepathy; that is, they somehow exchange information without sharing a communication channel. This paper provides a formal framework for specifying, implementing, and analysing quantum non-locality 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.
Despite the success of quantum mechanics in predicting the outcomes of experiments in many branches of physics, the foundations of the theory have remained subject of research and dispute. At the basis of this struggle with the theory lie the phenomena of nonlocality and entanglement. Since it was first predicted by Bell in 1964, nonlocality was not only verified in numerous experiments, but also identified as a useful resource for quantum information processing. Thus, the study of nonlocality is important both from a fundamental point of view and with respect to new applications in quantum information theory, such as secure cryptography and randomness generation. The identification of entanglement as a resource for quantum information led to a strong theoretical effort devoted to its characterisation and detection. Many of the resulting mathematical tools find application in several domains of physics. Although the only known way to create nonlocal correlations is to measure entangled quantum systems, it has been shown that entanglement and nonlocality constitute two inequivalent properties. Therefore, in the light of the success of entanglement theory, it is of interest to also devise a resource theory of nonlocality. The task of this thesis is to develop such a theoretical framework for the characterisation of nonlocality as a resource. To gain a better understanding of nonlocal correlations it will be necessary to investigate correlation scenarios that go beyond the situation originally considered by Bell. In doing so, this thesis provides new description of nonlocality that also have implications for the characterisation of quantum correlations and the detection of new forms of nonlocality. The first question we address is how nonlocality can consistently be defined in a scenario of arbitrarily many parties that may collaborate among each other. To this end we recognise which are the allowed physical operations in this situation and then define nonlocality as the resource that cannot be created by these operations. Our approach shows that the conventional definition of multipartite nonlocality, adopted by the community so far, is inconsistent with this operational definition; we further propose and analyse new models that do not suffer from these inconsistencies. Furthermore, we show that our findings have implications for the characterisation of quantum correlations. A recent approach to describe the set of quantum correlation consists in using principles inspired from information theory. By using a special instance of the models we defined earlier we show a fundamental limitation of this approach: no bipartite information principle is sufficient to single out the set of quantum correlations from the set of nonsignalling correlations. We then developed a description of nonlocality in an even more generalised scenario of several parties. Motivated by a result of Popescu we study scenarios where the parties are allowed to perform not only a single but sequences of measurements on their systems. Characterising nonlocality also in this scenario in operational terms and defining local models compatible with this definition, we show that a new form of nonlocality can be detected Lastly, we examine the problem of detecting the presence of nonlocality in a multipartite scenario when one is given only partial access to the global system. We find that one can verify that the total system must display nonlocality, even though the accessible subsystems only exhibit local correlations.