# Quantum Speedup for Spectral Approximation of Kronecker Products

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

## Key facts

- Cited by 1 papers in the map (data through 14 Oct 2026).
- Builds on 29 of its 54 references that are in the map.
- First posted on arXiv 10 Feb 2024.

## Builds on (most cited first, 29 of 29)

- [Tensor Decomposition for Signal Processing and Machine Learning](https://mlsanity.com/paper/1607.01668/) (2016)
- [Training Multi-Layer Over-Parametrized Neural Network in Subquadratic Time](https://mlsanity.com/paper/2112.07628/) (2021)
- [q-means: A quantum algorithm for unsupervised machine learning](https://mlsanity.com/paper/1812.03584/) (2018)
- [A Faster Interior Point Method for Semidefinite Programming](https://mlsanity.com/paper/2009.10217/) (2020)
- [A Faster Cutting Plane Method and its Implications for Combinatorial and Convex Optimization](https://mlsanity.com/paper/1508.04874/) (2015)
- [Relative Error Tensor Low Rank Approximation](https://mlsanity.com/paper/1704.08246/) (2017)
- [Fast Sketching of Polynomial Kernels of Polynomial Degree](https://mlsanity.com/paper/2108.09420/) (2021)
- [Uniform Sampling for Matrix Approximation](https://mlsanity.com/paper/1408.5099/) (2014)
- [The power of block-encoded matrix powers: improved regression techniques via faster Hamiltonian simulation](https://mlsanity.com/paper/1804.01973/) (2018)
- [Optimal CUR Matrix Decompositions](https://mlsanity.com/paper/1405.7910/) (2014)
- [Sketching for Kronecker Product Regression and P-splines](https://mlsanity.com/paper/1712.09473/) (2017)
- [Optimal Sketching for Kronecker Product Regression and Low Rank Approximation](https://mlsanity.com/paper/1909.13384/) (2019)
- [Quantum SDP-Solvers: Better upper and lower bounds](https://mlsanity.com/paper/1705.01843/) (2017)
- [A near-optimal algorithm for approximating the John Ellipsoid](https://mlsanity.com/paper/1905.11580/) (2019)
- [Speeding Up Sparsification using Inner Product Search Data Structures](https://mlsanity.com/paper/2204.03209/) (2022)
- [Solving Tall Dense Linear Programs in Nearly Linear Time](https://mlsanity.com/paper/2002.02304/) (2020)
- [Bipartite Matching in Nearly-linear Time on Moderately Dense Graphs](https://mlsanity.com/paper/2009.01802/) (2020)
- [Quantum Algorithms and Lower Bounds for Linear Regression with Norm Constraints](https://mlsanity.com/paper/2110.13086/) (2021)
- [Quantum Speedups of Optimizing Approximately Convex Functions with Applications to Logarithmic Regret Stochastic Convex Bandits](https://mlsanity.com/paper/2209.12897/) (2022)
- [Quantum Speedup for Graph Sparsification, Cut Approximation and Laplacian Solving](https://mlsanity.com/paper/1911.07306/) (2019)
- [Quantum Boosting](https://mlsanity.com/paper/2002.05056/) (2020)
- [Quantum Regularized Least Squares](https://mlsanity.com/paper/2206.13143/) (2022)
- [Quantum Algorithms for Sampling Log-Concave Distributions and Estimating Normalizing Constants](https://mlsanity.com/paper/2210.06539/) (2022)
- [Navigating Central Path with Electrical Flows: from Flows to Matchings, and Back](https://mlsanity.com/paper/1307.2205/) (2013)
- [An almost-linear time algorithm for uniform random spanning tree generation](https://mlsanity.com/paper/1711.06455/) (2017)
- [Quantum tomography using state-preparation unitaries](https://mlsanity.com/paper/2207.08800/) (2022)
- [Do you know what q-means?](https://mlsanity.com/paper/2308.09701/) (2023)
- [A CS guide to the quantum singular value transformation](https://mlsanity.com/paper/2302.14324/) (2023)
- [Faster Energy Maximization for Faster Maximum Flow](https://mlsanity.com/paper/1910.14276/) (2019)

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

- [LazyDiT: Lazy Learning for the Acceleration of Diffusion Transformers](https://mlsanity.com/paper/2412.12444/) (2024)

## Abstract (arXiv)

Given its widespread application in machine learning and optimization, the Kronecker product emerges as a pivotal linear algebra operator. However, its computational demands render it an expensive operation, leading to heightened costs in spectral approximation of it through traditional computation algorithms. Existing classical methods for spectral approximation exhibit a linear dependency on the matrix dimension denoted by n, considering matrices of size A1 ∈ ℝn × d and A2 ∈ ℝn × d. Our work introduces an innovative approach to efficiently address the spectral approximation of the Kronecker product A1 otimes A2 using quantum methods. By treating matrices as quantum states, our proposed method significantly reduces the time complexity of spectral approximation to Od,ε(√n).