Sample Complexity of Learning Parametric Quantum Circuits. (arXiv:2107.09078v2 [quant-ph] UPDATED)

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 …

arxiv complexity learning