Pseudo-dimension of quantum circuits

Abstract

We characterize the expressive power of quantum circuits with the pseudo-dimension, a measure of complexity for probabilistic concept classes. We prove pseudo-dimension bounds on the output probability distributions of quantum circuits; the upper bounds are polynomial in circuit depth and number of gates. Using these bounds, we exhibit a class of circuit output states out of which at least one has exponential state complexity, and moreover demonstrate that quantum circuits of known polynomial size and depth are PAC-learnable.

arXiv comment22 pages, 1 figure; corrected Lemma 3.8, this does not change our results

References in corpus (3)

• Many-body quantum state tomography with neural networks
• Prediction, Learning, Uniform Convergence, and Scale-sensitive Dimensions
• The Learnability of Quantum States

Cited by in corpus (22)

• The effect of data encoding on the expressive power of variational quantum machine learning models
• Generalization in quantum machine learning from few training data
• Efficient measure for the expressivity of variational quantum algorithms
• Quantum Machine Learning: from physics to software engineering
• Understanding quantum machine learning also requires rethinking generalization
• Out-of-distribution generalization for learning quantum dynamics
• On the statistical complexity of quantum circuits
• Variational quantum process tomography
• Learning quantum circuits of some $T$ gates
• Dynamical simulation via quantum machine learning with provable generalization
• Structural risk minimization for quantum linear classifiers
• Quantum Deep Hedging
• Learning quantum states and unitaries of bounded gate complexity
• Learning Quantum Processes and Hamiltonians via the Pauli Transfer Matrix
• Generalization of Quantum Machine Learning Models Using Quantum Fisher Information Metric
• Effects of quantum resources on the statistical complexity of quantum circuits
• Expressivity of Variational Quantum Machine Learning on the Boolean Cube
• Entanglement-induced provable and robust quantum learning advantages
• Encoding-dependent generalization bounds for parametrized quantum circuits
• A learning theory for quantum photonic processors and beyond
• Clifford Circuits can be Properly PAC Learned if and only if $\text{RP}=\text{NP}$
• PAC-learning of free-fermionic states is NP-hard