The central aim of machine learning is to generate accurate predictions on unseen data, a process known as generalization. Classical machine learning has extensively investigated this, developing theoretical upper bounds on generalization error based on training data size and model complexity. Quantum machine learning (QML), a burgeoning field, involves training parameterized quantum circuits to analyze classical or quantum datasets. While QML shows promise in offering advantages over classical methods in certain scenarios, particularly in terms of sample complexity for quantum data analysis, the conditions for accurate generalization in QML remain poorly understood. Research has advanced our knowledge of QML trainability, but this is distinct from generalization. Overfitting, a challenge in classical machine learning, could also hinder QML. The required training data size for QML generalization is a key open question. Naively, one might expect exponential training data scaling for unitaries acting on exponentially large Hilbert spaces. However, the more relevant scenario is learning unitaries represented by polynomial-depth quantum circuits, efficiently implementable on quantum computers. This work directly addresses this gap by focusing on the relationship between generalization error, the number of parameterized gates (T), and the training data size (N) in variational QML models. The authors aim to provide theoretical bounds on generalization error, clarifying the sufficient training data size for good generalization in efficiently implementable QML models.

The paper reviews existing literature on generalization in classical machine learning, highlighting the development of upper bounds on generalization error as a function of training data size and model complexity. It also surveys the progress in QML, noting the excitement surrounding the field but emphasizing the lack of understanding regarding the conditions needed for accurate generalization in QML. The authors mention existing research on the trainability of QML models, distinguishing it from the question of generalization, and point out the lack of thorough investigation into the training data size required for QML generalization. Previous studies suggesting exponentially scaling training data requirements for arbitrary unitaries are discussed, contrasting them with the more realistic scenario of learning unitaries represented by polynomial-depth quantum circuits.

The authors develop a theoretical framework to analyze generalization in variational QML. They model a quantum machine learning model (QMLM) as a parameterized quantum channel, a completely positive trace-preserving (CPTP) map parameterized by continuous (θ) and discrete (κ) parameters. The input data, either classical or quantum, is encoded into a quantum state ρ(x). The QMLM acts on a subsystem of this state, producing an output state. The loss function ℓ(α; x; y) is defined as the trace of a loss observable Oloss acting on the output state. The training error Rs(α) is the average loss over a training dataset S of size N, and the prediction error R(α) is the expected loss over the data distribution P. The generalization error gen(α) is the difference between R(α) and Rs(α). The authors' main contribution lies in establishing probabilistic bounds on this generalization error. Their proof strategy involves deriving novel metric entropy bounds (logarithms of covering numbers) for QMLMs, which quantify the complexity of the model class. These bounds, combined with the chaining technique from the theory of random processes, yield generalization error bounds. The analysis considers several scenarios: (1) Basic QMLM with T independent parameterized gates; (2) Gate-sharing QMLM where gates are reused M times; (3) Gate-sharing QMLM under optimization, accounting for the changes Δt in each gate's parameters during optimization; and (4) Gate-sharing QMLM with a variable structure, where the number of gates changes during optimization. For each scenario, the authors derive corresponding generalization error bounds. The numerical investigations involve two applications: quantum convolutional neural networks (QCNNs) for quantum phase classification, and variational unitary compiling using the VAns algorithm. Matrix Product State (MPS) techniques and the Simultaneous Perturbation Stochastic Approximation (SPSA) algorithm are utilized for optimization in the QCNN experiments. The VAns algorithm, combined with qFactor, optimizes over both discrete and continuous parameters for unitary compiling. The authors compare the training and testing errors across different training data sizes and initializations.

The core findings are presented as theorems that provide upper bounds on the generalization error of variational QMLMs. **Theorem 1 (Basic QMLM):** The generalization error is bounded by O(T log T/N). This shows that for efficiently implementable QMLMs (T ∈ poly(n)), a polynomial-sized training dataset (N ∈ poly(n)) suffices for good generalization. **Theorem 2 (Gate-sharing QMLM):** Even with gate reuse (M times), the generalization error bound improves to O(T log(MT)/N), highlighting that multiple copies of the QMLM don't significantly worsen generalization. **Theorem 3 (Gate-sharing QMLM under optimization):** If only K gates change significantly (Δt), the generalization error bound becomes O(min1≤K≤T {K log(MT)/N + Σt=K+1T Δt}), improving generalization when only a subset of parameters are significantly modified. The numerical experiments confirm these theoretical findings. In quantum phase classification using QCNNs, good generalization is observed even with constant-size training datasets. In unitary compiling of the Quantum Fourier Transform (QFT), the study demonstrates that polynomial-sized training datasets are sufficient, a significant improvement over previous exponential scaling approaches. When initializing the unitary compiling close to the solution, the experiments show that only two training data points can suffice for good generalization, even for systems with up to 40 qubits. This latter observation aligns with Theorem 3, which suggests improved generalization with good initialization. The numerical results demonstrate that the training requirements scale linearly with the number of qubits when training data consists of random computational basis states.

The results demonstrate that QML models, even with a limited number of trainable parameters, can generalize well from surprisingly small training datasets. The theoretical bounds, confirmed by numerical experiments, provide a crucial foundation for understanding and improving QML algorithms. The findings have significant implications for several applications. For quantum phase classification, the study provides a theoretical explanation for the good generalization performance of QCNNs, resolving a previous heuristic understanding. In unitary compiling, the results suggest significant improvements are possible in terms of reduced data requirements. This impacts variational dynamical simulation, quantum error correction code discovery, and quantum autoencoders and GANs by providing quantitative guidance on the necessary training data size. The study compares favorably to prior work, offering stronger and more general bounds, and discusses the implications for quantum advantage in QML. The authors highlight that while they don't prove a quantum advantage directly, their bounds are essential for understanding the conditions under which a quantum advantage might be achieved. Specifically, a quantum advantage could be demonstrated when a QML model generalizes well with few trainable gates, whereas classical models require significantly higher complexity.

The paper establishes novel generalization bounds for variational QML, demonstrating that good generalization is achievable with surprisingly small training datasets. This is especially true for efficiently implementable QMLMs, where polynomial-sized data suffices. Numerical experiments confirm these bounds, highlighting the implications for quantum phase classification and unitary compiling. The work suggests several avenues for future research, including investigating the generalization behavior of exponentially large QMLMs, tightening bounds using application-specific prior knowledge, and analyzing distribution-specific effects on generalization performance.

The generalization bounds derived in the paper are valid for arbitrary data-generating distributions, and therefore might be overly pessimistic for specific favorable distributions. The study focuses on variational QMLMs and might not directly generalize to other QML approaches. The numerical experiments, while demonstrating the feasibility and potential of the theoretical bounds, are limited in scope and may not capture the full complexity of real-world scenarios. Further research is needed to explore the generalization behavior of exponentially large QMLMs and to investigate how application-specific knowledge could be used to tighten the provided bounds.