Towards provably efficient quantum algorithms for large-scale machine-learning models

• URL: http://arxiv.org/abs/2303.03428v5
• Date: Thu, 28 Dec 2023 07:46:22 GMT
• Title: Towards provably efficient quantum algorithms for large-scale machine-learning models
• Authors: Junyu Liu, Minzhao Liu, Jin-Peng Liu, Ziyu Ye, Yunfei Wang, Yuri Alexeev, Jens Eisert, Liang Jiang
• Abstract summary: We show that fault-tolerant quantum computing could possibly provide provably efficient resolutions for generic (stochastic) gradient descent algorithms. We benchmark instances of large machine learning models from 7 million to 103 million parameters.
• Score: 11.440134080370811
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: Large machine learning models are revolutionary technologies of artificial intelligence whose bottlenecks include huge computational expenses, power, and time used both in the pre-training and fine-tuning process. In this work, we show that fault-tolerant quantum computing could possibly provide provably efficient resolutions for generic (stochastic) gradient descent algorithms, scaling as O(T^2 polylog(n)), where n is the size of the models and T is the number of iterations in the training, as long as the models are both sufficiently dissipative and sparse, with small learning rates. Based on earlier efficient quantum algorithms for dissipative differential equations, we find and prove that similar algorithms work for (stochastic) gradient descent, the primary algorithm for machine learning. In practice, we benchmark instances of large machine learning models from 7 million to 103 million parameters. We find that, in the context of sparse training, a quantum enhancement is possible at the early stage of learning after model pruning, motivating a sparse parameter download and re-upload scheme. Our work shows solidly that fault-tolerant quantum algorithms could potentially contribute to most state-of-the-art, large-scale machine-learning problems.

Related papers

• Efficient Learning for Linear Properties of Bounded-Gate Quantum Circuits [63.733312560668274]
  Given a quantum circuit containing d tunable RZ gates and G-d Clifford gates, can a learner perform purely classical inference to efficiently predict its linear properties? We prove that the sample complexity scaling linearly in d is necessary and sufficient to achieve a small prediction error, while the corresponding computational complexity may scale exponentially in d. We devise a kernel-based learning model capable of trading off prediction error and computational complexity, transitioning from exponential to scaling in many practical settings.
  arXiv  Detail & Related papers  (2024-08-22T08:21:28Z)
• Efficient and practical Hamiltonian simulation from time-dependent product formulas [1.2534672170380357]
  We propose an approach for implementing time-evolution of a quantum system using product formulas. Our algorithms generate a decomposition of the evolution operator into a product of simple unitaries that are directly implementable on a quantum computer. Although the theoretical scaling is suboptimal compared with state-of-the-art algorithms, the performance of the algorithms we propose is highly competitive in practice.
  arXiv  Detail & Related papers  (2024-03-13T17:29:05Z)
• Performance and Energy Consumption of Parallel Machine Learning Algorithms [0.0]
  Machine learning models have achieved remarkable success in various real-world applications. Model training in machine learning requires large-scale data sets and multiple iterations before it can work properly. Parallelization of training algorithms is a common strategy to speed up the process of training.
  arXiv  Detail & Related papers  (2023-05-01T13:04:39Z)
• A didactic approach to quantum machine learning with a single qubit [68.8204255655161]
  We focus on the case of learning with a single qubit, using data re-uploading techniques. We implement the different proposed formulations in toy and real-world datasets using the qiskit quantum computing SDK.
  arXiv  Detail & Related papers  (2022-11-23T18:25:32Z)
• A single $T$-gate makes distribution learning hard [56.045224655472865]
  This work provides an extensive characterization of the learnability of the output distributions of local quantum circuits. We show that for a wide variety of the most practically relevant learning algorithms -- including hybrid-quantum classical algorithms -- even the generative modelling problem associated with depth $d=omega(log(n))$ Clifford circuits is hard.
  arXiv  Detail & Related papers  (2022-07-07T08:04:15Z)
• Quantum Semi-Supervised Kernel Learning [4.726777092009554]
  We present a quantum machine learning algorithm for training Semi-Supervised Kernel Support Vector Machines. We show that it maintains the same speedup as the fully-supervised Quantum LS-SVM.
  arXiv  Detail & Related papers  (2022-04-22T13:39:55Z)
• MQBench: Towards Reproducible and Deployable Model Quantization Benchmark [53.12623958951738]
  MQBench is a first attempt to evaluate, analyze, and benchmark the and deployability for model quantization algorithms. We choose multiple platforms for real-world deployments, including CPU, GPU, ASIC, DSP, and evaluate extensive state-of-the-art quantization algorithms. We conduct a comprehensive analysis and find considerable intuitive or counter-intuitive insights.
  arXiv  Detail & Related papers  (2021-11-05T23:38:44Z)
• Quantum Machine Learning: Fad or Future? [0.0]
  We're fast approach the threshold of the maximum possible computational capacity available to us by the means of classical computing devices. This is due to the exponential increase in model sizes which now have parameters in the magnitude of billions and trillions. This paper will look forth to test and verify the aspects in which quantum machine learning can help improve over classical machine learning approaches.
  arXiv  Detail & Related papers  (2021-06-20T15:39:36Z)
• Fixed Depth Hamiltonian Simulation via Cartan Decomposition [59.20417091220753]
  We present a constructive algorithm for generating quantum circuits with time-independent depth. We highlight our algorithm for special classes of models, including Anderson localization in one dimensional transverse field XY model. In addition to providing exact circuits for a broad set of spin and fermionic models, our algorithm provides broad analytic and numerical insight into optimal Hamiltonian simulations.
  arXiv  Detail & Related papers  (2021-04-01T19:06:00Z)
• Ps and Qs: Quantization-aware pruning for efficient low latency neural network inference [56.24109486973292]
  We study the interplay between pruning and quantization during the training of neural networks for ultra low latency applications. We find that quantization-aware pruning yields more computationally efficient models than either pruning or quantization alone for our task.
  arXiv  Detail & Related papers  (2021-02-22T19:00:05Z)
• QUBO Formulations for Training Machine Learning Models [0.0]
  We leverage non-conventional computing paradigms like quantum computing to train machine learning models efficiently. We formulate the training problems of three machine learning models---linear regression, support vector machine (SVM) and equal-sized k-means clustering---as QUBO problems so that they can be trained on adiabatic quantum computers efficiently. We show that the time and space complexities of our formulations are better (in the case of SVM and equal-sized k-means clustering) or equivalent (in case of linear regression) to their classical counterparts.
  arXiv  Detail & Related papers  (2020-08-05T21:16:05Z)

This list is automatically generated from the titles and abstracts of the papers in this site.

This site does not guarantee the quality of this site (including all information) and is not responsible for any consequences.