Does Data Complexity Predict Quantum Advantage? A framework, a pre-specified test, and an attribution of the measured edge

The gist The paper introduces a theoretical framework for quantifying data complexity as a determinant of classical vs. quantum machine learning performance, arguing that data structure, representation, and encoding resources are central to defining conditions for quantum advantage.

Defining Data Complexity

Data complexity is defined as the structural richness of a dataset, expressed in terms of the minimal resources required to represent, compress, or learn from the data distribution (Page 2). This concept extends across classical and quantum regimes by considering both classical metrics like entropy, correlations, compressibility and quantum metrics such as entanglement entropy and topological invariants such as persistent homology and topological entanglement entropy (Page 1). The paper formalizes this by defining a composite classical data complexity measure: Cdata = λ1S(D) + λ2Icorr(D) + λ3K(D)+λ4Ctop(D), where S(D) is Distributional entropy, Icorr(D) captures higher-order dependencies via multivariate mutual information, K(D) reflects Kolmogorov complexity / compressibility, and Ctop(D) incorporates Topological complexity / manifold invariants (Page 6).

Quantum Data Metrics

In the quantum regime, data complexity is measured through several quantum-native properties. These include:

1. Average bipartite entanglement entropy Sent = 1/N P i S(ρ(i)A), which quantifies the degree of quantum correlations across bipartitions (Page 7).

2. Multipartite total correlation Imulti = P j S(ρj) − S(ρ1…n), capturing higher-order dependencies beyond pairwise correlations (Page 7).

3. Effective rank of ensemble kernel rankeff(KE) = (P i λi)2 / P i λ2i, which indicates broader Hilbert-space support and greater sample complexity (Page 8).

4. Nonclassicality / magic monotone N(ρ), quantifying the extent to which states depart from stabilizer (Clifford) structure, reflecting computational resources unavailable to classical simulation (Page 8).

5. Quantum Fisher information F = TrρL2, which measures sensitivity of states to parameter variations and encoding capacity for precision (Page 8).

6. Topological quantum complexity C(q)top(E), which is defined as a composite measure incorporating Topological entanglement entropy, the Euler characteristic of the quantum state manifold ME, and persistent homology contributions of dimension k (Page 9).

Impact on Circuit Size and Trainability

The complexity of data directly constrains the quantum resources needed for representation, as data with high complexity requires deeper circuits to capture higher-order correlations (Page 9). This relationship is modeled by scaling functions where qubit count Q(Cdata) ∝ log(H(Cdata)) and circuit depth D(Cdata) ∼ O(f(Cdata)), reflecting the growth in entangling resources required (Page 9). Furthermore, data complexity impacts trainability through the barren plateau problem: "High data complexity (Cdata >> 1) accelerates the onset of barren plateaus, demanding deeper circuits and amplifying optimization difficulties" (Page 11). A practical trainability condition is expressed as Var[g(θ)] ≳ ϵ, where high-complexity datasets amplify this difficulty by demanding deeper circuits (Page 12).

Expressibility vs. Generalization

A central challenge in QML is balancing the expressibility of a quantum model with its ability to generalize from training data (Page 10). The relationship between these two is formalized by the generalization error as E[ϵgen] ≈ ϵemp + λ E(U) − Cdata, where E(U) is circuit expressibility and Cdata is data complexity (Page 10). Optimal learning occurs when circuit expressibility is commensurate with the data complexity (E(U) ≈ Cdata) (Page 10). When E(U) >> Cdata, the model risks overfitting, while when E(U) << Cdata, it underfits due to a lack of capacity to represent higher-order patterns (Page 10).

Practical Boundaries and Constraints

The feasibility of quantum advantage is constrained by several practical factors. First, data complexity interacts with hardware error rates: as complexity increases, error accumulation that scales superlinearly with circuit depth occurs (Page 13). Second, sample complexity is a constraint; while theory suggests polynomial scaling under structured settings, the cost of preparing or measuring samples can overwhelm expressivity benefits (Page 13). Third, hardware constraints like qubit count and connectivity limit the depth of circuits that can run reliably (Page 14). Finally, topological structure adds difficulty: topological invariants enrich the definition of data complexity by highlighting global, manifold-level structure (Page 16).

Encoding Challenges

The process of data encoding is a critical resource bottleneck where complexity materializes (Page 15). The cost of encoding classical data into quantum states can offset speedups, illustrating a tension where richer encodings amplify the potential advantage in learning complex patterns, but simultaneously increase the physical and algorithmic costs (Page 15). Simple encodings offer low-cost solutions for structured data, while amplitude encoding provides maximal expressivity at a steep cost (Page 15). The paper concludes that the path to quantum advantage in learning will not be determined by qubit counts alone but by a deeper understanding of the interplay between complexity, topology, noise, and trainability (Page 16).

The research suggests that the feasibility of QML advantage is conditional on data structure and encoding resources rather than just asymptotic algorithmic performance. This framework motivates complexity-based benchmarks and calls for a topological PAC-bound to formalize the boundary where quantum representations provably surpass classical models (Page 17). It establishes that high-complexity datasets push circuits into barren plateaus faster, necessitating a joint framework that unifies data complexity with hardware limitations (Page 18). Ultimately, the quest for quantum advantage hinges on understanding how intrinsic complexity amplifies or mitigates noise and trainability in variational circuits (Page 19). This paper provides a unified language for comparing dataset difficulty across classical and quantum domains (Page 20). It aims to shift the discourse on QML advantage from hardware- and algorithm-centric metrics to a data-centric view (Page 20).

