Data Complexity: a threshold between Classical and Quantum Machine Learning -- Part I

• URL: http://arxiv.org/abs/2509.16410v1
• Date: Fri, 19 Sep 2025 20:35:45 GMT
• Title: Data Complexity: a threshold between Classical and Quantum Machine Learning -- Part I
• Authors: Christophe Pere,
• Abstract summary: Quantum machine learning (QML) holds promise for accelerating pattern recognition, optimization, and data analysis.<n>Existing research often emphasizes algorithms and hardware, while the role of data itself in determining quantum advantage has received less attention.<n>We argue that data complexity is central to defining these conditions.
• Score: 0.0
• License: http://creativecommons.org/licenses/by-sa/4.0/
• Abstract: Quantum machine learning (QML) holds promise for accelerating pattern recognition, optimization, and data analysis, but the conditions under which it can truly outperform classical approaches remain unclear. Existing research often emphasizes algorithms and hardware, while the role of data itself in determining quantum advantage has received less attention. We argue that data complexity -- the structural, statistical, algorithmic, and topological richness of datasets -- is central to defining these conditions. Beyond qubit counts or circuit depth, the real bottleneck lies in the cost of embedding, representing, and generalizing from data. In this paper (Part I of a two-part series), we review classical and quantum metrics of data complexity, including entropy, correlations, compressibility, and topological invariants such as persistent homology and topological entanglement entropy. We also examine their implications for trainability, scalability, and error tolerance in QML. Part II will develop a unified framework and provide empirical benchmarks across datasets, linking these complexity measures to practical performance.

Related papers

• AQER: a scalable and efficient data loader for digital quantum computers [62.40228216126285]
  We develop AQER, a scalable AQL method that constructs the loading circuit by systematically reducing entanglement in target states.<n>We conduct systematic experiments to evaluate the effectiveness of AQER, using synthetic datasets, classical image and language datasets, and a quantum many-body state datasets with up to 50 qubits.
  arXiv  Detail & Related papers  (2026-02-02T14:39:42Z)
• Qlustering: Harnessing Network-Based Quantum Transport for Data Clustering [0.0]
  We introduce Qlustering, a quantum-inspired algorithm for unsupervised learning that leverages network-based quantum transport to perform data clustering.<n>Data are encoded as input states in steady-binding Hamiltonian currents governed by the Lindblad equation.<n>We benchmark Qlustering on synthetic datasets, a localization problem, and real-world chemical data.
  arXiv  Detail & Related papers  (2025-10-26T15:55:01Z)
• Is data-efficient learning feasible with quantum models? [0.0]
  We show that quantum kernel methods (QKMs) can achieve low error rates with less training data compared to classical counterparts.<n>We introduce a new analytical tool to the QML domain, derived for classical kernel methods, which can be aimed at investigating the classical-quantum gap.<n>This research contributes to a deeper understanding of the generalization benefits of QKM models and potentially a broader family of QML models.
  arXiv  Detail & Related papers  (2025-08-26T21:14:52Z)
• Quantum-Accelerated Neural Imputation with Large Language Models (LLMs) [0.0]
  This paper introduces Quantum-UnIMP, a novel framework that integrates shallow quantum circuits into an LLM-based imputation architecture.<n>Our experiments on benchmark mixed-type datasets demonstrate that Quantum-UnIMP reduces imputation error by up to 15.2% for numerical features (RMSE) and improves classification accuracy by 8.7% for categorical features (F1-Score) compared to state-of-the-art classical and LLM-based methods.
  arXiv  Detail & Related papers  (2025-07-11T02:00:06Z)
• An Efficient Quantum Classifier Based on Hamiltonian Representations [50.467930253994155]
  Quantum machine learning (QML) is a discipline that seeks to transfer the advantages of quantum computing to data-driven tasks.<n>We propose an efficient approach that circumvents the costs associated with data encoding by mapping inputs to a finite set of Pauli strings.<n>We evaluate our approach on text and image classification tasks, against well-established classical and quantum models.
  arXiv  Detail & Related papers  (2025-04-13T11:49:53Z)
