# Quantum Ridgelet Transform: Winning Lottery Ticket of Neural Networks with Quantum Computation

arXiv: https://arxiv.org/abs/2301.11936 · HTML: https://mlsanity.com/paper/2301.11936/

## Key facts

- Cited by 5 papers in the map (data through 14 Oct 2026).
- Builds on 31 of its 96 references that are in the map.
- First posted on arXiv 27 Jan 2023.

## Builds on (most cited first, 30 of 31)

- [The Lottery Ticket Hypothesis: Finding Sparse, Trainable Neural Networks](https://mlsanity.com/paper/1803.03635/) (2018)
- [SNIP: Single-shot Network Pruning based on Connection Sensitivity](https://mlsanity.com/paper/1810.02340/) (2018)
- [Pruning neural networks without any data by iteratively conserving synaptic flow](https://mlsanity.com/paper/2006.05467/) (2020)
- [Picking Winning Tickets Before Training by Preserving Gradient Flow](https://mlsanity.com/paper/2002.07376/) (2020)
- [A rigorous and robust quantum speed-up in supervised machine learning](https://mlsanity.com/paper/2010.02174/) (2020)
- [What's Hidden in a Randomly Weighted Neural Network?](https://mlsanity.com/paper/1911.13299/) (2019)
- [Supermasks in Superposition](https://mlsanity.com/paper/2006.14769/) (2020)
- [Deconstructing Lottery Tickets: Zeros, Signs, and the Supermask](https://mlsanity.com/paper/1905.01067/) (2019)
- [Proving the Lottery Ticket Hypothesis: Pruning is All You Need](https://mlsanity.com/paper/2002.00585/) (2020)
- [Quantum advantage in learning from experiments](https://mlsanity.com/paper/2112.00778/) (2021)
- [Pruning Neural Networks at Initialization: Why are We Missing the Mark?](https://mlsanity.com/paper/2009.08576/) (2020)
- [On the Equivalence between Kernel Quadrature Rules and Random Feature Expansions](https://mlsanity.com/paper/1502.06800/) (2015)
- [Tight Analyses for Non-Smooth Stochastic Gradient Descent](https://mlsanity.com/paper/1812.05217/) (2018)
- [Information-theoretic bounds on quantum advantage in machine learning](https://mlsanity.com/paper/2101.02464/) (2021)
- [Quantum machine learning: a classical perspective](https://mlsanity.com/paper/1707.08561/) (2017)
- [Optimal Lottery Tickets via SubsetSum: Logarithmic Over-Parameterization is Sufficient](https://mlsanity.com/paper/2006.07990/) (2020)
- [Pruning from Scratch](https://mlsanity.com/paper/1909.12579/) (2019)
- [Logarithmic Pruning is All You Need](https://mlsanity.com/paper/2006.12156/) (2020)
- [Quantum Recommendation Systems](https://mlsanity.com/paper/1603.08675/) (2016)
- [A quantum-inspired classical algorithm for recommendation systems](https://mlsanity.com/paper/1807.04271/) (2018)
- [Neural Network with Unbounded Activation Functions is Universal Approximator](https://mlsanity.com/paper/1505.03654/) (2015)
- [On the Quantum versus Classical Learnability of Discrete Distributions](https://mlsanity.com/paper/2007.14451/) (2020)
- [Exponential separations between learning with and without quantum memory](https://mlsanity.com/paper/2111.05881/) (2021)
- [The power of block-encoded matrix powers: improved regression techniques via faster Hamiltonian simulation](https://mlsanity.com/paper/1804.01973/) (2018)
- [On the minimax optimality and superiority of deep neural network learning over sparse parameter spaces](https://mlsanity.com/paper/1905.09195/) (2019)
- [Quantum Computing: Lecture Notes](https://mlsanity.com/paper/1907.09415/) (2019)
- [Fully-Connected Network on Noncompact Symmetric Space and Ridgelet Transform based on Helgason-Fourier Analysis](https://mlsanity.com/paper/2203.01631/) (2022)
- [Universality of Group Convolutional Neural Networks Based on Ridgelet Analysis on Groups](https://mlsanity.com/paper/2205.14819/) (2022)
- [Learning with Optimized Random Features: Exponential Speedup by Quantum Machine Learning without Sparsity and Low-Rank Assumptions](https://mlsanity.com/paper/2004.10756/) (2020)
- [Exponential Error Convergence in Data Classification with Optimized Random Features: Acceleration by Quantum Machine Learning](https://mlsanity.com/paper/2106.09028/) (2021)

## Built on by (most cited first, 5 of 5)

- [Advantage of Quantum Machine Learning from General Computational Advantages](https://mlsanity.com/paper/2312.03057/) (2023)
- [A unified Fourier slice method to derive ridgelet transform for a variety of depth-2 neural networks](https://mlsanity.com/paper/2402.15984/) (2024)
- [Deep Ridgelet Transform and Unified Universality Theorem for Deep and Shallow Joint-Group-Equivariant Machines](https://mlsanity.com/paper/2405.13682/) (2024)
- [Winning Lottery Tickets in Neural Networks via a Quantum-Inspired Classical Algorithm](https://mlsanity.com/paper/2605.13979/) (2026)
- [A Quantum-Inspired Dequantization Method for Diagonally Weighted Matrix Functions: Application to Learning with Optimized Random Features](https://mlsanity.com/paper/2609.10729/) (2026)

## Abstract (arXiv)

A significant challenge in the field of quantum machine learning (QML) is to establish applications of quantum computation to accelerate common tasks in machine learning such as those for neural networks. Ridgelet transform has been a fundamental mathematical tool in the theoretical studies of neural networks, but the practical applicability of ridgelet transform to conducting learning tasks was limited since its numerical implementation by conventional classical computation requires an exponential runtime exp(O(D)) as data dimension D increases. To address this problem, we develop a quantum ridgelet transform (QRT), which implements the ridgelet transform of a quantum state within a linear runtime O(D) of quantum computation. As an application, we also show that one can use QRT as a fundamental subroutine for QML to efficiently find a sparse trainable subnetwork of large shallow wide neural networks without conducting large-scale optimization of the original network. This application discovers an efficient way in this regime to demonstrate the lottery ticket hypothesis on finding such a sparse trainable neural network. These results open an avenue of QML for accelerating learning tasks with commonly used classical neural networks.