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 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.
We study the classical compilation of quantum circuits for the preparation of matrix product states (MPS), which are quantum states of low entanglement with an efficient classical description. Our algorithm represents a near-term alternative to previous sequential approaches by reverse application of a disentangler, which can be found by minimizing bipartite entanglement measures after the application of a layer of parametrized disentangling gates. Since a successful disentangler is expected to decrease the bond dimension on average, such a layer-by-layer optimization remains classically efficient even for deep circuits. Additionally, as the Schmidt coefficients of all bonds are locally accessible through the canonical Γ − Λ form of an MPS, the optimization algorithm can be heavily parallelized. We discuss guarantees and limitations to trainability and show numerical results for ground states of one-dimensional, local Hamiltonians as well as artificially spread out entanglement among multiple qubits using error-correcting codes.
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 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.
Variational Quantum Algorithms have emerged as a leading paradigm for near-term quantum computation. In such algorithms, a parameterized quantum circuit is controlled via a classical optimization method that seeks to minimize a problem-dependent cost function. Although such algorithms are powerful in principle, the non-convexity of the associated cost landscapes and the prevalence of local minima means that local optimization methods such as gradient descent typically fail to reach good solutions. In this work we suggest a method to improve gradient-based approaches to variational quantum circuit optimization, which involves coupling the output of the quantum circuit to a classical neural network. The effect of this neural network is to peturb the cost landscape as a function of its parameters, so that local minima can be escaped or avoided via a modification to the cost landscape itself. We present two algorithms within this framework and numerically benchmark them on small instances of the Max-Cut optimization problem. We show that the method is able to reach deeper minima and lower cost values than standard gradient descent based approaches. Moreover, our algorithms require essentially the same number of quantum circuit evaluations per optimization step as the standard approach since, unlike the gradient with respect to the circuit, the neural network updates can be estimated in parallel via the backpropagation method. More generally, our approach suggests that relaxing the cost landscape is a fruitful path to improving near-term quantum computing algorithms.
Modeling probability distributions via the wave function of a quantum state is central to quantum-inspired generative modeling and quantum state tomography (QST). We investigate a common failure mode in training randomly initialized matrix product states (MPS) using gradient descent. The results show that the trained MPS models do not accurately predict the strong interactions between boundary sites in periodic spin chain models. In the case of the Born machine algorithm, we further identify a causality trap, where the trained MPS models resemble causal models that ignore the non-local correlations in the true distribution. We propose two complementary strategies to overcome the training failure -- one through optimization and one through initialization. First, we develop a natural gradient descent (NGD) method, which approximately simulates the gradient flow on tensor manifolds and significantly enhances training efficiency. Numerical experiments show that NGD avoids local minima in both Born machines and in general MPS tomography. Remarkably, we show that NGD with line search can converge to the global minimum in only a few iterations. Second, for the BM algorithm, we introduce a warm-start initialization based on the TTNS-Sketch algorithm. We show that gradient descent under a warm initialization does not encounter the causality trap and admits rapid convergence to the ground truth.
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.