Computational Bell inequalities

Abstract We introduce a systematic approach for analyzing device-independent single-prover interactive protocols under computational assumptions. This is done by establishing an explicit correspondence with Bell inequalities and nonlocal games and constructing a computational space of correlations . We show how computational assumptions are converted to computational Bell inequalities , in their rigorous mathematical sense—a hyperplane that separates the sets of classical and quantum verifier-prover interactions. We reveal precisely how the nonsignaling assumption in standard device-independent setups admits a computational analogue through the challenge of learning a hidden input (which we define). We further utilize our fundamental results to study explicit protocols using the new perspective. We take advantage of modular tools for studying nonlocality, deriving tighter Tsirelson bounds for single-prover protocols and bounding the entropy generated in the interaction, improving on previous results. Our work thus establishes a modular approach to analyzing single-prover quantum certification protocols based on computational assumptions through the fundamental lens of Bell inequalities, removing many layers of technical overhead. The link that we draw between single-prover protocols and Bell inequalities goes far beyond the spread intuitive understanding or known results about ‘compiled nonlocal games’; Notably, it captures the exact way in which the correspondence between computational assumptions and locality should be understood also in protocols based on, e.g. trapdoor claw-free functions (in which there is no clear underlying nonlocal game).