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

Journal of Physics Complexity

General Vapnik–Chervonenkis dimension bounds for quantum circuit learning

Chih-Chieh Chen, Masaru Sogabe, Kodai Shiba, Katsuyoshi Sakamoto, Tomah Sogabe

Published Nov 2, 2022• 1 citation
Publisher

Abstract

Abstract Quantifying the model complexity of quantum circuits provides a guide to avoid overfitting in quantum machine learning. Previously we established a Vapnik–Chervonenkis (VC) dimension upper bound for ‘encoding-first’ quantum circuits, where the input layer is the first layer of the circuit. In this work, we prove a general VC dimension upper bound for quantum circuit learning including ‘data re-uploading’ circuits, where the input gates can be single qubit rotations anywhere in the circuit. A linear lower bound is also constructed. The properties of the bounds and approximation-estimation trade-off considerations are discussed.

DOI
10.1088/2632-072x/ac9f9b

Related papers

On the Expressibility and Overfitting of Quantum Circuit Learning

Chih-Chieh Chen, Masaya Watabe, Kodai Shiba +3 more

Applying quantum processors to model a high-dimensional function approximator is a typical method in quantum machine learning with potential advantage. It is conjectured that the unitarity of quantum circuits provides possible regularization to avoid overfitting. However, it is not clear how the regularization interplays with the expressibility under the limitation of current Noisy-Intermediate Scale Quantum devices. In this article, we perform simulations and theoretical analysis of the quantum circuit learning problem with hardware-efficient ansatz. Thorough numerical simulations show that the expressibility and generalization error scaling of the ansatz saturate when the circuit depth increases, implying the automatic regularization to avoid the overfitting issue in the quantum circuit learning scenario. This observation is supported by the theory on PAC learnability, which proves that VC dimension is upper bounded due to the locality and unitarity of the hardware-efficient ansatz. Our study provides supporting evidence for automatic regularization by unitarity to suppress overfitting and guidelines for possible performance improvement under hardware constraints.

ACM Transactions on Quantum Computing•Jun 30, 2021•44 citations

One qubit as a universal approximant

Adrián Pérez-Salinas, David López-Núñez, Artur García-Sáez +2 more

A single-qubit circuit can approximate any bounded complex function stored in the degrees of freedom defining its quantum gates. The single-qubit approximant presented in this work is operated through a series of gates that take as their parametrization the independent variable of the target function and an additional set of adjustable parameters. The independent variable is re-uploaded in every gate while the parameters are optimized for each target function. The output state of this quantum circuit becomes more accurate as the number of re-uploadings of the independent variable increases, i.e., as more layers of gates parameterized with the independent variable are applied. In this work, we provide two proofs of this claim related to both the Fourier series and the universal approximation theorem for neural networks, and we benchmark both methods against their classical counterparts. We further implement a single-qubit approximant in a real superconducting qubit device, demonstrating how the ability to describe a set of functions improves with the depth of the quantum circuit. This work shows the robustness of the re-uploading technique on quantum machine learning.

arXiv:2102.04032•Physical Review A•Jul 2, 2021•71 citations

Re-uploading quantum data: a universal function approximator for quantum inputs

Hyunho Cha, Daniel K. Park, Jungwoo Lee

Quantum data re-uploading has proved powerful for classical inputs, where repeatedly encoding features into a small circuit yields universal function approximation. Extending this idea to quantum inputs remains underexplored, as the information contained in a quantum state is not directly accessible in classical form. We propose and analyze a quantum data re-uploading architecture in which a qubit interacts sequentially with fresh copies of an arbitrary input state. The circuit can approximate any bounded continuous function using only one ancilla qubit and single-qubit measurements, provided that sufficiently many copies of the input state and, in general, sufficiently many layers are available. By alternating entangling unitaries with mid-circuit resets of the input register, the architecture realizes a discrete cascade of completely positive and trace-preserving maps, analogous to collision models in open quantum system dynamics. Our framework provides a space-efficient and expressive approach to designing quantum machine learning models that operate directly on quantum data.

arXiv:2509.18530•Quantum•Oct 29, 2026•0 citations

Predictive Performance of Deep Quantum Data Re-uploading Models

Wang, Xin, Han-Xiao Tao, Re-Bing Wu

