pith. sign in

arxiv: 2507.11604 · v1 · submitted 2025-07-15 · 🪐 quant-ph

k-Contextuality as a Heuristic for Memory Separations in Learning

Mariesa H. Teo , Willers Yang , James Sud , Teague Tomesh , Frederic T. Chong , Eric R. Anschuetz This is my paper

Pith reviewed 2026-05-19 03:53 UTC · model grok-4.3

classification 🪐 quant-ph
keywords contextualityquantum machine learningmemory lower boundsstreaming modelssequential distributionsBayesian networksgenerative models
0
0 comments X

The pith

Any translation task with strong k-contextuality cannot be represented to finite relative entropy by a classical streaming model with fewer than k latent states.

A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.

The paper defines strong k-contextuality as a property of sequential distributions and proves it imposes a strict memory lower bound on classical streaming models. Tasks showing this property cannot achieve finite relative entropy approximation unless the model maintains at least k distinct latent states. Quantum generative models face no equivalent restriction, which motivates the use of the measure to flag data where quantum approaches may require less memory. Algorithms are given to estimate the quantity directly from sequences, and experiments confirm that higher estimated values predict larger performance gaps between resource-limited classical and quantum Bayesian networks.

Core claim

Strong k-contextuality is defined for translation tasks on sequential data, and any such task is shown to require at least k latent states in a classical streaming model to achieve finite relative entropy. The same lower bound does not apply to quantum generative models, and empirical estimates of the measure serve as predictors for performance differences between constrained classical and quantum networks.

What carries the argument

strong k-contextuality, a new quantifier of contextuality in sequential distributions that directly implies a latent-state lower bound for classical streaming models

If this is right

  • Classical streaming models must use at least k latent states to reach finite relative entropy on strongly k-contextual tasks.
  • Quantum generative models can avoid the k-state lower bound on the same tasks.
  • Estimates of strong k-contextuality from data can indicate when quantum Bayesian networks will outperform memory-limited classical ones.
  • The measure provides a practical heuristic for selecting between classical and quantum models under memory constraints.

Where Pith is reading between the lines

These are editorial extensions of the paper, not claims the author makes directly.

  • The separation could be used to decide when to allocate quantum resources in hybrid sequential learning pipelines.
  • Similar contextuality measures might be developed for other classical resource models such as finite automata or recurrent networks.
  • Empirical checks on real-world sequential datasets could test whether high k-contextuality correlates with observed quantum advantages in practice.

Load-bearing premise

A classical streaming model with a fixed number of latent states is the right resource-bounded model for proving memory lower bounds on learning these sequential distributions.

What would settle it

Exhibit a classical streaming model with fewer than k latent states that approximates a strongly k-contextual translation task to finite relative entropy.

Figures

Figures reproduced from arXiv: 2507.11604 by Eric R. Anschuetz, Frederic T. Chong, James Sud, Mariesa H. Teo, Teague Tomesh, Willers Yang.

Figure 1
Figure 1. Figure 1: Strong k-contextuality implies a memory lower bound on a classical generative model representing some family of probability distributions to finite relative entropy. The intuition to study the implications of contextuality on machine learning (ML) stems from the fact that classical ML models can have difficulty capturing the correlations present in certain complex probability distributions—such as those as… view at source ↗
Figure 2
Figure 2. Figure 2: Presence of strong k-contextuality in empirical data sets can indicate separations between classical and quantum learning models. Here we show an example of the perfor￾mance gap between classical and quantum HMMs trained on synthetic random distributions, where the gap increases with the larger strong k-contextuality number. We return to this result in Sec. VI. This paper is structured as follows: We begin… view at source ↗
Figure 3
Figure 3. Figure 3: Overview of the contextuality framework. a) A mea [PITH_FULL_IMAGE:figures/full_fig_p003_3.png] view at source ↗
Figure 4
Figure 4. Figure 4: Performance of approximation methods for randomly [PITH_FULL_IMAGE:figures/full_fig_p006_4.png] view at source ↗
Figure 5
Figure 5. Figure 5: Runtimes of approximation methods for random mod [PITH_FULL_IMAGE:figures/full_fig_p006_5.png] view at source ↗
Figure 6
Figure 6. Figure 6: The greedy heuristic converges to the correct answer [PITH_FULL_IMAGE:figures/full_fig_p006_6.png] view at source ↗
Figure 7
Figure 7. Figure 7: Performance of classical and quantum hidden Markov models on contextual random empirical models. (a) The KL [PITH_FULL_IMAGE:figures/full_fig_p007_7.png] view at source ↗
Figure 8
Figure 8. Figure 8: Performance of classical and quantum hidden Markov [PITH_FULL_IMAGE:figures/full_fig_p008_8.png] view at source ↗
Figure 9
Figure 9. Figure 9: The convergence of the greedy heuristic to a contextu [PITH_FULL_IMAGE:figures/full_fig_p008_9.png] view at source ↗
Figure 10
Figure 10. Figure 10: Performance of classical and quantum hidden Markov models on predicting promoter gene sequences of token length [PITH_FULL_IMAGE:figures/full_fig_p009_10.png] view at source ↗
Figure 11
Figure 11. Figure 11: The likelihood-ratio test for the performance gap [PITH_FULL_IMAGE:figures/full_fig_p009_11.png] view at source ↗
read the original 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.

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, simulated authors' rebuttal, and a circularity audit. Tearing a paper down is the easy half of reading it; the pith above is the substance, this is the friction.

