Bell's theorem says, roughly, that it follows from the laws
of quantum mechanics that two parties can interact
instantaneously across arbitrary distances. This phenomenon,
called "quantum nonlocality", has been called "the most
profound discovery of science". The nature of these
"interactions" is notoriously subtle. For example, the
no-communication theorem says that quantum nonlocality is
not useful for sending genuine signals. In this paper, we
rule out one possible approach to characterizing the exact
extent of the "nonlocal powers" granted by the laws of
quantum mechanics. In particular, aside from quantum
nonlocality, another situation in which two parties can
interact in a limited way is if there is some discrete,
classical device that each party is able to interact with.
We prove that quantum nonlocality is not quite equivalent to
any such discrete, classical device.
also available on this site
is much more compact than the earlier
The arXiv version has essentially the same results, but it
has more detailed definitions and proofs and some suggested
open problems. The arXiv version also uses slightly
different notation and is missing some references.
I presented this paper in Scott Aaronson's course "Topics
in Quantum and Classical Complexity Theory" in Fall 2016;
the slides are available
© 2017 American Physical Society.