The paper introduces a theoretical framework for quantifying data complexity as a determinant of classical vs. quantum machine learning performance, arguing that data structure, representation, and encoding resources are central to defining conditions for quantum advantage

Data complexity is defined as the structural richness of a dataset, expressed in terms of the minimal resources required to represent, compress, or learn from the data distribution

This concept extends across classical and quantum regimes by considering both classical metrics like entropy, correlations, compressibility and quantum metrics such as entanglement entropy and topological invariants such as persistent homology and topological entanglement entropy

Data complexity is defined as a composite classical data complexity measure: Cdata = λ1S(D) + λ2Icorr(D) + λ3K(D)+λ4Ctop(D), where S(D) is Distributional entropy, Icorr(D) captures higher-order dependencies via multivariate mutual information, K(D) reflects Kolmogorov complexity / compressibility, and Ctop(D) incorporates Topological complexity / manifold invariants

In the quantum regime, data complexity is measured through several quantum-native properties.

These include:

Average bipartite entanglement entropy Sent = 1/N P i S(ρ(i)A), which quantifies the degree of quantum correlations across bipartitions

Multipartite total correlation Imulti = P j S(ρj) − S(ρ1…n), capturing higher-order dependencies beyond pairwise correlations

Effective rank of ensemble kernel rankeff(KE) = (P i λi)2 / P i λ2i, which indicates broader Hilbert-space support and greater sample complexity

Nonclassicality / magic monotone N(ρ), quantifying the extent to which states depart from stabilizer (Clifford) structure, reflecting computational resources unavailable to classical simulation

Quantum data complexity is measured through several quantum-native properties.</ref:2509.

1. Data-Complexity-Aware Model Selection: The system can select between classical and quantum approaches by calculating a composite complexity score using Eq. 7, which sums Distributional entropy S(D), Correlation order Icorr(D), Kolmogorov complexity K(D)+λ4Ctop(D). This allows the system to determine if the required resources scale favorably for a quantum advantage or if classical methods are sufficient, based on whether the data complexity is low or high.

2. Circuit Design Optimization: The system can optimize variational quantum circuits by balancing expressibility and data complexity, aiming for a regime where circuit expressibility is commensurate with the data complexity (E(U) ≈ Cdata). This ensures that models are neither overfit nor underfit, directly addressing the generalization error formula: E[ϵgen] ≈ ϵemp + λ E(U) − Cdata.

3. Trainability-Guided Resource Allocation: The system can dynamically adjust circuit depth and qubit count based on data complexity to avoid barren plateaus. Specifically, it uses the condition that Var[g(θ)] ≳ ϵ to set a practical trainability boundary, ensuring that high-complexity datasets indirectly amplify this scaling by demanding deeper circuits do not lead to optimization difficulties where training becomes effectively impossible.

4. Encoding Strategy Adaptation: The system can choose the optimal data encoding scheme based on the dataset's structure and hardware constraints. It can select between basis or angle encoding for low-rank data, or amplitude encoding for high-expressivity needs, recognizing that encoding challenges are not merely technical obstacles but rather define the frontier between classical and quantum learning capabilities.

5. Topological Feature Utilization: The system can leverage topological invariants like Persistent homology and topological entanglement entropy to capture global manifold structure in both classical and quantum data. This allows the AI to recognize structures that require models to capture multi-scale connectivity, loops, and voids, potentially identifying domains where quantum systems naturally encode these features.

Quantum machine learning (QML) holds promise for pattern recognition, optimization, and data analysis, but the conditions under which it can outperform classical methods remain unclear. We propose data complexity--the structural, statistical, algorithmic, and topological richness of a dataset--as a central axis for stating such conditions, and test the resulting framework under a pre-specified benchmark. The central predictive claim fails. A composite complexity measure does not predict the budget-matched quantum edge across 27 datasets in leave-one-dataset-out validation (pooled R 2=-0.32, versus a pre-specified threshold of 0.4). The failure is strongly coupled to the classical baseline: against logistic regression, the selector reaches R 2=+0.13 and the parity family wins 17% of cells, whereas against the best of six standard classical models performance falls to R 2=-0.94, with parity winning only 1%. The apparent signal therefore tracks classical model error rather than a robust quantum contribution. The tested encoding and reduction procedures further leave little nonlinear headroom for the downstream model to exploit; gradient boosting matches a linear probe across the tested widths. The null is also constrained by the regime: quantum performance is at chance in 81.5% of cells. Yet a deliberately constructed quantum-signature control produces a +0.42 edge under a structure-aware measurement, while generic models required to learn that structure remain near chance. Thus the null result is not evidence that quantum-sensitive structure cannot exist. Rather, in the tested regime, data complexity alone does not predict quantum advantage: the observable edge depends jointly on the classical baseline, accessible data structure, representation and model headroom, and whether quantum-sensitive structure is accessible to the measurement.