2013/11/20 by Mohammad Bavarian, Peter W. Shor, Bavarian, Mohammad +1
Computer Science · Mathematics · #Benford’s Law and Fraud Detection #Computability, Logic, AI Algorithms #Computational Complexity (cs.CC) #Cryptography and Data Security #FOS: Computer and information sciences #FOS: Physical sciences #Quantum Computing Algorithms and Architecture #Quantum Physics (quant-ph)
paper · pdf · doi:10.48550/arxiv.1311.5186
openalex publication_date 2013/11/20 · openalex created_date 2022/10/04 · openalex updated_date 2026/07/28
In this work, we consider the following family of two prover one-round games.\nIn the CHSHq game, two parties are given x,y in Fq uniformly at random, and\neach must produce an output a,b in Fq without communicating with the other.\nThe players' objective is to maximize the probability that their outputs\nsatisfy a+b=xy in Fq. This game was introduced by Buhrman and Massar (PRA\n2005) as a large alphabet generalization of the celebrated CHSH game---which is\none of the most well-studied two-prover games in quantum information theory,\nand which has a large number of applications to quantum cryptography and\nquantum complexity.\n Our main contributions in this paper are the first asymptotic and explicit\nbounds on the entangled and classical values of CHSHq, and the realization of\na rather surprising connection between CHSHq and geometric incidence theory.\nOn the way to these results, we also resolve a problem of Pawlowski and Winter\nabout pairwise independent Information Causality, which, beside being\ninteresting on its own, gives as an application a short proof of our upper\nbound for the entangled value of CHSHq.\n