Challenges
Datasets
Workspaces
Papers
Discussions
Leaderboard
Log inSign up
Challenges
Datasets
Workspaces
Papers
Discussions
Leaderboard
Blog
Job Board
Q3AS

© 2026 Aqora Quantum S.A.S.

TermsPrivacyLegal Notice

arXiv:2507.11604 · IEEE International Conference on Quantum Computing and Engineering (QCE)

$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

Published Aug 30, 2025• 0 citations
arXivHTMLPDF

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.

DOI
10.1109/qce65121.2025.00260

Related papers

Quantifying the Limits of Classical Machine Learning Models Using Contextuality

Eric R. Anschuetz, Mariesa Teo, Willers Yang +4 more

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.

IEEE International Conference on Quantum Computing and Engineering (QCE)•Sep 15, 2024•1 citation

Enhancing Generative Models via Quantum Correlations

Xun Gao, Eric R. Anschuetz, Sheng-Tao Wang +2 more

Generative modeling using samples drawn from the probability distribution constitutes a powerful approach for unsupervised machine learning.Quantum mechanical systems can produce probability distributions that exhibit quantum correlations which are difficult to capture using classical models.We show theoretically that such quantum-inspired correlations provide a powerful resource for generative modeling.In particular, we provide an unconditional proof of separation in expressive power between a class of widely used generative models, known as Bayesian networks, and its minimal quantum-inspired extension.We show that this expressivity enhancement is associated with quantum nonlocality and quantum contextuality.Furthermore, we numerically test this separation on standard machine-learning data sets and show that it holds for practical problems.The possibility of quantum-inspired enhancement demonstrated in this work not only sheds light on the design of useful quantum machine-learning protocols but also provides inspiration to draw on ideas from quantum foundations to improve purely classical algorithms.

arXiv:2101.08354•Physical Review X•May 13, 2022•77 citations

Interpretable Quantum Advantage in Neural Sequence Learning

Eric R. Anschuetz, Hong-Ye Hu, Jin-Long Huang +1 more

Quantum neural networks have been widely studied in recent years, given their potential practical utility and recent results regarding their ability to efficiently express certain classical data.However, analytic results to date rely on assumptions and arguments from complexity theory.Because of this, there is little intuition as to the source of the expressive power of quantum neural networks or for which classes of classical data any advantage can be reasonably expected to hold.Here, we study the relative expressive power between a broad class of neural network sequence models and a class of recurrent models based on Gaussian operations with non-Gaussian measurements.We explicitly show that quantum contextuality is the source of an unconditional memory separation in the expressivity of the two model classes.We use this intuition to study the relative performance of our introduced model on a standard translation data set exhibiting linguistic contextuality.In doing so, we demonstrate that our introduced quantum models are able to outperform state-of-the-art classical models even in practice.

arXiv:2209.14353•PRX Quantum•Jun 8, 2023•30 citations

Quantum Memory Advantage from Contextuality

Shiroman Prakash

Quantum contextuality is a vital non-classical resource, yet illuminating the precise mechanisms through which it enables unconditional computational advantages remains a challenge. We translate graph-theoretic formulations of contextuality into an unconditional quantum memory advantage for formal language recognition. We define a promise problem on an exclusivity graph $G$ where any classical finite automaton respecting exclusivity requires $N \ge χ(G)$ memory states, whereas a QFA requires a memory of dimension $d = ξ(G)$. The gap between these bounds isolates a structural, information-theoretic incompatibility between classical and quantum descriptions that we term \textit{representational contextuality}. For Boolean orthogonality graphs, this exacts an exponential classical memory penalty ($d=\mathcal{O}(n)$ vs $N=2^{Ω(n)}$). Finally, we demonstrate a sharp algorithmic phase transition: allowing the classical machine a finite confusability of mutually exclusive events reduces this exponential classical memory cost to $\mathcal{O}(n)$.

quant-pharXiv:2607.00507•Jul 2, 2026•0 citations

Arbitrary Polynomial Separations in Trainable Quantum Machine Learning

Eric R. Anschuetz, Xun Gao

Recent theoretical results in quantum machine learning have demonstrated a general trade-off between the expressive power of quantum neural networks (QNNs) and their trainability; as a corollary of these results, practical exponential separations in expressive power over classical machine learning models are believed to be infeasible as such QNNs take a time to train that is exponential in the model size. We here circumvent these negative results by constructing a hierarchy of efficiently trainable QNNs that exhibit unconditionally provable, polynomial memory separations of arbitrary constant degree over classical neural networks—including state-of-the-art models, such as Transformers—in performing a classical sequence modeling task. This construction is also computationally efficient, as each unit cell of the introduced class of QNNs only has constant gate complexity. We show that contextuality—informally, a quantitative notion of semantic ambiguity—is the source of the expressivity separation, suggesting that other learning tasks with this property may be a natural setting for the use of quantum learning algorithms.

arXiv:2402.08606•Quantum•Jan 20, 2026•3 citations

On establishing learning separations between classical and quantum machine learning with classical data

Casper Gyurik, Vedran Dunjko