Quantum machine learning models incorporating data re-uploading circuits have garnered significant attention due to their exceptional expressivity and trainability. However, their ability to generate accurate predictions on unseen data, referred to as the predictive performance, remains insufficiently investigated. This study reveals a fundamental limitation in predictive performance when deep encoding layers are employed within the data re-uploading model. Concretely, we theoretically demonstrate that when processing high-dimensional data with limited-qubit data re-uploading models, their predictive performance progressively degenerates to near random-guessing levels as the number of encoding layers increases. In this context, the repeated data uploading cannot mitigate the performance degradation. These findings are validated through experiments on both synthetic linearly separable datasets and real-world datasets. Our results demonstrate that when processing high-dimensional data, the quantum data re-uploading models should be designed with wider circuit architectures rather than deeper and narrower ones.

arXiv:2505.20337•May 24, 2025•0 citations

Non-asymptotic Approximation Error Bounds of Parameterized Quantum Circuits

Zhan Yu, Qiuhao Chen, Yuling Jiao +4 more

Parameterized quantum circuits (PQCs) have emerged as a promising approach for quantum neural networks. However, understanding their expressive power in accomplishing machine learning tasks remains a crucial question. This paper investigates the expressivity of PQCs for approximating general multivariate function classes. Unlike previous Universal Approximation Theorems for PQCs, which are either nonconstructive or rely on parameterized classical data processing, we explicitly construct data re-uploading PQCs for approximating multivariate polynomials and smooth functions. We establish the first non-asymptotic approximation error bounds for these functions in terms of the number of qubits, quantum circuit depth, and number of trainable parameters. Notably, we demonstrate that for approximating functions that satisfy specific smoothness criteria, the quantum circuit size and number of trainable parameters of our proposed PQCs can be smaller than those of deep ReLU neural networks. We further validate the approximation capability of PQCs through numerical experiments. Our results provide a theoretical foundation for designing practical PQCs and quantum neural networks for machine learning tasks that can be implemented on near-term quantum devices, paving the way for the advancement of quantum machine learning.

arXiv:2310.07528•neural information processing systems•Jan 1, 2024•4 citations

Sample complexity of learning parametric quantum circuits

Haoyuan Cai, Qi Ye, Dong-Ling Deng

Abstract Quantum computers hold unprecedented potentials for machine learning applications. Here, we prove that physical quantum circuits are probably approximately correct learnable on a quantum computer via empirical risk minimization: to learn a parametric quantum circuit with at most n c gates and each gate acting on a constant number of qubits, the sample complexity is bounded by O ~ ( n c + 1 ) . In particular, we explicitly construct a family of variational quantum circuits with O(n c+1) elementary gates arranged in a fixed pattern, which can represent all physical quantum circuits consisting of at most n c elementary gates. Our results provide a valuable guide for quantum machine learning in both theory and practice.

