Pseudo-dimension of quantum circuits
This provides theoretical learning guarantees for quantum circuits, addressing the problem of understanding their complexity for quantum computing researchers.
The authors characterized the expressive power of quantum circuits using pseudo-dimension, proving polynomial upper bounds on output probability distributions in terms of circuit depth and gate count, and demonstrated that at least one class of circuit output states has exponential state complexity while polynomial-size quantum circuits are PAC-learnable.
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.