Referee Report

2 major / 2 minor

Summary. The paper defines a new measure called strong k-contextuality for sequential translation tasks with long-range correlations. It proves that any task exhibiting this property cannot be represented to finite relative entropy by a classical streaming model (finite latent states with Markovian updates) using fewer than k states, while quantum generative models face no such bound. Efficient estimation algorithms are developed, and empirical results on synthetic and real data show that the estimated measure predicts performance gaps between resource-constrained classical and quantum Bayesian networks.

Significance. If the central theorem is correct, the work supplies a concrete, parameter-free criterion for identifying sequential distributions that impose strict memory lower bounds on classical streaming learners but not on quantum ones. The empirical demonstration that the measure correlates with observed performance differences provides a practical heuristic for selecting model classes in memory-limited learning settings. This could help guide quantum advantage searches in tasks with contextuality-like correlations.

major comments (2)
  1. [§3] §3, Theorem 3.1: The lower-bound argument establishes that strong k-contextuality forces at least k latent states under the Markovian streaming model, but the manuscript does not address whether non-Markovian classical models with the same total memory budget (or polynomial-time per-step computation) could achieve finite relative entropy with sub-k effective states; this gap weakens the claim that the result serves as a heuristic for general memory separations in learning.
  2. [§4.2] §4.2, Algorithm 1: The estimation procedure for strong k-contextuality is presented without a convergence guarantee or finite-sample error bound; because the empirical correlation in §5 relies on this estimator, the absence of such analysis leaves open the possibility that post-hoc choices of window size or threshold affect the reported predictive power.
minor comments (2)
  1. [Abstract and §2] Notation for relative entropy is inconsistent between the abstract (relative entropy) and §2 (KL divergence); a single term should be used throughout.
  2. [Figure 3] Figure 3 caption does not state the number of independent runs or error bars; adding this information would improve reproducibility.

Simulated Author's Rebuttal

2 responses · 0 unresolved

We thank the referee for the detailed and insightful report. We respond to each major comment below and outline the revisions we intend to implement.

read point-by-point responses

  1. Referee: [§3] §3, Theorem 3.1: The lower-bound argument establishes that strong k-contextuality forces at least k latent states under the Markovian streaming model, but the manuscript does not address whether non-Markovian classical models with the same total memory budget (or polynomial-time per-step computation) could achieve finite relative entropy with sub-k effective states; this gap weakens the claim that the result serves as a heuristic for general memory separations in learning.

    Authors: The theorem is indeed stated for the Markovian streaming model, which is the natural setting for analyzing finite-memory online learners with Markovian state updates. We do not claim a bound for arbitrary non-Markovian classical models, as those could in theory use different memory organizations. However, the result still provides a concrete criterion for when classical models with limited latent states fail, serving as a heuristic for identifying potential quantum advantages in memory-constrained scenarios. We will add a clarifying paragraph in the discussion section to address this scope explicitly. revision: partial

  2. Referee: [§4.2] §4.2, Algorithm 1: The estimation procedure for strong k-contextuality is presented without a convergence guarantee or finite-sample error bound; because the empirical correlation in §5 relies on this estimator, the absence of such analysis leaves open the possibility that post-hoc choices of window size or threshold affect the reported predictive power.

    Authors: We agree that a formal analysis of convergence and finite-sample bounds for the estimator in Algorithm 1 is missing. To address this, we will include additional empirical validation demonstrating that the estimated values and the observed performance gaps are robust to variations in window size and threshold parameters. We will also explicitly state that deriving theoretical guarantees remains an open question for future research. revision: yes

Circularity Check

0 steps flagged

