Search

We study bipartite games that arise in the context of nonlocality with the help of graph theory. Our main results are alternate proofs that deciding whether a no-communication classical winning strategy exists for certain games (called forbidden-edge and covering games) is NP-complete, while the problem of deciding if these games admit a nonsignalling winning strategy is in P. We discuss relations between quantum winning strategies and orthogonality graphs. We also show that every pseudotelepathy game yields both a proof of the Bell-Kochen-Specker theorem and an instance of a two-prover interactive proof system that is classically sound, but that becomes unsound when provers use shared entanglement.

As demonstrated by John Bell, quantum mechanics exhibits correlations in spacelike separated bipartite systems that are impossible to reproduce by classical means. There are three levels of ''Bell Theorems'', depending on which aspects of the quantum correlations can or cannot be reproduced classically. The original ''Bell Inequalities'' (BI) require a perfect classical simulation of all quantum probabilities. With ''Bell Theorems Without Inequalities'' (BTWI), we ask the classical simulation to be able to produce precisely the outcomes that could occur according to quantum mechanics, but we do not worry about their exact probabilities. With ''Pseudotelepathy'' (PT), we are satisfied if the classical simulation produces only outcomes allowed by quantum mechanics, but not necessarily all of them. Bell's original proof of BI involved a maximally entangled 2x2 bipartite state such as the singlet state. Hardy proved that BTWI are possible in dimension 2x2, but his construction used a non-maximally entangled state. Here, we prove that no 2x2 maximally entangled state can serve to produce BTWI. Combining this with our earlier result that 2x2 entangled states cannot be used at all for the purpose of PT, it follows a strict hierarchy on the quantum resources that are required to exhibit the various levels of Bell Theorems.

In an earlier paper written in loving memory of Asher Peres, we gave a critical analysis of the celebrated 1935 paper in which Einstein, Podolsky and Rosen (EPR) challenged the completeness of quantum mechanics. There, we had pointed out logical shortcomings in the EPR paper. Now, we raise additional questions concerning their suggested program to find a theory that would “provide a complete description of the physical reality”. In particular, we investigate the extent to which the EPR argumentation could have lead to the more dramatic conclusion that quantum mechanics is in fact incorrect. With this in mind, we propose a speculation, made necessary by a logical shortcoming in the EPR paper caused by the lack of a necessary condition for “elements of reality”, and surmise that an eventually complete theory would either be inconsistent with quantum mechanics, or would at least violate Heisenberg’s Uncertainty Principle.

Pseudo-telepathy is the most recent form of rejection of locality. Many of its properties have already been discovered: for instance, the minimal entanglement, as well as the minimal cardinality of the output sets, have been characterized. This paper contains two main results. First, we prove that no bipartite pseudo-telepathy game exists, in which one of the partners receives only two questions; as a corollary, we show that the minimal "input cardinality", that is, the minimal number of questions required in a bipartite pseudo-telepathy game, is 3x3. Second, we study the Bell-type inequality derived from the pseudo-telepathy game known as the Magic Square game: we demonstrate that it is a tight inequality for 3 inputs and 4 outputs on each side and discuss its weak resistance to noise., 12 pages, no figures

There are many different definitions of what a Bell–Kochen–Specker proof with POVMs might be. Here, we present and discuss the minimal proof on qubits for three of these definitions and show that they are indeed minimal.

Recently, a number of two-participant all-versus-nothing Bell experiments have been proposed. Here, we give local realistic explanations for these experiments. More precisely, we examine the scenario where a participant swaps his entanglement with two other participants and then is removed from the experiment; we also examine the scenario where two particles are in the same light cone, i.e. belong to a single participant. Our conclusion is that, in both cases, the proposed experiments are not convincing proofs against local realism., 10 pages, no figure, LHV models given explicitely, more explanations

In loving memory of Asher Peres, we discuss a most important and influential paper written in 1935 by his thesis supervisor and mentor Nathan Rosen, together with Albert Einstein and Boris Podolsky. In that paper, the trio known as EPR questioned the completeness of quantum mechanics. The authors argued that the then-new theory should not be considered final because they believed it incapable of describing physical reality. The epic battle between Einstein and Bohr intensified following the latter's response later the same year. Three decades elapsed before John S. Bell gave a devastating proof that the EPR argument was fatally flawed. The modest purpose of our paper is to give a critical analysis of the original EPR paper and point out its logical shortcomings in a way that could have been done 70 years ago, with no need to wait for Bell's theorem. We also present an overview of Bohr's response in the interest of showing how it failed to address the gist of the EPR argument.

Given a set of correlations originating from measurements on a quantum state of unknown Hilbert space dimension, what is the minimal dimension d necessary to describe such correlations? We introduce the concept of dimension witness to put lower bounds on d. This work represents a first step in a broader research program aiming to characterize Hilbert space dimension in various contexts related to fundamental questions and quantum information applications.

