Research map / Learning theory and algorithms / Matrix and tensor methods

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

NeurIPS 2026 · Learning theory and algorithms › Matrix and tensor methods · approach: Sparse regression with guarantees · 0 citations (OpenAlex)

Read the paperCheck your idea against 108,967 papers

AI-extracted summary. Written by AI from the paper's full text. Numbers and claims can be wrong or missing context, so check the paper before you cite or build on it.

Gives a fully classical, polynomial-in-data-dimension sampler for the optimized ridgelet distribution used in quantum lottery-ticket sparse subnetwork construction, by exploiting ridgelet isometry to avoid the dense inverse, and also improves the quantum sampler by removing its 1/λ dependence.

Problem

Sampling hidden-node parameters from an optimized ridgelet-based distribution for sparse subnetwork construction requires inverting an exponentially large dense regularized matrix (and normalizing over exponentially many nodes), which takes exp(O(D)) time classically and previously needed quantum co

Approach

Using the isometry of the discrete ridgelet transform and diagonality of the empirical data distribution, the inverse decomposes so the regularized ridgelet coefficients reduce to a diagonal reweighting over the M data points followed by the ridgelet transform; a binary-tree sampling-and-query data structure plus rejection sampling with a data-dependent proposal q then yields an exact-target sampl

Key results

• Empirical risk of the dequantized sampler (delta=0.1) closely tracks exact sampling from the optimized distribution across D=1..6 and is lower than uniform sampling in the middle regime of N.
• Naive exact sampler runtime fits P^{2.85D} for D>=6, while the dequantized sampler fits D^{2.55} over the measured range (D up to 128).
• Theoretical runtime O(D log(1/delta)) * tilde O(M^2 gamma/Delta); the improved quantum sampler removes the 1/lambda dependence.

Surprising findings

• For large D, the less accurate setting delta=0.1 tracks the exact sampler more closely than the looser delta=0.7 setting, as reported in the text.

Limitations

• Polynomial runtime only holds when M=poly(D) and gamma, 1/Delta, log(1/delta) are polynomially bounded.
• Experiments are on small discrete domains (P=7 or P=3) with synthetic sine targets only.
• Dequantization is for the sampling subroutine only; end-to-end comparison with quantum hardware overhead not assessed.

Experimental setup

Datasets: synthetic sine target on discrete domain Z_P^D

Benchmarks: synthetic sine regression on Z_P^D (empirical risk vs number of nodes N) runtime scaling vs data dimension D

Metrics: empirical risk runtime scaling exponent

Baselines: naive classical exact sampling uniform distribution sampling previous quantum ridgelet sampler

Builds on: quantum ridgelet transform quantum singular value transformation quantum-inspired classical algorithms (Tang) lottery ticket hypothesis random feature method

Closest papers by meaning

• Quantum Ridgelet Transform: Winning Lottery Ticket of Neural Networks with Quantum Computation (ICML 2023 · similarity 0.91)
• Limitations of measure-first protocols in quantum machine learning (ICML 2025 · similarity 0.87)
• On the Relation between Trainability and Dequantization of Variational Quantum Learning Models (ICLR 2025 · similarity 0.87)
• ATP: Adaptive Threshold Pruning for Efficient Data Encoding in Quantum Neural Networks (CVPR 2025 · similarity 0.86)
• Exponential Quantum Communication Advantage in Distributed Inference and Learning (NeurIPS 2024 · similarity 0.86)
• TensorRL-QAS: Reinforcement learning with tensor networks for improved quantum architecture search (NeurIPS 2025 · similarity 0.86)