One of the most important properties of classical neural networks is the clustering of local minima of the network near the global minimum, enabling efficient training. This has been observed not only numerically, but also has begun to be analytically understood through the lens of random matrix theory. Inspired by these results in classical machine learning, we show that a certain randomized class of variational quantum algorithms can be mapped to Wishart random fields on the hypertorus. Then, using the statistical properties of such random processes, we analytically find the expected distribution of critical points. Unlike the case for deep neural networks, we show the existence of a transition in the quality of local minima at a number of parameters exponentially large in the problem size. Below this transition, all local minima are concentrated far from the global minimum; above, all local minima are concentrated near the global minimum. This is consistent with previously observed numerical results on the landscape behavior of Hamiltonian agnostic variational quantum algorithms. We give a heuristic explanation as to why ansatzes that depend on the problem Hamiltonian might not suffer from these scaling issues. We also verify that our analytic results hold experimentally even at modest system sizes.
One of the most important properties of classical neural networks is the clustering of local minima of the network near the global minimum, enabling efficient training. This has been observed not only numerically, but also has begun to be analytically understood through the lens of random matrix theory. Inspired by these results in classical machine learning, we show that a certain randomized class of variational quantum algorithms can be mapped to Wishart random fields on the hypertorus. Then, using the statistical properties of such random processes, we analytically find the expected distribution of critical points. Unlike the case for deep neural networks, we show the existence of a transition in the quality of local minima at a number of parameters exponentially large in the problem size. Below this transition, all local minima are concentrated far from the global minimum; above, all local minima are concentrated near the global minimum. This is consistent with previously observed numerical results on the landscape behavior of Hamiltonian agnostic variational quantum algorithms. We give a heuristic explanation as to why ansatzes that depend on the problem Hamiltonian might not suffer from these scaling issues. We also verify that our analytic results hold experimentally even at modest system sizes.
One of the most important properties of neural networks is the clustering of local minima of the loss function near the global minimum, enabling efficient training. Though generative models implemented on quantum computers are known to be more expressive than their traditional counterparts, it has empirically been observed that these models experience a transition in the quality of their local minima. Namely, below some critical number of parameters, all local minima are far from the global minimum in function value; above this critical parameter count, all local minima are good approximators of the global minimum. Furthermore, for a certain class of quantum generative models, this transition has empirically been observed to occur at parameter counts exponentially large in the problem size, meaning practical training of these models is out of reach. Here, we give the first proof of this transition in trainability, specializing to this latter class of quantum generative model. We use techniques inspired by those used to study the loss landscapes of classical neural networks. We also verify that our analytic results hold experimentally even at modest model sizes.
The training efficiency of Variational Quantum Algorithms (VQAs) is dictated by the geometry of their loss landscapes, which can be formally analysed by mapping these functions to random fields on manifolds. Instead of VQAs, we can then directly study the corresponding random fields, in our case, the Wishart Hypertoroidal Random Fields (WHRFs). We are mostly interested in the distribution of critical points (especially local minima) of WHRFs. For this purpose, the Kac-Rice formula is presented, reformulated, and simulated. The findings identify a phase transition in the distribution of local minima. Beyond a specific threshold, local minima concentrate near the global minimum in function value, meaning that even local minima are good approximators of the global one. The threshold is governed by the ratio between the problem Hamiltonian degrees of freedom and by the number of independent parameters in the VQA. Since the degrees of freedom parameter scales exponentially, we propose symmetry reduction operations to lower the degrees of freedom. This mathematically reduces the dimension, scaling down the required parameter threshold and enabling to solve bigger problems.
One of the most important properties of classical neural networks is how surprisingly trainable they are, though their training algorithms typically rely on optimizing complicated, nonconvex loss functions. Previous results have shown that unlike the case in classical neural networks, variational quantum models are often not trainable. The most studied phenomenon is the onset of barren plateaus in the training landscape of these quantum models, typically when the models are very deep. This focus on barren plateaus has made the phenomenon almost synonymous with the trainability of quantum models. Here, we show that barren plateaus are only a part of the story. We prove that a wide class of variational quantum models-which are shallow, and exhibit no barren plateaus-have only a superpolynomially small fraction of local minima within any constant energy from the global minimum, rendering these models untrainable if no good initial guess of the optimal parameters is known. We also study the trainability of variational quantum algorithms from a statistical query framework, and show that noisy optimization of a wide variety of quantum models is impossible with a sub-exponential number of queries. Finally, we numerically confirm our results on a variety of problem instances. Though we exclude a wide variety of quantum algorithms here, we give reason for optimism for certain classes of variational algorithms and discuss potential ways forward in showing the practical utility of such algorithms.
Quantum circuits suffer from severe trainability issues: even shallow circuits are swamped with poor local minima. Yet matrix product states (MPS), which can be prepared by sequential circuits, are remarkably trainable in practice -- as demonstrated by decades of successful density matrix renormalization group calculations. In this work, we resolve this apparent paradox by proving that the energy landscapes of MPS are free from poor local minima, under the same setting where brickwork circuits are not. The key insight is that the gauge freedom of MPS creates an effective local overparametrization that causes local minima to concentrate near the global minimum, analogous to overparametrized classical neural networks. We rigorously prove that the local minimum distribution is invariant under moves of the orthogonality center of MPS representations. Numerical experiments further confirm that the optimization of sequential circuits converges to near-optimal solutions even for random Hamiltonians, in stark contrast to brickwork circuits. Our findings establish a theoretical understanding of the trainability of MPS, providing a valuable guide for designing variational quantum circuits and algorithms with better trainability in the future.
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.
Classical neural networks with random initialization famously behave as Gaussian processes in the limit of many neurons, which allows one to completely characterize their training and generalization behavior. No such general understanding exists for quantum neural networks (QNNs), which -- outside of certain special cases -- are known to not behave as Gaussian processes when randomly initialized. We here prove that QNNs and their first two derivatives instead generally form what we call "Wishart processes," where certain algebraic properties of the network determine the hyperparameters of the process. This Wishart process description allows us to, for the first time: give necessary and sufficient conditions for a QNN architecture to have a Gaussian process limit; calculate the full gradient distribution, generalizing previously known barren plateau results; and calculate the local minima distribution of algebraically constrained QNNs. Our unified framework suggests a certain simple operational definition for the "trainability" of a given QNN model using a newly introduced, experimentally accessible quantity we call the "degrees of freedom" of the network architecture.