Winning Lottery Tickets in Neural Networks via a Quantum-Inspired Classical Algorithm

• URL: http://arxiv.org/abs/2605.13979v1
• Date: Wed, 13 May 2026 18:00:56 GMT
• Title: Winning Lottery Tickets in Neural Networks via a Quantum-Inspired Classical Algorithm
• Abstract summary: We construct and analyze a quantum-inspired fully classical algorithm for the same sampling task.<n>We show that our algorithm runs in time $O(operatornamepoly(D))$, thereby removing the exponential dependence on $D$ from the previous classical approach.
• Score: 4.633161758939183
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: 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(\operatorname{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.

Related papers

• Quantum Speedup for Sampling Random Spanning Trees [2.356162747014486]
  We present a quantum algorithm for sampling random spanning trees from a weighted graph in $widetildeO(sqrtmn)$ time.<n>Our algorithm has sublinear runtime for dense graphs and achieves a quantum speedup over the best-known classical algorithm.
  arXiv  Detail & Related papers  (2025-04-22T05:45:04Z)
• Classical Combinatorial Optimization Scaling for Random Ising Models on 2D Heavy-Hex Graphs [0.8192907805418583]
  Ising models on heavy-hex graphs are examined for their classical computational hardness via empirical time scaling.<n>Because of the sparsity of these Ising models, the classical algorithms are able to find optimal solutions efficiently even for large instances.
  arXiv  Detail & Related papers  (2024-12-20T05:09:30Z)
• Sum-of-Squares inspired Quantum Metaheuristic for Polynomial Optimization with the Hadamard Test and Approximate Amplitude Constraints [76.53316706600717]
  Recently proposed quantum algorithm arXiv:2206.14999 is based on semidefinite programming (SDP) We generalize the SDP-inspired quantum algorithm to sum-of-squares. Our results show that our algorithm is suitable for large problems and approximate the best known classicals.
  arXiv  Detail & Related papers  (2024-08-14T19:04:13Z)
• Gaussian Boson Sampling to Accelerate NP-Complete Vertex-Minor Graph Classification [0.9935277311162707]
  We propose a hybrid quantum-classical algorithm for the NP-complete problem of determining if two graphs are minor of one another. We find a graph embedding that allows trading between the one-shot classification accuracy and the amount of input squeezing. We introduce a new classical algorithm based on graph spectra, which we show outperforms various well-known graph-similarity algorithms.
  arXiv  Detail & Related papers  (2024-02-05T21:24:11Z)
• Variational Quantum Algorithms for the Allocation of Resources in a Cloud/Edge Architecture [1.072460284847973]
  We show that Variational Quantum Algorithms can be a viable alternative to classical algorithms in the near future. In particular, we compare the performances, in terms of success probability, of two algorithms, i.e., Quantum Approximate Optimization Algorithm (QAOA) and Variational Quantum Eigensolver (VQE) The simulation experiments, performed for a set of simple problems, %CM230124 that involve a Cloud and two Edge nodes, show that the VQE algorithm ensures better performances when it is equipped with appropriate circuit textitansatzes that are able to restrict the search space
  arXiv  Detail & Related papers  (2024-01-25T17:37:40Z)
• Automatic and effective discovery of quantum kernels [41.61572387137452]
  Quantum computing can empower machine learning models by enabling kernel machines to leverage quantum kernels for representing similarity measures between data.<n>We present an approach to this problem, which employs optimization techniques, similar to those used in neural architecture search and AutoML.<n>The results obtained by testing our approach on a high-energy physics problem demonstrate that, in the best-case scenario, we can either match or improve testing accuracy with respect to the manual design approach.
  arXiv  Detail & Related papers  (2022-09-22T16:42:14Z)
• 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)
• Cluster-Promoting Quantization with Bit-Drop for Minimizing Network Quantization Loss [61.26793005355441]
  Cluster-Promoting Quantization (CPQ) finds the optimal quantization grids for neural networks. DropBits is a new bit-drop technique that revises the standard dropout regularization to randomly drop bits instead of neurons. We experimentally validate our method on various benchmark datasets and network architectures.
  arXiv  Detail & Related papers  (2021-09-05T15:15:07Z)
• A quantum algorithm for training wide and deep classical neural networks [72.2614468437919]
  We show that conditions amenable to classical trainability via gradient descent coincide with those necessary for efficiently solving quantum linear systems. We numerically demonstrate that the MNIST image dataset satisfies such conditions. We provide empirical evidence for $O(log n)$ training of a convolutional neural network with pooling.
  arXiv  Detail & Related papers  (2021-07-19T23:41:03Z)
• Accelerating variational quantum algorithms with multiple quantum processors [78.36566711543476]
  Variational quantum algorithms (VQAs) have the potential of utilizing near-term quantum machines to gain certain computational advantages. Modern VQAs suffer from cumbersome computational overhead, hampered by the tradition of employing a solitary quantum processor to handle large data. Here we devise an efficient distributed optimization scheme, called QUDIO, to address this issue.
  arXiv  Detail & Related papers  (2021-06-24T08:18:42Z)
• An optimal quantum sampling regression algorithm for variational eigensolving in the low qubit number regime [0.0]
  We introduce Quantum Sampling Regression (QSR), an alternative hybrid quantum-classical algorithm. We analyze some of its use cases based on time complexity in the low qubit number regime. We demonstrate the efficacy of our algorithm for a benchmark problem.
  arXiv  Detail & Related papers  (2020-12-04T00:01:15Z)
• Learning with Optimized Random Features: Exponential Speedup by Quantum Machine Learning without Sparsity and Low-Rank Assumptions [8.08640000394814]
  We develop a quantum algorithm for sampling from an optimized distribution over runtime features. Our algorithm achieves an exponential speedup in $D$ compared to any known classical algorithm for this sampling task.
  arXiv  Detail & Related papers  (2020-04-22T18:00:00Z)
• Lipschitz constant estimation of Neural Networks via sparse polynomial optimization [47.596834444042685]
  LiPopt is a framework for computing increasingly tighter upper bounds on the Lipschitz constant of neural networks. We show how to use the sparse connectivity of a network, to significantly reduce the complexity. We conduct experiments on networks with random weights as well as networks trained on MNIST.
  arXiv  Detail & Related papers  (2020-04-18T18:55:02Z)

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.