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 Ansätze. 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 Ansätze 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.

Figure 1

Overview of the expressivity of VQAs. The expressivity of the employed Ansätze of VQA rules its hypothesis space $\mathcal{H}$ (solid blue ellipse). When $\mathcal{H}$ has the modest size and covers the target concept (gray solid star), VQA can attain a good performance. Conversely, when $\mathcal{H}$ fails to cover the target concept (green solid star), due to the limited expressivity, VQA achieves a poor performance.

Figure 2

The geometric intuition of covering number. Covering number concerns the minimum number of spherical balls with radius $\epsilon$ that occupies the whole space.

Figure 3

Simulation results of QNN with the varied layer number $L$. The label Tr-$L=a$ (or Te-$L=a$) refers to the train (or test) accuracy of QNN with layer number $L=a$. The outer (or inner) plot shows the statistical (top-1) results of QNNs with $L=\{1,2,\dots ,5\}$ ($L=\{1,2\}$). Vertical bars refer to the variance of obtained results.

Figure 4

Simulation results of VQE. The labels “Under,” “Modest,” and “Over” refer to the estimated energy of VQEs when the employed Ansätze have the restricted, modest, and overwhelming expressivity, respectively. “Ha” (hartrees) and “Å” (angstroms) refer to the units for energy and the bond lengths. The inner plot shows the energy gap of VQEs in “Over” and “Modest” cases.