Universal Approximation Theorem and error bounds for quantum neural networks and quantum reservoirs

Lukas Gonon, Antoine Jacquier

TL;DR

This paper establishes theoretical guarantees for the approximation capabilities of quantum neural networks (QNNs) and quantum reservoir computing. It provides precise error bounds, showing that QNNs can approximate a broad class of functions with an error that scales favorably with the number of qubits and weights, crucially avoiding the "curse of dimensionality" seen in some classical approaches.

What Problem Does This Paper Address?

Classical neural networks have a well-established theoretical foundation in the form of Universal Approximation Theorems (UATs), which guarantee their ability to approximate any continuous function. While quantum computing offers potential advantages for machine learning, the theoretical underpinnings of QNNs, particularly regarding their approximation power and the resources (qubits, parameters) required, have been less understood. Specifically, there was a lack of precise error bounds for QNNs, making it difficult to quantify their performance and compare them to classical counterparts. This paper aims to bridge this gap by providing rigorous UATs and error bounds for both trainable QNNs and randomized quantum circuits (quantum reservoirs).

Methods

The authors construct specific quantum circuits and analyze their approximation capabilities. For trainable QNNs, they leverage a variational quantum circuit architecture. For quantum reservoir computing, they employ a circuit where parameters are randomly initialized and fixed, with only a final readout layer being trainable. A key technique involves analyzing the Fourier transforms of the functions being approximated, drawing parallels to classical methods that utilize Fourier series. The proofs rely on constructing specific quantum operations and employing probabilistic arguments to bound the approximation error. They also extend their results to $L^\infty$ error bounds on compact sets, offering a stronger guarantee than mean-square error.

Datasets

Not discussed in the paper. The paper focuses on theoretical guarantees for approximating arbitrary functions, rather than empirical evaluation on specific datasets.

Key Insights and Ideas

  • Quantum Advantage in Approximation: QNNs, particularly those with integrable Fourier transforms, can approximate functions with an error that scales favorably with the number of qubits and weights, avoiding the "curse of dimensionality" that can plague classical methods when dealing with high-dimensional inputs.
  • Reservoir Computing for Quantum ML: Randomizing circuit parameters and training only a readout layer (quantum reservoir computing) offers a computationally simpler training paradigm (akin to linear regression) while still achieving universal approximation.
  • Bridging Classical and Quantum Theory: The paper draws strong parallels between classical UATs and their quantum counterparts, using Fourier analysis as a common ground to establish theoretical guarantees.
  • Resource Efficiency: The derived bounds suggest that achieving a certain approximation accuracy $\varepsilon$ requires a number of qubits that grows logarithmically with $\varepsilon^{-1}$, and a number of weights that scales quadratically with $\varepsilon^{-2}$.

Key Results

  • Trainable QNNs: A quantum neural network with $O(\varepsilon^{-2})$ weights and $O(\lceil \log_2(\varepsilon^{-1}) \rceil)$ qubits can approximate functions with integrable Fourier transforms to an error of $\varepsilon > 0$.
  • Quantum Reservoir Networks: These networks can approximate functions with integrable Fourier transforms to an error of $\varepsilon > 0$ using $O(\varepsilon^{-2})$ random weights and $O(\lceil \log_2(\varepsilon^{-1}) \rceil)$ qubits.
  • Universal Approximation: Both trainable QNNs and quantum reservoir networks are shown to be universal approximators in a mean-square sense for any square-integrable function.
  • Uniform Approximation: The paper also provides $L^\infty$ error bounds on compact sets, demonstrating that QNNs can uniformly approximate continuous functions on these sets.

Limitations and Future Work

  • Constructive vs. Non-Constructive: While the theorems guarantee the existence of approximating QNNs, the explicit construction of optimal parameters might still be challenging in practice, especially when the target function is unknown.
  • Training Stability: The paper acknowledges potential challenges in training QNNs, such as barren plateaus, which can affect gradient-based optimization. While it mentions the quantum parameter-shift rule as an alternative, its computational efficiency is not guaranteed.
  • Hardware Requirements: The theoretical constructions might require specific quantum gates and a significant number of qubits, which could be a limitation for current noisy intermediate-scale quantum (NISQ) devices.
  • Future Work: The authors suggest exploring the application of their results to specific quantum machine learning tasks, investigating the practical performance of these QNNs on real-world data, and extending the theoretical framework to dynamic settings or more complex quantum circuit architectures. They also point out the need for further research into handling potential erratic behaviors of QNNs outside the training data domain.

Summary updated

Abstract

Universal approximation theorems are the foundations of classical neural networks, providing theoretical guarantees that the latter are able to approximate maps of interest. Recent results have shown that this can also be achieved in a quantum setting, whereby classical functions can be approximated by parameterised quantum circuits. We provide here precise error bounds for specific classes of functions and extend these results to the interesting new setup of randomised quantum circuits, mimicking classical reservoir neural networks. Our results show in particular that a quantum neural network with $\mathcal{O}(\varepsilon^{-2})$ weights and $\mathcal{O} (\lceil \log_2(\varepsilon^{-1}) \rceil)$ qubits suffices to achieve accuracy $\varepsilon>0$ when approximating functions with integrable Fourier transform.
BibTeX
@article{gonon2023universal,
  author = {Lukas Gonon and Antoine Jacquier},
  title = {{Universal Approximation Theorem and error bounds for quantum neural networks and quantum reservoirs}},
  journal = {IEEE Trans. Neural Networks Learn. Syst.},
  year = {2023},
  url = {https://openreview.net/forum?id=ET8FN31Rhc},
}
Figure