A significant challenge in the field of quantum machine learning (QML) is to establish applications of quantum computation to accelerate common tasks in machine learning such as those for neural networks. Ridgelet transform has been a fundamental mathematical tool in the theoretical studies of neural networks, but the practical applicability of ridgelet transform to conducting learning tasks was limited since its numerical implementation by conventional classical computation requires an exponential runtime $\exp(O(D))$ as data dimension $D$ increases. To address this problem, we develop a quantum ridgelet transform (QRT), which implements the ridgelet transform of a quantum state within a linear runtime $O(D)$ of quantum computation. As an application, we also show that one can use QRT as a fundamental subroutine for QML to efficiently find a sparse trainable subnetwork of large shallow wide neural networks without conducting large-scale optimization of the original network. This application discovers an efficient way in this regime to demonstrate the lottery ticket hypothesis on finding such a sparse trainable neural network. These results open an avenue of QML for accelerating learning tasks with commonly used classical neural networks.
A significant challenge in the field of quantum machine learning (QML) is to establish applications of quantum computation to accelerate common tasks in machine learning such as those for neural networks. Ridgelet transform has been a fundamental mathematical tool in the theoretical studies of neural networks, but the practical applicability of ridgelet transform to conducting learning tasks was limited since its numerical implementation by conventional classical computation requires an exponential runtime exp(O(D)) as data dimension D increases. To address this problem, we develop a quantum ridgelet transform (QRT), which implements the ridgelet transform of a quantum state within a linear runtime O(D) of quantum computation. As an application, we also show that one can use QRT as a fundamental subroutine for QML to efficiently find a sparse trainable subnetwork of large shallow wide neural networks without conducting large-scale optimization of the original network. This application discovers an efficient way in this regime to demonstrate the lottery ticket hypothesis on finding such a sparse trainable neural network. These results open an avenue of QML for accelerating learning tasks with commonly used classical neural networks.
Quantum machine learning (QML) aims to accelerate machine learning tasks by exploiting quantum computation. Previous work studied a QML algorithm for selecting sparse subnetworks from large shallow neural networks. Instead of directly solving an optimization problem over a large-scale network, this algorithm constructs a sparse subnetwork by sampling hidden nodes from an optimized probability distribution defined using the ridgelet transform. The quantum algorithm performs this sampling in time O(D) in the data dimension D, whereas a naive classical implementation relies on handling exponentially many candidate nodes and hence takes exp[O(D)] time. In this work, we construct and analyze a quantum-inspired fully classical algorithm for the same sampling task. We show that our algorithm runs in time O(poly(D)), thereby removing the exponential dependence on D from the previous classical approach. Numerical simulations show that the proposed sampler achieves empirical risk comparable to exact sampling from the optimized distribution and substantially lower than sampling from the non-optimized uniform distribution, while also exhibiting exponentially improved runtime scaling compared with the conventional classical implementation. These successful dequantization results show that sparse subnetwork selection via optimized sampling can be achieved classically with polynomial data-dimension scaling on conventional computers without quantum hardware, providing an alternative to the existing quantum algorithm.
Quantum Neural Networks (QNNs) possess high expressivity via rich unitary transformations, offering abundant representational capacity while maintaining a parameter-effective architecture. In classical deep learning, the high expressivity of deep neural networks (DNNs) motivates the Strong Lottery Ticket Hypothesis (SLTH), which suggests that a randomly initialized DNN contains sparse subnetworks that achieve high performance immediately or serve as a warm start. On the quantum side, a key question is: Does a strong lottery ticket exist in QNNs? Our answer is, Quantum-Strong Lottery Ticket Hypothesis (Q-SLTH), i.e., the first theoretical analysis for the existence of high-performing subnetworks in random scratch of QNNs. We validate our theory by proposing a quantum edge-popup algorithm to find strong subnetworks and empirically identifying winning tickets in randomly initialized QNNs on the MNIST and Fashion-MNIST benchmarks. For practice, Q-SLTH suggests a way to compress QNNs, allowing them to use fewer gates and thereby mitigating quantum-noise-induced degradation that is amplified across multiple layers of quantum gates.
Quantum computing is an emerging field in computer science that has seen considerable progress in recent years, especially in machine learning. By harnessing the principles of quantum physics, it can surpass the limitations of classical algorithms. However, variational quantum circuits (VQCs), which rely on adjustable parameters, often face the barren plateau phenomenon, hindering optimization. The Lottery Ticket Hypothesis (LTH) is a recent concept in classical machine learning that has led to notable improvements in parameter efficiency for neural networks. It states that within a large network, a smaller, more efficient subnetwork, or ''winning ticket,'' can achieve comparable performance, potentially circumventing plateau challenges. In this work, we investigate whether this idea can apply to VQCs. We show that the weak LTH holds for VQCs, revealing winning tickets that retain just 26.0\% of the original parameters. For the strong LTH, where a pruning mask is learned without any training, we discovered a winning ticket in a binary VQC, achieving 100\% accuracy with only 45\% of the weights. These findings indicate that LTH may mitigate barren plateaus by reducing parameter counts while preserving performance, thus enhancing the efficiency of VQCs in quantum machine learning tasks.
Large-scale machine learning (ML) models, particularly deep neural networks, often present significant challenges for traditional optimization algorithms. These algorithms, rooted in classical mechanics, frequently encounter issues such as getting trapped in local optima, high computational cost, and difficulty in handling complex, non-convex landscapes. This paper investigates the application of quantum-inspired optimization techniques to address these challenges. We explore how concepts derived from quantum phenomena – such as quantum annealing and quantum walks – can be adapted to efficiently navigate and optimize large-scale ML models. The core idea is to leverage the probabilistic and superposition properties inherent in quantum mechanics to escape local optima and accelerate the convergence process. We present a framework for designing and implementing quantum-inspired optimization strategies, focusing on the theoretical foundations and potential benefits. The proposed approach aims to provide a novel and effective solution for optimizing complex ML models, ultimately improving model performance and reducing training time. This work contributes to the growing field of quantum machine learning and offers a promising avenue for tackling the optimization problems inherent in large-scale ML.
Machine learning holds fundamental computational significance due to the increasing demand for efficient solutions to complex tasks in data analysis, pattern recognition, and optimization, which are essential for addressing the multifaceted challenges of modern society. As the volume of data proliferates at an unprecedented rate, the need for more powerful machine learning strategies becomes increasingly evident. Quantum neural networks (QNNs) represent an emerging and transformative research field that seeks to harness the unique principles of quantum mechanics to enhance the capabilities of machine learning algorithms. This survey examines various QNN approaches, including fully connected QNNs, quantum convolutional neural networks, equivariant QNNs, quantum Hopfield networks, quantum Boltzmann machines, quantum reservoir computing, and composite networks for quantum reinforcement learning, quantum generative learning, and quantum transfer learning. We summarize the relevant investigations on their performance, including learning accuracy, training time, and resource requirements, etc. Each QNN type has unique strengths and weaknesses, offering diverse solutions for different applications.
Given the success of deep learning in classical machine learning, quantum algorithms for traditional neural network architectures may provide one of the most promising settings for quantum machine learning. Considering a fully-connected feedforward neural network, we show that conditions amenable to classical trainability via gradient descent coincide with those necessary for efficiently solving quantum linear systems. We propose a quantum algorithm to approximately train a wide and deep neural network up to O(1/n) error for a training set of size n by performing sparse matrix inversion in O(logn) time. To achieve an end-to-end exponential speedup over gradient descent, the data distribution must permit efficient state preparation and readout. We numerically demonstrate that the MNIST image dataset satisfies such conditions; moreover, the quantum algorithm matches the accuracy of the fully-connected network. Beyond the proven architecture, we provide empirical evidence for O(logn) training of a convolutional neural network with pooling.