Sample Complexity of Learning Parametric Quantum Circuits
This provides a theoretical foundation for quantum machine learning, addressing sample complexity for researchers and practitioners in the field.
The paper tackles the problem of learning parametric quantum circuits by proving they are PAC learnable via empirical risk minimization, achieving a sample complexity bound of $ ilde{O}(n^{c+1})$ for circuits with up to $n^c$ gates.
Quantum computers hold unprecedented potentials for machine learning applications. Here, we prove that physical quantum circuits are PAC (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 $\tilde{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.