The Complexity-Theoretic Bell Inequality

The Bell inequality is one of the most important and foundational results of quantum physics named after its inventor John Stewart Bell. The inequality proves Einstein wrong and provides a concrete method to distinguish quantum mechanics from classical theories. We study Bell inequalities from a complexity theory perspective and show that the classical and quantum violations of a Bell inequality are not only different in value but are also different in terms of their computational complexity.