Quantifying the Limits of Classical Machine Learning Models Using Contextuality

Classical machine learning models struggle with learning and prediction tasks on data sets exhibiting long-range correlations. To quantify this observation we introduce a new quantity we call strong k-contextuality, develop efficient algorithms to estimate the strong k-contextuality of an empirical data set, and prove that the presence of strong k-contextuality lower bounds the classical resources required to model the associated distribution. We also show that this correlation measure does not induce a similar resource lower bound for quantum generative models, and thus propose strong k-contextuality as an empirical measure for evaluating whether a given machine learning task may be better suited for quantum models than classical models.