COMPLEXITY ANALYSIS OF ALGORITHMS FOR QUANTUM NEURAL NETWORKS USING TENSOR NETWORKS

Ezhitskaya Daria Dmitrievna

This paper provides a comprehensive analysis of the computational complexity of algorithms underlying quantum neural networks (QNNs) using tensor network (TN) frameworks. QNNs represent a promising hybrid approach that combines the principles of quantum computing and machine learning, but their theoretical underpinnings and understanding of their superiority over classical analogs remain underdeveloped. We demonstrate that tensor networks, as a powerful tool for compactly representing multi-qubit quantum states, provide a natural and effective formalism for analyzing the expressiveness and training complexity of QNNs. The paper formalizes the relationship between QNN architectures and specific TN types (such as matrix product states (MPS) and tree tensor networks (TTNs). Based on this, a detailed analysis of the capacity characteristics and computational complexity of forward and backward propagation operations is conducted for various QNN topologies. It has been shown that the key parameter determining complexity is the so-called "connectivity" of a quantum circuit, which directly correlates with the maximum connectivity of the corresponding deep neural network. It has been theoretically and numerically substantiated that quantum neural networks corresponding to finite-connectivity networks (e.g., MPS) can be efficiently simulated on classical computers, narrowing the potential range of problems where quantum supremacy can be expected. At the same time, a class of problems related to the modeling of highly entangled quantum systems or solving certain optimization problems has been identified, where quantum neural networks with moderate connectivity demonstrate a theoretical advantage over classical deep neural networks. The results of this study allow us to formulate criteria for designing effective quantum neural networks and identify promising areas for achieving practical quantum supremacy in machine learning.

Keywords:quantum neural networks, tensor networks, matrix product states, computational complexity, quantum machine learning, expressiveness, connectivity, quantum supremacy