arXiv:2107.09078•Quantum Science and Technology•Jan 26, 2022•21 citations
Abstract Quantifying the model complexity of quantum circuits provides a guide to avoid overfitting in quantum machine learning. Previously we established a Vapnik–Chervonenkis (VC) dimension upper bound for ‘encoding-first’ quantum circuits, where the input layer is the first layer of the circuit. In this work, we prove a general VC dimension upper bound for quantum circuit learning including ‘data re-uploading’ circuits, where the input gates can be single qubit rotations anywhere in the circuit. A linear lower bound is also constructed. The properties of the bounds and approximation-estimation trade-off considerations are discussed.
Applying quantum processors to model a high-dimensional function approximator is a typical method in quantum machine learning with potential advantage. It is conjectured that the unitarity of quantum circuits provides possible regularization to avoid overfitting. However, it is not clear how the regularization interplays with the expressibility under the limitation of current Noisy-Intermediate Scale Quantum devices. In this article, we perform simulations and theoretical analysis of the quantum circuit learning problem with hardware-efficient ansatz. Thorough numerical simulations show that the expressibility and generalization error scaling of the ansatz saturate when the circuit depth increases, implying the automatic regularization to avoid the overfitting issue in the quantum circuit learning scenario. This observation is supported by the theory on PAC learnability, which proves that VC dimension is upper bounded due to the locality and unitarity of the hardware-efficient ansatz. Our study provides supporting evidence for automatic regularization by unitarity to suppress overfitting and guidelines for possible performance improvement under hardware constraints.
A single-qubit circuit can approximate any bounded complex function stored in the degrees of freedom defining its quantum gates. The single-qubit approximant presented in this work is operated through a series of gates that take as their parametrization the independent variable of the target function and an additional set of adjustable parameters. The independent variable is re-uploaded in every gate while the parameters are optimized for each target function. The output state of this quantum circuit becomes more accurate as the number of re-uploadings of the independent variable increases, i.e., as more layers of gates parameterized with the independent variable are applied. In this work, we provide two proofs of this claim related to both the Fourier series and the universal approximation theorem for neural networks, and we benchmark both methods against their classical counterparts. We further implement a single-qubit approximant in a real superconducting qubit device, demonstrating how the ability to describe a set of functions improves with the depth of the quantum circuit. This work shows the robustness of the re-uploading technique on quantum machine learning.
Quantum data re-uploading has proved powerful for classical inputs, where repeatedly encoding features into a small circuit yields universal function approximation. Extending this idea to quantum inputs remains underexplored, as the information contained in a quantum state is not directly accessible in classical form. We propose and analyze a quantum data re-uploading architecture in which a qubit interacts sequentially with fresh copies of an arbitrary input state. The circuit can approximate any bounded continuous function using only one ancilla qubit and single-qubit measurements, provided that sufficiently many copies of the input state and, in general, sufficiently many layers are available. By alternating entangling unitaries with mid-circuit resets of the input register, the architecture realizes a discrete cascade of completely positive and trace-preserving maps, analogous to collision models in open quantum system dynamics. Our framework provides a space-efficient and expressive approach to designing quantum machine learning models that operate directly on quantum data.
Quantum machine learning models incorporating data re-uploading circuits have garnered significant attention due to their exceptional expressivity and trainability. However, their ability to generate accurate predictions on unseen data, referred to as the predictive performance, remains insufficiently investigated. This study reveals a fundamental limitation in predictive performance when deep encoding layers are employed within the data re-uploading model. Concretely, we theoretically demonstrate that when processing high-dimensional data with limited-qubit data re-uploading models, their predictive performance progressively degenerates to near random-guessing levels as the number of encoding layers increases. In this context, the repeated data uploading cannot mitigate the performance degradation. These findings are validated through experiments on both synthetic linearly separable datasets and real-world datasets. Our results demonstrate that when processing high-dimensional data, the quantum data re-uploading models should be designed with wider circuit architectures rather than deeper and narrower ones.
Parameterized quantum circuits (PQCs) have emerged as a promising approach for quantum neural networks. However, understanding their expressive power in accomplishing machine learning tasks remains a crucial question. This paper investigates the expressivity of PQCs for approximating general multivariate function classes. Unlike previous Universal Approximation Theorems for PQCs, which are either nonconstructive or rely on parameterized classical data processing, we explicitly construct data re-uploading PQCs for approximating multivariate polynomials and smooth functions. We establish the first non-asymptotic approximation error bounds for these functions in terms of the number of qubits, quantum circuit depth, and number of trainable parameters. Notably, we demonstrate that for approximating functions that satisfy specific smoothness criteria, the quantum circuit size and number of trainable parameters of our proposed PQCs can be smaller than those of deep ReLU neural networks. We further validate the approximation capability of PQCs through numerical experiments. Our results provide a theoretical foundation for designing practical PQCs and quantum neural networks for machine learning tasks that can be implemented on near-term quantum devices, paving the way for the advancement of quantum machine learning.
Abstract Quantum computers hold unprecedented potentials for machine learning applications. Here, we prove that physical quantum circuits are probably approximately correct learnable on a quantum computer via empirical risk minimization: to learn a parametric quantum circuit with at most n c gates and each gate acting on a constant number of qubits, the sample complexity is bounded by O ~ ( n c + 1 ) . In particular, we explicitly construct a family of variational quantum circuits with O(n c+1) elementary gates arranged in a fixed pattern, which can represent all physical quantum circuits consisting of at most n c elementary gates. Our results provide a valuable guide for quantum machine learning in both theory and practice.