Non-asymptotic Approximation Error Bounds of Parameterized Quantum Circuits

Summary

This is a solid paper for approximating Hölder smooth functions using parameterized Quantum Circuits (PQC). The results show that using PQC for approximation can achieve better results than those in Lu's paper, especially when $K$, the length of the local region of Taylor expansion, is not large and the dimension $d$ is large.

Strengths

Finding the approximation rate for different structures in deep learning is an important task to understand deep learning. The author presents approximation results for PQC, and I find this result interesting.

Weaknesses

1. For continuous and Lipschitz continuous functions, the author only establishes the Universal Approximation Theory. Can the author improve the result to find the approximation rate based on [22] cited in the paper? 2. The author's result is better than Lu's paper since they consider the approximation by $L^\infty$-norm. In [22], it is shown that for the $L^p$ norm, the coefficient in Lu's paper can also not exponentially depend on $d$. In this case, is the result in this paper still better than Lu's paper? 3. Based on my knowledge, in Lu's paper, they obtain a better rate of $K$ than the author's paper due to the use of the bit extraction technique, achieved by ReLU FNN, but the parameters in this technique need to be very large. Therefore, can your paper provide the bound of parameters? If so, this would be a significant benefit of your paper. 4. The structure of the neural network is hard to train since it is not wide but deep when $K$ is large. Can you make the neural network shallower and wider? 5. I think some tables and comments in the appendix can be shown on the main page such as Table S1.

Questions

Mentioned in the Weaknesses.

Rating

7

Confidence

4

Soundness

3

Presentation

2

Contribution

3

Limitations

All right.

Summary

The authors explore the power and limitations of parameterized quantum circuits (PQCs). They show that a large class of multivariate polynomials and smooth functions can be efficiently (approximately) represented by PQCs. More importantly, they show that the requirements of such PQCs compare favorably to their classical counterparts (deep ReLu nets, etc.)

Strengths

The main strength of the paper is that it addresses an important problem of practical and theoretical interest regarding the power and limitations of parameterized quantum circuits. The results are novel, and the highlighted open problems are of great interest.

Weaknesses

See questions below.

Questions

Page 1: Maybe you can early on present a figure depicting some PQC (and a deep ReLu net, for comparison)? This could help the reader relate to the subject matter. Page 2: Can PQCs trivially simulate classical deep learning nets? Page 3: Should you define mixed states for comparison with the pure states? Should you emphasize that the chosen basis is complete? Page 4: How is Equation (1) derived? Equation (2) captures your notion of expressibility, right? Page 5: Can you please add some more discussion about Theorem 2? Page 6: Can you please elaborate on Lines 220 -- 221? Page 7: Please elaborate on the caption of Figure 2. Line 263: Why is such an $f$ interesting? Page 8: Figure 3: Please elaborate on the caption. Figure 4: What is the moral regarding K? The higher the better? :) Page 9: Discussion is good. Please add some more future work/next steps. Please do not wait until the end of the paper to state that your work is (???) the first of its kind :) What is the relationship of your work to (classical or quantum) computational complexity, and Turing machines? Please provide some discussion about how your work connects to the theory of computation.

Rating

7

Confidence

3

Soundness

3

Presentation

4

Contribution

3

Limitations

None.

Summary

In this work, the authors aim to build a theoretical understanding of parameterized quantum circuits via non-asymptotic approximation error performance analysis. In particular, they demonstrate the advantages of PQCs over classical ones if specific smoothness criteria can be satisfied. The simulation results can further corroborate their theoretical understanding.

Strengths

1. The paper provides a different theoretical perspective of understanding PQCs using a non-asymptotic viewpoint in addition to the universal approximation theory. 2. Their established non-asymptotic PQC approximation error bounds are technically correct 3. The simulation results can corroborate the theoretical results.

Weaknesses

1. The authors' theoretical analysis of PQCs relies on the assumption of continuous or smooth target functions, which hinders the theoretical usage from a broader case of non-smooth and non-continuous target functions. 2. The numerical simulation is less convincing than practical machine learning datasets, so the actual machine learning applications are expected to validate the proposed theory. 3. the experimental validation could be designed to corroborate the theoretical results, e.g., the target function relying on Holder's discussions on smooth and continuous functions.

Questions

1. how can the authors generalize the proposed theory to those cases if the target function is non-smooth and non-continuous? 2. What is the most significant advantage of the non-asymptotical analysis on PQCs compared to the universal approximation theory? 3. Is there a different or new discovery of the PQC's setup if using the authors' new theoretical perspective?

Rating

7

Confidence

5

Soundness

3

Presentation

3

Contribution

3

Limitations

1. The proposed theorems rely on continuous or smooth target functions, which hinders their application to broader use cases. 2. The numerical simulations cannot corroborate the specific smooth and continuous functions.

Summary

This paper studies the expressiveness of parameterized circuits to perform multivariate function approximation. This serves as a quantum counterpart to the theoretical results of classical machine learning, namely the universal approximation theorem. Theoretical results provide bounds on the approximation error of parameterized circuits with bounds on the quantum resources required. Finally, numerical experiments are provided, showing that parameterized quantum circuits are able to approximate multivariate functions with improved accuracy as the number of parameters increases.

Strengths

- This paper uses ideas from quantum signal processing to study the expressivity of parameterized quantum circuits, thereby serving as a first step for bridging the gap between quantum algorithms for matrix functions and quantum machine learning. This is a very natural idea, and is better motivated than many other ansatz used in variational quantum algorithms. Generally speaking, I think it is valuable for works in (quantum) machine learning to be guided by results with theoretical guarantees as this typically leads to better algorithm design. - The overall paper is well-written and clear to understand. - The numerical experiments appear promising and supplement the theoretical results well, although the parameter counts are fairly large even for the small test-cases presented.

Weaknesses

- The use of ideas from quantum signal processing is a bit of a double-edged sword. While Theorem 3 provides a non-asymptotic error bound, the quantum resources (circuit width and depth) are only asymptotic bounds. Presumably, the resources required for performing the LCU circuit are not very practical for NISQ devices, and it is likely that there are significant improvements to be made. - It would be nice to include code for the numerical experiments.

Questions

- In the second paragraph of Sec 3.1, why is the number of parameters $s+d$, rather than simply $s$? If $d>s$, then only $s$ variables are relevant. - In Sec 3.2, why were Bernstein polynomials chosen over other polynomial approximations, such as truncated Taylor series expansions? Are there other ways, and if so, what are the drawbacks? - In Theorem 2, how does $n$ depend on $\epsilon$? I think it would make more sense to express the resource costs in terms of $1/\epsilon$. - In Theorem 3, why does $n$ no longer depend on $\epsilon$? Does it mean that both $ \epsilon$ and $n$ could be simultaneously chosen to be arbitrarily small? - I am curious about how the PQCs were implemented for the numerical experiments. I assume analytical formulas for the approximating polynomial were used, rather than full circuit implementations with the overhead of LCU, right?

Rating

7

Confidence

3

Soundness

3

Presentation

3

Contribution

3

Limitations

There are no major negative societal impacts of this work.