As proved by John Bell, quantum mechanics exhibits correlations in spacelike separated bipartite systems that are impossible to reproduce by classical means. There are three levels of "Bell theorems", depending on which aspects of the quantum correlations can or cannot be reproduced classically. The original "Bell inequalities" (Bl) require a perfect classical simulation of all quantum probabilities. With "Bell theorems without inequalities" (BTWI), we ask the classical simulation to be able to produce precisely the outputs that could occur according to quantum mechanics, but we do not worry about their exact probabilities. With "pseudo-telepathy" (PT), we are satisfied if the classical simulation produces only outputs allowed by quantum mechanics, but not necessarily all of them. Bell's original proof of Bl involved a maximally entangled 2times2 bipartite state such as the singlet state. Hardy proved that BTWI are possible in dimension 2times2, but his construction used a non-maximally entangled state. Here, we prove that no 2times2 maximally entangled state can serve to produce BTWI. Combining this with the fact that 2times2 entangled states cannot be used at all for the purpose of PT, it follows a strict hierarchy on the quantum resources that are required to exhibit the various levels of Bell theorems.

Bell proved that quantum entanglement enables two space-like separated parties to exhibit classically impossible correlations. Even though these correlations are stronger than anything classically achievable, they cannot be harnessed to make instantaneous (faster than light) communication possible. Yet, Popescu and Rohrlich have shown that even stronger correlations can be defined, under which instantaneous communication remains impossible. This raises the question: Why are the correlations achievable by quantum mechanics not maximal among those that preserve causality? We give a partial answer to this question by showing that slightly stronger correlations would result in a world in which communication complexity becomes trivial., 13 pages, no figures

The strongest attack against quantum mechanics came in 1935 in the form of a paper by Einstein, Podolsky and Rosen. It was argued that the theory of quantum mechanics could not be called a complete theory of Nature, for every element of reality is not represented in the formalism as such. The authors then put forth a proposition: we must search for a theory where, upon knowing everything about the system, including possible hidden variables, one could make precise predictions concerning elements of reality. This project was ultimatly doomed in 1964 with the work of Bell Bell, who showed that the most general local hidden variable theory could not reproduce correlations that arise in quantum mechanics. There exist mainly three forms of no-go theorems for local hidden variable theories. Although almost every physicist knows the consequences of these no-go theorems, not every physicist is aware of the distinctions between the three or even their exact definitions. Thus we will discuss here the three principal forms of no-go theorems for local hidden variable theories of Nature. We will define Bell inequalities, Bell inequalities without inequalities and pseudo-telepathy. A discussion of the similarities and differences will follow., Comment: 7 pages, no figure, replaced "Bell inequalities" with "Bell theorems" and updated the references

We show that standard nonlocal boxes, also known as Popescu-Rohrlich machines, are not sufficient to simulate any nonlocal correlations that do not allow signalling. This was known in the multipartite scenario, but we extend the result to the bipartite case. We then generalize this result further by showing that no finite set containing any finite-output-alphabet nonlocal boxes can be a universal set for nonlocality., Comment: Additions to the acknowledgements section

Bell theorems show how to experimentally falsify local realism. Conclusive falsification is highly desirable as it would provide support for the most profoundly counterintuitive feature of quantum theory - nonlocality. Despite the preponderance of evidence for quantum mechanics, practical limits on detector efficiency and the difficulty of coordinating space-like separated measurements have provided loopholes for a classical worldview; these loopholes have never been simultaneously closed. A number of new experiments have recently been proposed to close both loopholes at once. We show some of these novel designs fail in the most basic way, by not ruling out local hidden variable models, and we provide an explicit classical model to demonstrate this. They share a common flaw, which reveals a basic misunderstanding of how nonlocality proofs work. Given the time and resources now being devoted to such experiments, theoretical clarity is essential. Our explanation is presented in terms of simple logic and should serve to correct misconceptions and avoid future mistakes. We also show a nonlocality proof involving four participants which has interesting theoretical properties.

A non-local box is a virtual device that has the following property: given that Alice inputs a bit at her end of the device and that Bob does likewise, it produces two bits, one at Alice's end and one at Bob's end, such that the XOR of the outputs is equal to the AND of the inputs. This box, inspired from the CHSH inequality, was first proposed by Popescu and Rohrlich to examine the question: given that a maximally entangled pair of qubits is non-local, why is it not maximally non-local? We believe that understanding the power of this box will yield insight into the non-locality of quantum mechanics. It was shown recently by Cerf, Gisin, Massar and Popescu, that this imaginary device is able to simulate correlations from any measurement on a singlet state. Here, we show that the non-local box can in fact do much more: through the simulation of the magic square pseudo-telepathy game and the Mermin-GHZ pseudo-telepathy game, we show that the non-local box can simulate quantum correlations that no entangled pair of qubits can in a bipartite scenario and even in a multi-party scenario. Finally we show that a single non-local box cannot simulate all quantum correlations and propose a generalization for a multi-party non-local box. In particular, we show quantum correlations whose simulation requires an exponential amount of non-local boxes, in the number of maximally entangled qubit pairs., Comment: 14 pages, 1 figure

We study bipartite games that arise in the context of nonlocality with the help of graph theory. Our main results are alternate proofs that deciding whether a no communication classical winning strategy exists for certain games (called forbidden edge and covering games) is NP complete while the problem of decid ing if these games admit a non signalling winning strategy is in P. We discuss rela tions between quantum winning strategies and orthogonality graphs. We also show that every pseudo telepathy game yields both a proof of the Bell Kochen Specker theorem and an instance of a two prover interactive proof system that is classically sound but that becomes unsound when provers use shared entanglement.