  The superiority of variational quantum algorithms (VQAs) such as quantum
neural networks (QNNs) and variational quantum eigen-solvers (VQEs) heavily
depends on the expressivity of the employed ansatze. Namely, a simple ansatze
is insufficient to capture the optimal solution, while an intricate ansatze
leads to the hardness of the trainability. Despite its fundamental importance,
an effective strategy of measuring the expressivity of VQAs remains largely
unknown. Here, we exploit an advanced tool in statistical learning theory,
i.e., covering number, to study the expressivity of VQAs. In particular, we
first exhibit how the expressivity of VQAs with an arbitrary ansatze is upper
bounded by the number of quantum gates and the measurement observable. We next
explore the expressivity of VQAs on near-term quantum chips, where the system
noise is considered. We observe an exponential decay of the expressivity with
increasing circuit depth. We also utilize the achieved expressivity to analyze
the generalization of QNNs and the accuracy of VQE. We numerically verify our
theory employing VQAs with different levels of expressivity. Our work opens the
avenue for quantitative understanding of the expressivity of VQAs.

Quantum Physics