  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.
