@article {3246, title = {Analyzing Convergence in Quantum Neural Networks: Deviations from Neural Tangent Kernels}, year = {2023}, month = {3/26/2023}, abstract = {

A quantum neural network (QNN) is a parameterized mapping efficiently implementable on near-term Noisy Intermediate-Scale Quantum (NISQ) computers. It can be used for supervised learning when combined with classical gradient-based optimizers. Despite the existing empirical and theoretical investigations, the convergence of QNN training is not fully understood. Inspired by the success of the neural tangent kernels (NTKs) in probing into the dynamics of classical neural networks, a recent line of works proposes to study over-parameterized QNNs by examining a quantum version of tangent kernels. In this work, we study the dynamics of QNNs and show that contrary to popular belief it is qualitatively different from that of any kernel regression: due to the unitarity of quantum operations, there is a non-negligible deviation from the tangent kernel regression derived at the random initialization. As a result of the deviation, we prove the at-most sublinear convergence for QNNs with Pauli measurements, which is beyond the explanatory power of any kernel regression dynamics. We then present the actual dynamics of QNNs in the limit of over-parameterization. The new dynamics capture the change of convergence rate during training and implies that the range of measurements is crucial to the fast QNN convergence.

}, url = {https://arxiv.org/abs/2303.14844}, author = {Xuchen You and Shouvanik Chakrabarti and Boyang Chen and Xiaodi Wu} } @article {3072, title = {A Convergence Theory for Over-parameterized Variational Quantum Eigensolvers}, year = {2022}, month = {5/25/2022}, abstract = {

The Variational Quantum Eigensolver (VQE) is a promising candidate for quantum applications on near-term Noisy Intermediate-Scale Quantum (NISQ) computers. Despite a lot of empirical studies and recent progress in theoretical understanding of VQE\&$\#$39;s optimization landscape, the convergence for optimizing VQE is far less understood. We provide the first rigorous analysis of the convergence of VQEs in the over-parameterization regime. By connecting the training dynamics with the Riemannian Gradient Flow on the unit-sphere, we establish a threshold on the sufficient number of parameters for efficient convergence, which depends polynomially on the system dimension and the spectral ratio, a property of the problem Hamiltonian, and could be resilient to gradient noise to some extent. We further illustrate that this overparameterization threshold could be vastly reduced for specific VQE instances by establishing an ansatz-dependent threshold paralleling our main result. We showcase that our ansatz-dependent threshold could serve as a proxy of the trainability of different VQE ansatzes without performing empirical experiments, which hence leads to a principled way of evaluating ansatz design. Finally, we conclude with a comprehensive empirical study that supports our theoretical findings

}, url = {https://arxiv.org/abs/2205.12481}, author = {Xuchen You and Shouvanik Chakrabarti and Xiaodi Wu} } @article {2860, title = {Exponentially Many Local Minima in Quantum Neural Networks}, journal = {Proceedings of the 38th International Conference on Machine Learning, PMLR}, volume = {139}, year = {2021}, month = {10/5/2021}, pages = {12144-12155}, abstract = {

Quantum Neural Networks (QNNs), or the so-called variational quantum circuits, are important quantum applications both because of their similar promises as classical neural networks and because of the feasibility of their implementation on near-term intermediate-size noisy quantum machines (NISQ). However, the training task of QNNs is challenging and much less understood. We conduct a quantitative investigation on the landscape of loss functions of QNNs and identify a class of simple yet extremely hard QNN instances for training. Specifically, we show for typical under-parameterized QNNs, there exists a dataset that induces a loss function with the number of spurious local minima depending exponentially on the number of parameters. Moreover, we show the optimality of our construction by providing an almost matching upper bound on such dependence. While local minima in classical neural networks are due to non-linear activations, in quantum neural networks local minima appear as a result of the quantum interference phenomenon. Finally, we empirically confirm that our constructions can indeed be hard instances in practice with typical gradient-based optimizers, which demonstrates the practical value of our findings.\ 

}, url = {https://arxiv.org/pdf/2110.02479.pdf}, author = {Xuchen You and Xiaodi Wu} } @article {2633, title = {Quantum exploration algorithms for multi-armed bandits}, journal = {Proceedings of the 35th Conference on Artificial Intelligence (AAAI 2021)}, volume = {35}, year = {2021}, month = {2021}, pages = {10102-10110}, abstract = {

\ Identifying the best arm of a multi-armed bandit is a central problem in bandit optimization. We study a quantum computational version of this problem with coherent oracle access to states encoding the reward probabilities of each arm as quantum amplitudes. Specifically, we show that we can find the best arm with fixed confidence using O~(\∑ni=2Δ\−2i\−\−\−\−\−\−\−\−\√) quantum queries, where Δi represents the difference between the mean reward of the best arm and the ith-best arm. This algorithm, based on variable-time amplitude amplification and estimation, gives a quadratic speedup compared to the best possible classical result. We also prove a matching quantum lower bound (up to poly-logarithmic factors).

}, url = {https://ojs.aaai.org/index.php/AAAI/article/view/17212}, author = {Daochen Wang and Xuchen You and Tongyang Li and Andrew M. Childs} }