{"ID":2895697,"CreatedAt":"2026-06-01T04:54:23.091178241Z","UpdatedAt":"2026-06-01T04:54:23.091178241Z","DeletedAt":null,"paper_url":"https://arxiv.org/abs/2507.08543","arxiv_id":"2507.08543","title":"Quantum Algorithms for Projection-Free Sparse Convex Optimization","abstract":"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 $\\mathcal{D} \\subset \\mathbb{R}^d$, we propose two quantum algorithms for sparse constraints that finds a $\\varepsilon$-optimal solution with the query complexity of $O(\\sqrt{d}/\\varepsilon)$ and $O(1/\\varepsilon)$ by using the function value oracle, reducing a factor of $O(\\sqrt{d})$ and $O(d)$ over the best classical algorithm, respectively, where $d$ is the dimension. For the matrix domain $\\mathcal{D} \\subset \\mathbb{R}^{d\\times d}$, we propose two quantum algorithms for nuclear norm constraints that improve the time complexity to $\\tilde{O}(rd/\\varepsilon^2)$ and $\\tilde{O}(\\sqrt{r}d/\\varepsilon^3)$ for computing the update step, reducing at least a factor of $O(\\sqrt{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$.","short_abstract":"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 $\\mathcal{D} \\subset \\mathbb{R}^d$, we propose two quantum algorithms for sparse cons...","url_abs":"https://arxiv.org/abs/2507.08543","url_pdf":"https://arxiv.org/pdf/2507.08543v1","authors":"[\"Jianhao He\",\"John C. S. Lui\"]","published":"2025-07-11T12:43:58Z","proceeding":"quant-ph","tasks":"[\"quant-ph\",\"cs.LG\"]","methods":"[]","has_code":false}