Despite years of effort, the quantum machine learning community has only been able to show quantum learning advantages for certain contrived cryptography-inspired datasets in the case of classical data. In this note, we discuss the challenges of finding learning problems that quantum learning algorithms can learn much faster than any classical learning algorithm, and we study how to identify such learning problems. Specifically, we reflect on the main concepts in computational learning theory pertaining to this question, and we discuss how subtle changes in definitions can mean conceptually significantly different tasks, which can either lead to a separation or no separation at all. Moreover, we study existing learning problems with a provable quantum speedup to distill sets of more general and sufficient conditions (i.e., ``checklists'') for a learning problem to exhibit a separation between classical and quantum learners. These checklists are intended to streamline one's approach to proving quantum speedups for learning problems, or to elucidate bottlenecks. Finally, to illustrate its application, we analyze examples of potential separations (i.e., when the learning problem is build from computational separations, or when the data comes from a quantum experiment) through the lens of our approach.

arXiv:2208.06339•Aug 12, 2022•8 citations
kkk-Contextuality as a Heuristic for Memory Separations in Learning
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 strongkkk-contextuality, and prove that any translation task exhibiting strongkkk-contextuality is unable to be represented to finite relative entropy by a classical streaming model with fewer thankkklatent 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. Strongkkk-contextuality thus emerges as a measure to help identify problems that are difficult for classical computers, but may not be for quantum computers.
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.
Generative modeling using samples drawn from the probability distribution constitutes a powerful approach for unsupervised machine learning.Quantum mechanical systems can produce probability distributions that exhibit quantum correlations which are difficult to capture using classical models.We show theoretically that such quantum-inspired correlations provide a powerful resource for generative modeling.In particular, we provide an unconditional proof of separation in expressive power between a class of widely used generative models, known as Bayesian networks, and its minimal quantum-inspired extension.We show that this expressivity enhancement is associated with quantum nonlocality and quantum contextuality.Furthermore, we numerically test this separation on standard machine-learning data sets and show that it holds for practical problems.The possibility of quantum-inspired enhancement demonstrated in this work not only sheds light on the design of useful quantum machine-learning protocols but also provides inspiration to draw on ideas from quantum foundations to improve purely classical algorithms.
Quantum neural networks have been widely studied in recent years, given their potential practical utility and recent results regarding their ability to efficiently express certain classical data.However, analytic results to date rely on assumptions and arguments from complexity theory.Because of this, there is little intuition as to the source of the expressive power of quantum neural networks or for which classes of classical data any advantage can be reasonably expected to hold.Here, we study the relative expressive power between a broad class of neural network sequence models and a class of recurrent models based on Gaussian operations with non-Gaussian measurements.We explicitly show that quantum contextuality is the source of an unconditional memory separation in the expressivity of the two model classes.We use this intuition to study the relative performance of our introduced model on a standard translation data set exhibiting linguistic contextuality.In doing so, we demonstrate that our introduced quantum models are able to outperform state-of-the-art classical models even in practice.
Quantum contextuality is a vital non-classical resource, yet illuminating the precise mechanisms through which it enables unconditional computational advantages remains a challenge. We translate graph-theoretic formulations of contextuality into an unconditional quantum memory advantage for formal language recognition. We define a promise problem on an exclusivity graph GGG where any classical finite automaton respecting exclusivity requires N≥χ(G)N \ge χ(G)N≥χ(G) memory states, whereas a QFA requires a memory of dimension d=ξ(G)d = ξ(G)d=ξ(G). The gap between these bounds isolates a structural, information-theoretic incompatibility between classical and quantum descriptions that we term \textit{representational contextuality}. For Boolean orthogonality graphs, this exacts an exponential classical memory penalty (d=O(n)d=\mathcal{O}(n)d=O(n) vs N=2Ω(n)N=2^{Ω(n)}N=2Ω(n)). Finally, we demonstrate a sharp algorithmic phase transition: allowing the classical machine a finite confusability of mutually exclusive events reduces this exponential classical memory cost to O(n)\mathcal{O}(n)O(n).
Recent theoretical results in quantum machine learning have demonstrated a general trade-off between the expressive power of quantum neural networks (QNNs) and their trainability; as a corollary of these results, practical exponential separations in expressive power over classical machine learning models are believed to be infeasible as such QNNs take a time to train that is exponential in the model size. We here circumvent these negative results by constructing a hierarchy of efficiently trainable QNNs that exhibit unconditionally provable, polynomial memory separations of arbitrary constant degree over classical neural networks—including state-of-the-art models, such as Transformers—in performing a classical sequence modeling task. This construction is also computationally efficient, as each unit cell of the introduced class of QNNs only has constant gate complexity. We show that contextuality—informally, a quantitative notion of semantic ambiguity—is the source of the expressivity separation, suggesting that other learning tasks with this property may be a natural setting for the use of quantum learning algorithms.
Despite years of effort, the quantum machine learning community has only been able to show quantum learning advantages for certain contrived cryptography-inspired datasets in the case of classical data. In this note, we discuss the challenges of finding learning problems that quantum learning algorithms can learn much faster than any classical learning algorithm, and we study how to identify such learning problems. Specifically, we reflect on the main concepts in computational learning theory pertaining to this question, and we discuss how subtle changes in definitions can mean conceptually significantly different tasks, which can either lead to a separation or no separation at all. Moreover, we study existing learning problems with a provable quantum speedup to distill sets of more general and sufficient conditions (i.e., ``checklists'') for a learning problem to exhibit a separation between classical and quantum learners. These checklists are intended to streamline one's approach to proving quantum speedups for learning problems, or to elucidate bottlenecks. Finally, to illustrate its application, we analyze examples of potential separations (i.e., when the learning problem is build from computational separations, or when the data comes from a quantum experiment) through the lens of our approach.