k-Contextuality as a Heuristic for Memory Separations in Learning

Abstract

Classical machine learning models struggle with learning and prediction tasks on data sets exhibiting long-range correlations. Previously, the existence of a long-range correlational structure known as contextuality was shown to inhibit efficient classical machine learning representations of certain quantum-inspired sequential distributions. Here, we define a new quantifier of contextuality we call strong k-contextuality, and prove that any translation task exhibiting strong k-contextuality is unable to be represented to finite relative entropy by a classical streaming model with fewer than k latent states. Importantly, this correlation measure does not induce a similar resource lower bound for quantum generative models. Using this theory as motivation, we develop efficient algorithms which estimate our new measure of contextuality in sequential data, and empirically show that this estimate is a good predictor for the difference in performance of resource-constrained classical and quantum Bayesian networks in modeling the data. Strong k-contextuality thus emerges as a measure to help identify problems that are difficult for classical computers, but may not be for quantum computers.

References in corpus (17)

• Supplementary information for "Quantum supremacy using a programmable superconducting processor"
• Quantum computational advantage using photons
• The ITensor Software Library for Tensor Network Calculations
• Contextuality supplies the magic for quantum computation
• The Sheaf-Theoretic Structure Of Non-Locality and Contextuality
• Quantum Supremacy and the Complexity of Random Circuit Sampling
• Contextuality in Measurement-based Quantum Computation
• Computational power of correlations
• A Combinatorial Approach to Nonlocality and Contextuality
• The contextual fraction as a measure of contextuality
• Contextuality as a resource for models of quantum computation on qubits
• Quantum Inference on Bayesian Networks
• Necessary and Sufficient Conditions for Extended Noncontextuality in a Broad Class of Quantum Mechanical Systems
• Enhancing Generative Models via Quantum Correlations
• Contextuality and Wigner negativity are equivalent for continuous-variable quantum measurements
• Interpretable Quantum Advantage in Neural Sequence Learning
• The role of cohomology in quantum computation with magic states