Derivation of strong k-contextuality lower bound is self-contained

full rationale

The paper introduces a new quantifier called strong k-contextuality and proves that translation tasks exhibiting it cannot be represented to finite relative entropy by classical streaming models with fewer than k latent states. No quoted step reduces the claimed prediction or bound to a fitted parameter, self-referential equation, or load-bearing self-citation by construction. The proof is presented as following from the definition and model assumptions without circular reduction, and the empirical use as a performance predictor is described as independent. The modeling choice of finite-state streaming models is an explicit assumption rather than a derived result that loops back on itself.

Axiom & Free-Parameter Ledger

0 free parameters · 1 axioms · 0 invented entities

The central claim rests on a new definition of contextuality and standard assumptions about streaming models and relative entropy; no free parameters or invented entities are introduced in the abstract.

axioms (1)
  • domain assumption Classical streaming models with a bounded number of latent states are the relevant resource model for sequential learning tasks.
    Invoked to translate the contextuality measure into a memory lower bound.

pith-pipeline@v0.9.0 · 5719 in / 1136 out tokens · 35871 ms · 2026-05-19T03:53:21.703688+00:00 · methodology

discussion (0)

Sign in with ORCID, Apple, or X to comment. Anyone can read and Pith papers without signing in.

Lean theorems connected to this paper

Citations machine-checked in the Pith Canon. Every link opens the source theorem in the public Lean library.

What do these tags mean?
matches
The paper's claim is directly supported by a theorem in the formal canon.
supports
The theorem supports part of the paper's argument, but the paper may add assumptions or extra steps.
extends
The paper goes beyond the formal theorem; the theorem is a base layer rather than the whole result.
uses
The paper appears to rely on the theorem as machinery.
contradicts
The paper's claim conflicts with a theorem or certificate in the canon.
unclear
Pith found a possible connection, but the passage is too broad, indirect, or ambiguous to say the theorem truly supports the claim.

Reference graph

Works this paper leans on

