Gradient descent methods have long been the de facto standard for training deep neural networks. Millions of training samples are fed into models with billions of parameters, which are slowly updated over hundreds of epochs. Recently, it's been shown that large, randomly initialized neural networks contain subnetworks that perform as well as fully trained models. This insight offers a promising avenue for training future neural networks by simply pruning weights from large, random models. However, this problem is combinatorically hard and classical algorithms are not efficient at finding the best subnetwork. In this paper, we explore how quantum algorithms could be formulated and applied to this neuron selection problem. We introduce several methods for local quantum neuron selection that reduce the entanglement complexity that large scale neuron selection would require, making this problem more tractable for current quantum hardware.Gradient descent methods have long been the de facto standard for training deep neural networks. Millions of training samples are fed into models with billions of parameters, which are slowly updated over hundreds of epochs. Recently, it's been shown that large, randomly initialized neural networks contain subnetworks that perform as well as fully trained models. This insight offers a promising avenue for training future neural networks by simply pruning weights from large, random models. However, this problem is combinatorically hard and classical algorithms are not efficient at finding the best subnetwork. In this paper, we explore how quantum algorithms could be formulated and applied to this neuron selection problem. We introduce several methods for local quantum neuron selection that reduce the entanglement complexity that large scale neuron selection would require, making this problem more tractable for current quantum hardware.

Genetic and Evolutionary Computation Conference Companion (GECCO Companion)Jul 9, 20221 citation

Quantum algorithms for feedforward neural networks

Jonathan Allcock, Chang‐Yu Hsieh, Iordanis Kerenidis +1 more

Quantum machine learning has the potential for broad industrial applications, and the development of quantum algorithms for improving the performance of neural networks is of particular interest given the central role they play in machine learning today. In this paper we present quantum algorithms for training and evaluating feedforward neural networks based on the canonical classical feedforward and backpropagation algorithms. Our algorithms rely on an efficient quantum subroutine for approximating the inner products between vectors in a robust way, and on implicitly storing large intermediate values in quantum random access memory for fast retrieval at later stages. The running times of our algorithms can be quadratically faster in the size of the network than their standard classical counterparts since they depend linearly on the number of neurons in the network, as opposed to the number of connections between neurons as in the classical case. This makes our algorithms suited for large-scale, highly-connected networks where the number of edges in the network dominates the classical algorithmic running time. Furthermore, networks trained by our quantum algorithm may have an intrinsic resilience to overfitting, as the algorithm naturally mimics the effects of classical techniques such as drop-out used to regularize networks. Our algorithms can also be used as the basis for new quantum-inspired classical algorithms which have the same dependence on the network dimensions as their quantum counterparts, but with quadratic overhead in other parameters that makes them relatively impractical.Quantum machine learning has the potential for broad industrial applications, and the development of quantum algorithms for improving the performance of neural networks is of particular interest given the central role they play in machine learning today. In this paper we present quantum algorithms for training and evaluating feedforward neural networks based on the canonical classical feedforward and backpropagation algorithms. Our algorithms rely on an efficient quantum subroutine for approximating the inner products between vectors in a robust way, and on implicitly storing large intermediate values in quantum random access memory for fast retrieval at later stages. The running times of our algorithms can be quadratically faster in the size of the network than their standard classical counterparts since they depend linearly on the number of neurons in the network, as opposed to the number of connections between neurons as in the classical case. This makes our algorithms suited for large-scale, highly-connected networks where the number of edges in the network dominates the classical algorithmic running time. Furthermore, networks trained by our quantum algorithm may have an intrinsic resilience to overfitting, as the algorithm naturally mimics the effects of classical techniques such as drop-out used to regularize networks. Our algorithms can also be used as the basis for new quantum-inspired classical algorithms which have the same dependence on the network dimensions as their quantum counterparts, but with quadratic overhead in other parameters that makes them relatively impractical.

Dec 15, 20190 citations

Quantum-Inspired Optimization of Neural Network Training Dynamics

Jincheng Zhang