• QCircuitBench: A Large-Scale Dataset for Benchmarking Quantum Algorithm Design [63.02824918725805]
  Quantum computing is recognized for the significant speedup it offers over classical computing through quantum algorithms.<n>QCircuitBench is the first benchmark dataset designed to evaluate AI's capability in designing and implementing quantum algorithms.
  arXiv  Detail & Related papers  (2024-10-10T14:24:30Z)
• Quantum reservoir computing on random regular graphs [0.0]
  Quantum reservoir computing (QRC) is a low-complexity learning paradigm that combines input-driven many-body quantum systems with classical learning techniques.<n>We study information localization, dynamical quantum correlations, and the many-body structure of the disordered Hamiltonian.<n>Our findings thus provide guidelines for the optimal design of disordered analog quantum learning platforms.
  arXiv  Detail & Related papers  (2024-09-05T16:18:03Z)
• Efficient Learning for Linear Properties of Bounded-Gate Quantum Circuits [62.46800898243033]
  Recent progress in quantum learning theory prompts a question: can linear properties of a large-qubit circuit be efficiently learned from measurement data generated by varying classical inputs?<n>We prove that the sample complexity scaling linearly in $d$ is required to achieve a small prediction error, while the corresponding computational complexity may scale exponentially in d.<n>We propose a kernel-based method leveraging classical shadows and truncated trigonometric expansions, enabling a controllable trade-off between prediction accuracy and computational overhead.
  arXiv  Detail & Related papers  (2024-08-22T08:21:28Z)
• Benchmarking quantum machine learning kernel training for classification tasks [0.0]
  This study focuses on quantum kernel methods in the context of classification tasks.<n>It examines the performance of Quantum Kernel Estimation (QKE) and Quantum Kernel Training (QKT) in connection with two quantum feature mappings.<n> Experimental results indicate that quantum methods exhibit varying performance across different datasets.
  arXiv  Detail & Related papers  (2024-08-17T10:53:06Z)
• Discovering physical laws with parallel symbolic enumeration [67.36739393470869]
  We introduce parallel symbolic enumeration (PSE) to efficiently distill generic mathematical expressions from limited data.<n>Experiments show that PSE achieves higher accuracy and faster computation compared to the state-of-the-art baseline algorithms.<n> PSE represents an advance in accurate and efficient data-driven discovery of symbolic, interpretable models.
  arXiv  Detail & Related papers  (2024-07-05T10:41:15Z)
• Quantum topological data analysis via the estimation of the density of states [17.857341127079305]
  We develop a quantum topological data analysis protocol based on the estimation of the density of states (DOS) of the Laplacian. We test our protocol on noiseless and noisy quantum simulators and run examples on IBM quantum processors.
  arXiv  Detail & Related papers  (2023-12-12T09:43:04Z)
• Unifying (Quantum) Statistical and Parametrized (Quantum) Algorithms [65.268245109828]
  We take inspiration from Kearns' SQ oracle and Valiant's weak evaluation oracle. We introduce an extensive yet intuitive framework that yields unconditional lower bounds for learning from evaluation queries.
  arXiv  Detail & Related papers  (2023-10-26T18:23:21Z)
• A didactic approach to quantum machine learning with a single qubit [68.8204255655161]
  We focus on the case of learning with a single qubit, using data re-uploading techniques. We implement the different proposed formulations in toy and real-world datasets using the qiskit quantum computing SDK.
  arXiv  Detail & Related papers  (2022-11-23T18:25:32Z)
• Amortized Inference for Causal Structure Learning [72.84105256353801]
  Learning causal structure poses a search problem that typically involves evaluating structures using a score or independence test. We train a variational inference model to predict the causal structure from observational/interventional data. Our models exhibit robust generalization capabilities under substantial distribution shift.
  arXiv  Detail & Related papers  (2022-05-25T17:37:08Z)

This list is automatically generated from the titles and abstracts of the papers in this site.

This site does not guarantee the quality of this site (including all information) and is not responsible for any consequences.