Combinatorics and Quantum Nonlocality

We use techniques for lower bounds on communication to derive necessary conditions (in terms of detector efficiency or amount of superluminal communication) for being able to reproduce the quantum correlations occurring in Einstein-Podolsky-Rosen–type experiments with classical local hidden-variable theories. As an application, we consider $n$ parties sharing a Greenberger-Horne-Zeilinger–type state and show that the amount of superluminal classical communication required to reproduce the correlations is at least $n({log}_{2}n-3)$ bits and the maximum detector efficiency ${\eta }_{*}$ for which the resulting correlations can still be reproduced by a local hidden-variable theory is upper bounded by ${\eta }_{*}\le 8/n$ and thus decreases with $n$.