33 extracted references · 33 canonical work pages

  1. [1]

    Quantum supremacy using a programmable supercon- ducting processor,

    F. Arute et al., “Quantum supremacy using a programmable supercon- ducting processor,” Nature, vol. 574, no. 7779, pp. 505–510, 2019

    work page 2019

  2. [2]

    Quantum computational advantage via 60-qubit 24-cycle random circuit sampling,

    Q. Zhu, S. Cao, F. Chen, M.-C. Chen, X. Chen, T.-H. Chung, H. Deng, Y . Du, D. Fan, M. Gong et al., “Quantum computational advantage via 60-qubit 24-cycle random circuit sampling,” Sci. Bull. , vol. 67, no. 3, pp. 240–245, 2022

    work page 2022

  3. [3]

    Quantum computational advantage using photons,

    H.-S. Zhong, H. Wang, Y .-H. Deng, M.-C. Chen, L.-C. Peng, Y .-H. Luo, J. Qin, D. Wu, X. Ding, Y . Huet al., “Quantum computational advantage using photons,” Science, vol. 370, no. 6523, pp. 1460–1463, 2020

    work page 2020

  4. [4]

    Enhancing generative models via quantum correlations,

    X. Gao, E. R. Anschuetz, S.-T. Wang, J. I. Cirac, and M. D. Lukin, “Enhancing generative models via quantum correlations,” Phys. Rev. X, vol. 12, p. 021037, 2022

    work page 2022

  5. [5]

    Interpretable quantum advantage in neural sequence learning,

    E. R. Anschuetz, H.-Y . Hu, J.-L. Huang, and X. Gao, “Interpretable quantum advantage in neural sequence learning,” PRX Quantum, vol. 4, p. 020338, 2023

    work page 2023

  6. [6]

    Arbitrary Polynomial Separations in Trainable Quantum Machine Learning,

    E. R. Anschuetz and X. Gao, “Arbitrary Polynomial Separations in Trainable Quantum Machine Learning,” Feb. 2024, arXiv:2402.08606 [quant-ph]. [Online]. Available: http://arxiv.org/abs/2402.08606

    work page arXiv 2024

  7. [7]

    The sheaf-theoretic structure of non-locality and contextuality,

    S. Abramsky and A. Brandenburger, “The sheaf-theoretic structure of non-locality and contextuality,”New J. Phys., vol. 13, no. 11, p. 113036, nov 2011

    work page 2011

  8. [8]

    Bayesian networks: A model of self-activated memory for evidential reasoning,

    J. Pearl, “Bayesian networks: A model of self-activated memory for evidential reasoning,” in Proceedings of the 7th Conference of the Cognitive Science Society, University of California, Irvine, CA, USA , 1985, pp. 329–334. [Online]. Available: https://cognitivesciencesociety. org/wp-content/uploads/2019/01/cogsci 7.pdf

    work page 1985

  9. [9]

    Statistical Inference for Probabilistic Func- tions of Finite State Markov Chains,

    L. E. Baum and T. Petrie, “Statistical Inference for Probabilistic Func- tions of Finite State Markov Chains,” Ann. Math. Stat. , vol. 37, no. 6, pp. 1554–1563, 1966

    work page 1966

  10. [10]

    Neural networks and physical systems with emergent collective computational abilities,

    J. J. Hopfield, “Neural networks and physical systems with emergent collective computational abilities,” Proc. Natl. Acad. Sci. U.S.A., vol. 79, no. 8, pp. 2554–2558, 1982

    work page 1982

  11. [11]

    Long short-term memory,

    S. Hochreiter and J. Schmidhuber, “Long short-term memory,” Neural Comput., vol. 9, no. 8, pp. 1735–1780, 1997

    work page 1997

  12. [12]

    Attention is all you need,

    A. Vaswani, N. Shazeer, N. Parmar, J. Uszkoreit, L. Jones, A. N. Gomez, L. Kaiser, and I. Polosukhin, “Attention is all you need,” in Proceedings of the 31st International Conference on Neural Information Processing Systems, ser. NIPS’17, I. Guyon, U. V . Luxburg, S. Bengio, H. Wallach, R. Fergus, S. Vishwanathan, and R. Garnett, Eds. Red Hook, NY , USA: ...

    work page 2017

  13. [13]

    Hidden Markov models as recurrent neural networks: An application to Alzheimer’s disease,

    M. Baucum, A. Khojandi, and T. Papamarkou, “Hidden Markov models as recurrent neural networks: An application to Alzheimer’s disease,” in 2021 IEEE 21st International Conference on Bioinformatics and Bioengineering (BIBE) . Los Alamitos, CA, USA: IEEE Computer Society, Oct. 2021, pp. 1–6

    work page 2021

  14. [14]

    A combinatorial approach to nonlocality and contextuality,

    A. Ac ´ın, T. Fritz, A. Leverrier, and A. B. Sainz, “A combinatorial approach to nonlocality and contextuality,” Commun. Math. Phys. , vol. 334, pp. 533–628, 2015

    work page 2015

  15. [15]

    Necessary and sufficient conditions for an extended noncontextuality in a broad class of quantum mechanical systems,

    J. V . Kujala, E. N. Dzhafarov, and J.-A. Larsson, “Necessary and sufficient conditions for an extended noncontextuality in a broad class of quantum mechanical systems,” Phys. Rev. Lett., vol. 115, p. 150401, Oct 2015

    work page 2015

  16. [16]

    Approximating independent set and coloring in random uniform hypergraphs,

    K. Plociennik, “Approximating independent set and coloring in random uniform hypergraphs,” in Mathematical Foundations of Computer Sci- ence 2008, E. Ochma ´nski and J. Tyszkiewicz, Eds. Berlin, Heidelberg: Springer Berlin Heidelberg, 2008, pp. 539–550

    work page 2008

  17. [17]

    Quantum inference on Bayesian networks,

    G. H. Low, T. J. Yoder, and I. L. Chuang, “Quantum inference on Bayesian networks,” Phys. Rev. A, vol. 89, p. 062315, Jun. 2014

    work page 2014

  18. [18]

    A maximization technique occurring in the statistical analysis of probabilistic functions of markov chains,

    L. E. Baum, T. Petrie, G. Soules, and N. Weiss, “A maximization technique occurring in the statistical analysis of probabilistic functions of markov chains,” Ann. Math. Statist. , vol. 41, no. 1, pp. 164–171, 1970

    work page 1970

  19. [19]

    The ITensor software library for tensor network calculations,

    M. Fishman, S. R. White, and E. M. Stoudenmire, “The ITensor software library for tensor network calculations,” SciPost Phys. Codebases, p. 4, 2022. [Online]. Available: https://scipost.org/10.21468/ SciPostPhysCodeb.4

    work page 2022

  20. [20]

    Molecular Biology (Pro- moter Gene Sequences),

    C. Harley, R. Reynolds, and M. Noordewier, “Molecular Biology (Pro- moter Gene Sequences),” UCI Machine Learning Repository, 1990, DOI: https://doi.org/10.24432/C5S01D

    work page doi:10.24432/c5s01d 1990

  21. [21]

    The long-range interaction landscape of gene promoters,

    A. Sanyal, B. R. Lajoie, G. Jain, and J. Dekker, “The long-range interaction landscape of gene promoters,” Nature, vol. 489, no. 7414, pp. 109–113, 2012

    work page 2012

  22. [22]

    Classifying promoters by interpreting the hidden information of dna sequences via deep learning and combination of continuous fasttext n- grams,

    N. Q. K. Le, E. K. Y . Yapp, N. Nagasundaram, and H.-Y . Yeh, “Classifying promoters by interpreting the hidden information of dna sequences via deep learning and combination of continuous fasttext n- grams,” Frontiers in bioengineering and biotechnology , vol. 7, p. 305, 2019

    work page 2019

  23. [23]

    Quantum generalizations of Bell’s inequality,

    B. S. Cirel’son, “Quantum generalizations of Bell’s inequality,” Lett. Math. Phys., vol. 4, pp. 93–100, 1980

    work page 1980

  24. [24]

    On the complex- ity and verification of quantum random circuit sampling,

    A. Bouland, B. Fefferman, C. Nirkhe, and U. Vazirani, “On the complex- ity and verification of quantum random circuit sampling,” Nat. Phys. , vol. 15, no. 2, pp. 159–163, 2019

    work page 2019

  25. [25]

    Computational power of correlations,

    J. Anders and D. E. Browne, “Computational power of correlations,” Phys. Rev. Lett. , vol. 102, p. 050502, Feb 2009. [Online]. Available: https://link.aps.org/doi/10.1103/PhysRevLett.102.050502

    work page doi:10.1103/physrevlett.102.050502 2009

  26. [26]

    Contextuality in measurement-based quantum computation,

    R. Raussendorf, “Contextuality in measurement-based quantum computation,” Phys. Rev. A , vol. 88, p. 022322, Aug 2013. [Online]. Available: https://link.aps.org/doi/10.1103/PhysRevA.88.022322

    work page doi:10.1103/physreva.88.022322 2013

  27. [27]

    Contextual fraction as a measure of contextuality,

    S. Abramsky, R. S. Barbosa, and S. Mansfield, “Contextual fraction as a measure of contextuality,” Phys. Rev. Lett. , vol. 119, p. 050504, Aug

    work page

  28. [28]

    E., & Bacon, D

    [Online]. Available: https://link.aps.org/doi/10.1103/PhysRevLett. 119.050504

    work page doi:10.1103/physrevlett

  29. [29]

    Contextuality supplies the ‘magic’ for quantum computation,

    M. Howard, J. Wallman, V . Veitch, and J. Emerson, “Contextuality supplies the ‘magic’ for quantum computation,” Nature, vol. 510, no. 7505, pp. 351–355, Jun. 2014. [Online]. Available: https: //www.nature.com/articles/nature13460

    work page 2014

  30. [30]

    Contextuality as a Resource for Models of Quantum Computation with Qubits,

    J. Bermejo-Vega, N. Delfosse, D. E. Browne, C. Okay, and R. Raussendorf, “Contextuality as a Resource for Models of Quantum Computation with Qubits,” Physical Review Letters , vol. 119, no. 12, p. 120505, Sep. 2017. [Online]. Available: https: //link.aps.org/doi/10.1103/PhysRevLett.119.120505

    work page doi:10.1103/physrevlett.119.120505 2017

  31. [31]

    The Interplay between Quantum Contextuality and Wigner Negativity,

    P.-E. Emeriau, “The Interplay between Quantum Contextuality and Wigner Negativity,” Apr. 2022, arXiv:2204.08782 [quant-ph]. [Online]. Available: http://arxiv.org/abs/2204.08782

    work page arXiv 2022

  32. [32]

    Contextuality and Wigner negativity are equivalent for continuous-variable quantum measure- ments,

    R. I. Booth, U. Chabaud, and P.-E. Emeriau, “Contextuality and Wigner negativity are equivalent for continuous-variable quantum measure- ments,” Phys. Rev. Lett., vol. 129, p. 230401, 2022

    work page 2022

  33. [33]

    The role of cohomology in quantum computation with magic states,

    R. Raussendorf, C. Okay, M. Zurel, and P. Feldmann, “The role of cohomology in quantum computation with magic states,” Quantum, vol. 7, p. 979, Apr. 2023, arXiv:2110.11631 [quant-ph]. [Online]. Available: http://arxiv.org/abs/2110.11631

    work page arXiv 2023