# Quantum Algorithms for Projection-Free Sparse Convex Optimization

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

## Key facts

- No citing papers in the map yet (data through 14 Oct 2026).
- Builds on 35 of its 79 references that are in the map.
- First posted on arXiv 11 Jul 2025.

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

- [Quantum Recommendation Systems](https://mlsanity.com/paper/1603.08675/) (2016)
- [A Theoretical and Empirical Comparison of Gradient Approximations in Derivative-Free Optimization](https://mlsanity.com/paper/1905.01332/) (2019)
- [Variance-Reduced and Projection-Free Stochastic Optimization](https://mlsanity.com/paper/1602.02101/) (2016)
- [One Sample Stochastic Frank-Wolfe](https://mlsanity.com/paper/1910.04322/) (2019)
- [Projection-Free Online Optimization with Stochastic Gradient: From Convexity to Submodularity](https://mlsanity.com/paper/1802.08183/) (2018)
- [The power of block-encoded matrix powers: improved regression techniques via faster Hamiltonian simulation](https://mlsanity.com/paper/1804.01973/) (2018)
- [The Complexity of Large-scale Convex Programming under a Linear Optimization Oracle](https://mlsanity.com/paper/1309.5550/) (2013)
- [Quantum SDP-Solvers: Better upper and lower bounds](https://mlsanity.com/paper/1705.01843/) (2017)
- [Quantum exploration algorithms for multi-armed bandits](https://mlsanity.com/paper/2007.07049/) (2020)
- [Convex optimization using quantum oracles](https://mlsanity.com/paper/1809.00643/) (2018)
- [Sublinear quantum algorithms for training linear and kernel-based classifiers](https://mlsanity.com/paper/1904.02276/) (2019)
- [Efficient Projection-Free Online Methods with Stochastic Recursive Gradient](https://mlsanity.com/paper/1910.09396/) (2019)
- [Quantum Multi-Armed Bandits and Stochastic Linear Bandits Enjoy Logarithmic Regrets](https://mlsanity.com/paper/2205.14988/) (2022)
- [Quantum Bandits](https://mlsanity.com/paper/2002.06395/) (2020)
- [A Quantum Interior Point Method for LPs and SDPs](https://mlsanity.com/paper/1808.09266/) (2018)
- [Linear Convergence of a Frank-Wolfe Type Algorithm over Trace-Norm Balls](https://mlsanity.com/paper/1708.02105/) (2017)
- [Quantum algorithms and lower bounds for convex optimization](https://mlsanity.com/paper/1809.01731/) (2018)
- [Conditional Gradient Algorithms for Norm-Regularized Smooth Convex Optimization](https://mlsanity.com/paper/1302.2325/) (2013)
- [Quantum speedups for stochastic optimization](https://mlsanity.com/paper/2308.01582/) (2023)
- [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)
- [Frank-Wolfe and friends: a journey into projection-free first-order optimization methods](https://mlsanity.com/paper/2106.10261/) (2021)
- [Faster Projection-free Convex Optimization over the Spectrahedron](https://mlsanity.com/paper/1605.06203/) (2016)
- [The Frank-Wolfe algorithm: a short introduction](https://mlsanity.com/paper/2311.05313/) (2023)
- [Quantum Expectation-Maximization for Gaussian Mixture Models](https://mlsanity.com/paper/1908.06657/) (2019)
- [Quantum Algorithms for Portfolio Optimization](https://mlsanity.com/paper/1908.08040/) (2019)
- [Quantum Langevin Dynamics for Optimization](https://mlsanity.com/paper/2311.15587/) (2023)
- [Quantum Lower Bounds for Finding Stationary Points of Nonconvex Functions](https://mlsanity.com/paper/2212.03906/) (2022)
- [Quantum algorithms for Second-Order Cone Programming and Support Vector Machines](https://mlsanity.com/paper/1908.06720/) (2019)
- [Quantum Algorithms and Lower Bounds for Finite-Sum Optimization](https://mlsanity.com/paper/2406.03006/) (2024)

## Abstract (arXiv)

This paper considers the projection-free sparse convex optimization problem for the vector domain and the matrix domain, which covers a large number of important applications in machine learning and data science. For the vector domain D subset ℝd, we propose two quantum algorithms for sparse constraints that finds a varepsilon-optimal solution with the query complexity of O(√d/varepsilon) and O(1/varepsilon) by using the function value oracle, reducing a factor of O(√d) and O(d) over the best classical algorithm, respectively, where d is the dimension. For the matrix domain D subset ℝd× d, we propose two quantum algorithms for nuclear norm constraints that improve the time complexity to tildeO(rd/varepsilon2) and tildeO(√rd/varepsilon3) for computing the update step, reducing at least a factor of O(√d) over the best classical algorithm, where r is the rank of the gradient matrix. Our algorithms show quantum advantages in projection-free sparse convex optimization problems as they outperform the optimal classical methods in dependence on the dimension d.