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.
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.
k-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 strongk-contextuality, and prove that any translation task exhibiting strongk-contextuality is unable to be represented to finite relative entropy by a classical streaming model with fewer thanklatent 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. Strongk-contextuality thus emerges as a measure to help identify problems that are difficult for classical computers, but may not be for quantum computers.
The use of quantum computing for machine learning is among the most exciting prospective applications of quantum technologies. However, machine learning tasks where data is provided can be considerably different than commonly studied computational tasks. In this work, we show that some problems that are classically hard to compute can be easily predicted by classical machines learning from data. Using rigorous prediction error bounds as a foundation, we develop a methodology for assessing potential quantum advantage in learning tasks. The bounds are tight asymptotically and empirically predictive for a wide range of learning models. These constructions explain numerical results showing that with the help of data, classical machine learning models can be competitive with quantum models even if they are tailored to quantum problems. We then propose a projected quantum model that provides a simple and rigorous quantum speed-up for a learning problem in the fault-tolerant regime. For near-term implementations, we demonstrate a significant prediction advantage over some classical models on engineered data sets designed to demonstrate a maximal quantum advantage in one of the largest numerical tests for gate-based quantum machine learning to date, up to 30 qubits.
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.
Classical probabilistic models of (noisy) quantum systems are not only relevant for understanding the non-classical features of quantum mechanics, but they are also useful for determining the possible advantage of using quantum resources for information processing tasks. A common feature of these models is the presence of inaccessible information, as captured by the concept of preparation contextuality: There are ensembles of quantum states described by the same density operator, and hence operationally indistinguishable, and yet in any probabilistic (ontological) model, they should be described by distinct probability distributions. In this work, we quantify the inaccessible information of a model in terms of the maximum distinguishability of probability distributions associated to any pair of ensembles with identical density operators, as quantified by the total variation distance of the distributions. We obtain a family of lower bounds on this maximum distinguishability in terms of experimentally measurable quantities. In the case of an ideal qubit this leads to a lower bound of, approximately, 0.07. These bounds can also be interpreted as a new class of robust preparation non-contextuality inequalities. Our non-contextuality inequalities are phrased in terms of generalizations of max-relative entropy and trace distance for general operational theories, which could be of independent interest. Under sufficiently strong noise any quantum system becomes preparation non-contextual, i.e., can be described by models with zero inaccessible information. Using our non-contextuality inequalities, we show that this can happen only if the noise channel has the average gate fidelity less than or equal to 1/D(1+1/2+...+1/D), where D is the dimension of the Hilbert space.
Quantifying entanglement for quantum states whose density matrices are unknown is a difficult task, but also becomes more and more necessary because of the fast development of quantum engineering. Machine learning provides practical solutions to this fundamental problem, where one has to train a proper machine learning model to predict entanglement measures of unknown quantum states based on experimentally measurable data, say, moments of density matrices or correlation data produced by local measurements. In this paper, we compare the performance of these two different machine learning approaches systematically. Particularly, we first show that the approach based on moments enjoys a remarkable advantage over that based on correlation data, though the cost of measuring moments is much higher. Next, since correlation data is much easier to obtain experimentally, we try to better its performance by proposing a hybrid quantum-classical machine learning framework for this problem, where the key is to train optimal local measurements, or even optimal tensor products of single-qubit observables, to generate more informative correlation data. Our numerical simulations show that the new hybrid framework brings us comparable performance with the approach based on moments to quantify entanglement, and furthermore, it turns out that the new hybrid framework has a nice noise-resistant capability when handling realistic correlation data.
Machine learning is being increasingly used for the detection, diagnosis, and treatment of cancer. However, models often struggle with biological data due to high dimensionality, limited sample diversity, and complex feature interactions. Recent works have investigated the potential for quantum machine learning models to exhibit improved performance over classical models on this kind of complex data, but have often lacked rigorous empirical evaluation of quantum advantage. In this work, we develop a methodology for fair benchmarking of quantum and classical machine learning models, based on the Red Cedar quantum machine learning and resource estimation framework and AutoML-optimized classical neural networks. We assess the potential for quantum advantage in machine learning across tabular, omics, and spatial oncological datasets drawn from the existing quantum machine learning literature, with a range of preprocessing methods, and find no evidence of quantum advantage. Our results suggest that the field should prioritize analyzing higher-dimensional, more biologically realistic datasets to make meaningful progress toward practical quantum advantage in oncological classification problems.