Provable Advantage of Parameterized Quantum Circuit in Function
  Approximation
Zhan Yu Qiuhao Chen Yuling Jiao Yinan Li Xiliang Lu Xin Wang Jerry Zhijian Yang
Understanding the power of parameterized quantum circuits (PQCs) in
accomplishing machine learning tasks is one of the most important questions in
quantum machine learning. In this paper, we analyze the expressivity of PQCs
through the lens of function approximation. Previously established universal
approximation theorems for PQCs are mainly nonconstructive, leading us to the
following question: How large do the PQCs need to be to approximate the target
function up to a given error? We exhibit explicit constructions of data
re-uploading PQCs for approximating continuous and smooth functions and
establish quantitative approximation error bounds in terms of the width, the
depth and the number of trainable parameters of the PQCs. To achieve this, we
utilize techniques from quantum signal processing and linear combinations of
unitaries to construct PQCs that implement multivariate polynomials. We
implement global and local approximation techniques using Bernstein polynomials
and local Taylor expansion and analyze their performances in the quantum
setting. We also compare our proposed PQCs to nearly optimal deep neural
networks in approximating high-dimensional smooth functions, showing that the
ratio between model sizes of PQC and deep neural networks is exponentially
small with respect to the input dimension. This suggests a potentially novel
avenue for showcasing quantum advantages in quantum machine learning.