Quantum Pseudo-Telepathy
arXiv:quant-ph/0407221 · doi:10.1007/s10701-005-7353-4
Abstract
Quantum information processing is at the crossroads of physics, mathematics and computer science. It is concerned with that we can and cannot do with quantum information that goes beyond the abilities of classical information processing devices. Communication complexity is an area of classical computer science that aims at quantifying the amount of communication necessary to solve distributed computational problems. Quantum communication complexity uses quantum mechanics to reduce the amount of communication that would be classically required. Pseudo-telepathy is a surprising application of quantum information processing to communication complexity. Thanks to entanglement, perhaps the most nonclassical manifestation of quantum mechanics, two or more quantum players can accomplish a distributed task with no need for communication whatsoever, which would be an impossible feat for classical players. After a detailed overview of the principle and purpose of pseudo-telepathy, we present a survey of recent and no-so-recent work on the subject. In particular, we describe and analyse all the pseudo-telepathy games currently known to the authors.
Minor modification in section 2 to give proper credit for the impossible colouring game. References corrected and updated
References in corpus (14)
- Violation of Bell inequalities by photons more than 10 km apart
- The cost of exactly simulating quantum entanglement with classical communication
- "All versus nothing" inseparability for two observers
- Experimental test of non-local quantum correlation in relativistic configurations
- Bell's theorem without inequalities and without probabilities for two observers
- Quantum nonlocality, Bell inequalities and the memory loophole
- Non locality, closing the detection loophole and communication complexity
- All-Versus-Nothing Violation of Local Realism for Two Entangled Photons
- Quantum codewords contradict local realism
- Violation of local realism vs detection efficiency
- Combinatorics and Quantum Nonlocality
- Bell inequality and the locality loophole: Active versus passive switches
- Multi-Party Pseudo-Telepathy
- Extended GHZ n-player games with classical probability of winning tending to 0
Cited by in corpus (90)
- Bell nonlocality
- Non-locality and Communication Complexity
- Self-testing of quantum systems: a review
- Kochen-Specker Contextuality
- Large violation of Bell inequalities with low entanglement
- Toward a general theory of quantum games
- The Two Bell's Theorems of John Bell
- Device-independent parallel self-testing of two singlets
- State independent contextuality advances one-way communication
- Fully nonlocal quantum correlations
- Playing Games with Multiple Access Channels
- From Einstein's Theorem to Bell's Theorem: A History of Quantum Nonlocality
- Unbounded violations of bipartite Bell Inequalities via Operator Space theory
- A two-qubit Bell inequality for which POVM measurements are relevant
- A compositional approach to quantum functions
- Converting contextuality into nonlocality
- Multisetting Bell-type inequalities for detecting genuine tripartite entanglement
- Quantum Game Theory Based on the Schmidt Decomposition
- On the power of non-local boxes
- The Morita theory of quantum graph isomorphisms
- Models of quantum computation and quantum programming languages
- A Generalization of Kochen-Specker Sets Relates Quantum Coloring to Entanglement-Assisted Channel Capacity
- Can quantum mechanics help distributed computing?
- Noise Effects in Quantum Magic Squares Game
- Contextuality in entanglement-assisted one-shot classical communication
- Experimental Demonstration of Quantum Pseudotelepathy
- Non-Locality Without Counterfactual Reasoning
- Extended nonlocal games and monogamy-of-entanglement games
- Device-Independent Quantum Key Distribution Based on the Mermin-Peres Magic Square Game
- Measurement-based quantum computation in finite one-dimensional systems: string order implies computational power
- Bell nonlocality with a single shot
- Quantum Broadcast Channels with Cooperating Decoders: An Information-Theoretic Perspective on Quantum Repeaters
- Surpassing the Classical Limit in Magic Square Game with Distant Quantum Dots Coupled to Optical Cavities
- Unlimited non-causal correlations and their relation to non-locality
- Generalized XOR games with outcomes and the task of non-local computation
- Steering is an essential feature of non-locality in quantum theory
- Quantum games on evolving random networks
- Distinguishing quantum channels via magic squares game
- Custom Bell inequalities from formal sums of squares
- Quantum sets
- A competitive game whose maximal Nash-equilibrium payoff requires quantum resources for its achievement
- Critical noncolorings of the 600-cell proving the Bell-Kochen-Specker theorem
- Certifying sets of quantum observables with any full-rank state
- Regarding the Maximal Qubit Violations of n-Locality in Star and Chain Networks
- Multiple-Access Channel Coding with Non-Signaling Correlations
- Enhancing pseudo-telepathy in the Magic Square game
- Entanglement-induced provable and robust quantum learning advantages
- Contextuality degree of quadrics in multi-qubit symplectic polar spaces
- Advantage of Quantum Theory Over Non-classical Models of Communication
- Equivalence between face nonsignaling correlations, full nonlocality, all-versus-nothing proofs, and pseudotelepathy
- On the separation of correlation-assisted sum capacities of multiple access channels
- More non-locality in the three-qubit Greenberger-Horne-Zeilinger state
- Symmetric multipartite Bell inequalities via Frank-Wolfe algorithms
- Playing nonlocal games across a topological phase transition on a quantum computer
- Two-player quantum pseudo-telepathy based on recent all-versus-nothing violations of local realism
- Simplest bipartite perfect quantum strategies
- On local-hidden-variable no-go theorems
- Entangled Rendezvous: A Possible Application of Bell Non-Locality For Mobile Agents on Networks
- Quantum Magic Rectangles: Characterization and Application to Certified Randomness Expansion
- Quantum guessing games with posterior information
- Random constructions in Bell inequalities: A survey
- Entanglement swapping, light cones and elements of reality
- Quantum nonlocality via local contextuality with qubit-qubit entanglement
- A multi-player, multi-team nonlocal game for the toric code
- Playing nonlocal games with phases of quantum matter
- Experimental Quantum Advantage in the Odd-Cycle Game
- Unconditional quantum magic advantage in shallow circuit computation
- Irreducible magic sets for -qubit systems
- Undetectable Werner states using linear Bell inequalities
- Towards Characterizing the Non-Locality of Entangled Quantum States
- Exponential quantum enhancement for distributed addition with local nonlinearity
- The six blinds and the elephant or an interdisciplinary selection of measurement features
- 3XOR Games with Perfect Commuting Operator Strategies Have Perfect Tensor Product Strategies and are Decidable in Polynomial Time
- Practical parallel self-testing of Bell states via magic rectangles
- Fiat-Shamir for Proofs Lacks a Proof Even in the Presence of Shared Entanglement
- Improving social welfare in non-cooperative games with different types of quantum resources
- Bound on Bell Inequalities by Fraction of Determinism and Reverse Triangle Inequality
- Stronger Nonlocality in GHZ States: A Step Beyond the Conventional GHZ Paradox
- Optimal conversion of Kochen-Specker sets into bipartite perfect quantum strategies
- Trade-off relations between Bell nonlocality and local Kochen-Specker contextuality in generalized Bell scenarios
- Nonlocal and quantum advantages in network coding for multiple access channels
- Quantitative comparison of quantum pseudo-telepathy games and Bell inequalities
- Weight-based measure of quantum memory as a universal and operational benchmark
- Beating one bit of communication with and without quantum pseudo-telepathy
- Alice and Bob Get Away With It: a playlet
- Supersinglets can be self-tested with perfect quantum strategies
- Counterexamples in self-testing
- The Quantum Multiple-Access Channel with Cribbing Encoders
- Analysis of Boolean Functions Related to Binary Input Binary Output Two-party Nonlocal Games
- Quantum advantage through the magic pentagram problem