Quantum advantage for learning shallow neural networks with natural data distributions

• URL: http://arxiv.org/abs/2503.20879v1
• Date: Wed, 26 Mar 2025 18:00:17 GMT
• Title: Quantum advantage for learning shallow neural networks with natural data distributions
• Authors: Laura Lewis, Dar Gilboa, Jarrod R. McClean,
• Abstract summary: We study an efficient quantum algorithm for learning periodic neurons in the QSQ model over a broad range of non-uniform distributions.<n>To our knowledge, our work is the first result in quantum learning theory for classical functions that explicitly considers real-valued functions.
• Score: 4.363673971859799
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: The application of quantum computers to machine learning tasks is an exciting potential direction to explore in search of quantum advantage. In the absence of large quantum computers to empirically evaluate performance, theoretical frameworks such as the quantum probably approximately correct (PAC) and quantum statistical query (QSQ) models have been proposed to study quantum algorithms for learning classical functions. Despite numerous works investigating quantum advantage in these models, we nevertheless only understand it at two extremes: either exponential quantum advantages for uniform input distributions or no advantage for potentially adversarial distributions. In this work, we study the gap between these two regimes by designing an efficient quantum algorithm for learning periodic neurons in the QSQ model over a broad range of non-uniform distributions, which includes Gaussian, generalized Gaussian, and logistic distributions. To our knowledge, our work is also the first result in quantum learning theory for classical functions that explicitly considers real-valued functions. Recent advances in classical learning theory prove that learning periodic neurons is hard for any classical gradient-based algorithm, giving us an exponential quantum advantage over such algorithms, which are the standard workhorses of machine learning. Moreover, in some parameter regimes, the problem remains hard for classical statistical query algorithms and even general classical algorithms learning under small amounts of noise.

Related papers

• Application of quantum machine learning using quantum kernel algorithms on multiclass neuron M type classification [0.0]
  This study is the first to propose the utilization of quantum systems to classify neuron morphologies.<n>We examined the influence of feature engineering on classification accuracy and found that quantum kernel methods achieved similar performance to classical methods.
  arXiv  Detail & Related papers  (2025-02-10T09:23:32Z)
• An Exponential Separation Between Quantum and Quantum-Inspired Classical Algorithms for Linear Systems [14.955338558971787]
  We present the first provable exponential separation between quantum and quantum-inspired classical algorithms for the basic problem of solving a linear system. From the current state-of-affairs, it is unclear whether we can hope for exponential quantum speedups for any natural machine learning task.
  arXiv  Detail & Related papers  (2024-11-04T13:49:26Z)
• 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)
• Quantum Machine Learning: Quantum Kernel Methods [0.0]
  Kernel methods are a powerful and popular technique in classical Machine Learning. The use of a quantum feature space that can only be calculated efficiently on a quantum computer potentially allows for deriving a quantum advantage. A data dependent projected quantum kernel was shown to provide significant advantage over classical kernels.
  arXiv  Detail & Related papers  (2024-05-02T23:45:29Z)
• Quantum data learning for quantum simulations in high-energy physics [55.41644538483948]
  We explore the applicability of quantum-data learning to practical problems in high-energy physics. We make use of ansatz based on quantum convolutional neural networks and numerically show that it is capable of recognizing quantum phases of ground states. The observation of non-trivial learning properties demonstrated in these benchmarks will motivate further exploration of the quantum-data learning architecture in high-energy physics.
  arXiv  Detail & Related papers  (2023-06-29T18:00:01Z)
• Classical Verification of Quantum Learning [42.362388367152256]
  We develop a framework for classical verification of quantum learning. We propose a new quantum data access model that we call "mixture-of-superpositions" quantum examples. Our results demonstrate that the potential power of quantum data for learning tasks, while not unlimited, can be utilized by classical agents.
  arXiv  Detail & Related papers  (2023-06-08T00:31:27Z)
• Expressive Quantum Supervised Machine Learning using Kerr-nonlinear Parametric Oscillators [0.0]
  Quantum machine learning with variational quantum algorithms (VQA) has been actively investigated as a practical algorithm in the noisy intermediate-scale quantum (NISQ) era. Recent researches reveal that the data reuploading, which repeatedly encode classical data into quantum circuit, is necessary for obtaining the expressive quantum machine learning model. We propose quantum machine learning with Kerrnon Parametric Hilberts (KPOs) as another promising quantum computing device.
  arXiv  Detail & Related papers  (2023-05-01T07:01:45Z)
• Quantum Machine Learning: from physics to software engineering [58.720142291102135]
  We show how classical machine learning approach can help improve the facilities of quantum computers. We discuss how quantum algorithms and quantum computers may be useful for solving classical machine learning tasks.
  arXiv  Detail & Related papers  (2023-01-04T23:37:45Z)
• Recent Advances for Quantum Neural Networks in Generative Learning [98.88205308106778]
  Quantum generative learning models (QGLMs) may surpass their classical counterparts. We review the current progress of QGLMs from the perspective of machine learning. We discuss the potential applications of QGLMs in both conventional machine learning tasks and quantum physics.
  arXiv  Detail & Related papers  (2022-06-07T07:32:57Z)
• Theory of Quantum Generative Learning Models with Maximum Mean Discrepancy [67.02951777522547]
  We study learnability of quantum circuit Born machines (QCBMs) and quantum generative adversarial networks (QGANs) We first analyze the generalization ability of QCBMs and identify their superiorities when the quantum devices can directly access the target distribution. Next, we prove how the generalization error bound of QGANs depends on the employed Ansatz, the number of qudits, and input states.
  arXiv  Detail & Related papers  (2022-05-10T08:05:59Z)
• Quantum algorithms for quantum dynamics: A performance study on the spin-boson model [68.8204255655161]
  Quantum algorithms for quantum dynamics simulations are traditionally based on implementing a Trotter-approximation of the time-evolution operator. variational quantum algorithms have become an indispensable alternative, enabling small-scale simulations on present-day hardware. We show that, despite providing a clear reduction of quantum gate cost, the variational method in its current implementation is unlikely to lead to a quantum advantage.
  arXiv  Detail & Related papers  (2021-08-09T18:00:05Z)
• Towards quantum advantage via topological data analysis [0.0]
  We study the quantum-algorithmic methods behind the algorithm for topological data analysis of Lloyd, Garnerone and Zanardi. We provide a number of new quantum algorithms for problems such as rank estimation and complex network analysis.
  arXiv  Detail & Related papers  (2020-05-06T06:31:24Z)

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.