Training deep neural networks remains a computationally intensive and often challenging process. Traditional optimization methods, such as stochastic gradient descent (SGD) and its variants, frequently struggle to escape local minima and converge to optimal solutions, leading to suboptimal network performance. This paper proposes a novel approach to neural network training that leverages principles inspired by quantum mechanics. Specifically, we investigate the application of quantum-inspired optimization techniques, including simulated annealing and quantum walks, to dynamically adjust the training process. The core idea is to mimic the probabilistic exploration inherent in quantum systems to effectively navigate the complex loss landscape of neural networks. We formulate the training process as a quantum-inspired optimization problem, where the network's weights are treated as quantum bits (Qubits) and the optimization algorithm seeks to find the lowest energy state, analogous to finding the minimum loss. The proposed method demonstrates the potential for accelerating convergence and improving the overall accuracy of neural networks compared to conventional optimization strategies. Our analysis focuses on the key aspects of the approach, including the mathematical formulation of the quantum-inspired optimization problem and the selection of appropriate parameters to govern the exploration and exploitation phases. We present a theoretical framework for understanding the dynamics of this approach and discuss potential avenues for further research, including hybrid quantum-classical algorithms and the integration of quantum computing hardware.Training deep neural networks remains a computationally intensive and often challenging process. Traditional optimization methods, such as stochastic gradient descent (SGD) and its variants, frequently struggle to escape local minima and converge to optimal solutions, leading to suboptimal network performance. This paper proposes a novel approach to neural network training that leverages principles inspired by quantum mechanics. Specifically, we investigate the application of quantum-inspired optimization techniques, including simulated annealing and quantum walks, to dynamically adjust the training process. The core idea is to mimic the probabilistic exploration inherent in quantum systems to effectively navigate the complex loss landscape of neural networks. We formulate the training process as a quantum-inspired optimization problem, where the network's weights are treated as quantum bits (Qubits) and the optimization algorithm seeks to find the lowest energy state, analogous to finding the minimum loss. The proposed method demonstrates the potential for accelerating convergence and improving the overall accuracy of neural networks compared to conventional optimization strategies. Our analysis focuses on the key aspects of the approach, including the mathematical formulation of the quantum-inspired optimization problem and the selection of appropriate parameters to govern the exploration and exploitation phases. We present a theoretical framework for understanding the dynamics of this approach and discuss potential avenues for further research, including hybrid quantum-classical algorithms and the integration of quantum computing hardware.

Sep 5, 20260 citations

A quantum algorithm for training wide and deep classical neural networks

Alexander Zlokapa, Hartmut Neven, Seth Lloyd

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(\log n)$ 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(\log n)$ training of a convolutional neural network with pooling.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(\log n)$ 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(\log n)$ training of a convolutional neural network with pooling.

arXiv:2107.09200Jul 19, 202110 citations

Title: Quantum-Enhanced Stochastic Gradient Descent for Deep Learning

Jincheng Zhang

Quantum-enhanced stochastic gradient descent (SGD) presents a promising avenue for accelerating deep learning training and enhancing generalization, leveraging quantum phenomena such as superposition and entanglement to potentially improve convergence rates and model robustness. This paper explores the feasibility of utilizing quantum states to represent and update neural network weights, proposing a novel algorithm that aims to address the limitations of current SGD approaches in handling large datasets and intricate models. We investigate the potential benefits of quantum acceleration in deep learning, focusing on the enhancement of learning speed and improved model performance. The paper details the core mechanism, outlines the experimental setup, and discusses the challenges and future directions of this research.Quantum-enhanced stochastic gradient descent (SGD) presents a promising avenue for accelerating deep learning training and enhancing generalization, leveraging quantum phenomena such as superposition and entanglement to potentially improve convergence rates and model robustness. This paper explores the feasibility of utilizing quantum states to represent and update neural network weights, proposing a novel algorithm that aims to address the limitations of current SGD approaches in handling large datasets and intricate models. We investigate the potential benefits of quantum acceleration in deep learning, focusing on the enhancement of learning speed and improved model performance. The paper details the core mechanism, outlines the experimental setup, and discusses the challenges and future directions of this research.

Sep 7, 20260 citations

Quantum-Inspired Optimization of Large-Scale Machine Learning Algorithms

Jincheng Zhang

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.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.

Sep 7, 20260 citations

O(1/n)

error for a training set of size

n

by performing sparse matrix inversion in

O(\log n)

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(\log n)

training of a convolutional neural network with pooling.