Efficient Measure for the Expressivity of Variational Quantum Algorithms

The superiority of variational quantum algorithms (VQAs) such as quantum neural networks (QNNs) and variational quantum eigensolvers (VQEs) heavily depends on the expressivity of the employed Ansatze. Namely, a simple Ansatz is insufficient to capture the optimal solution, while an intricate Ansatz leads to the hardness of 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. Particularly, 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 Letter opens the avenue for quantitative understanding of the expressivity of VQAs.

Automated summary

This paper investigates the expressivity of VQAs using the covering number tool in statistical learning theory. The expressivity is found to depend on the number of quantum gates and measurement observables, and it exponentially decays with increasing circuit depth under the consideration of system noise. Numerical verification using VQAs with different levels of expressivity is conducted to analyze their applications in QNN generalization and VQE accuracy.