Quantum algorithms speed up submodular function maximization tasks
Quantum Submodular Maximization
Computational ComplexityData Structures and Algorithms
Summary
Maximizing submodular functions is a common problem in computer science, often used to select the best subset from many options. The authors study quantum algorithms that can find good-enough solutions much faster than classical methods in certain cases. They show their quantum approach can get close to half the best solution with exponentially fewer queries in some settings. However, they also prove that beyond some quality level, quantum computers don't offer big speedups. This work maps where quantum advantages are possible for these optimization problems.
What this means in practice
- •For data scientists: Select large but informative feature subsets faster when working with huge datasets, using quantum algorithms to reduce computational queries.
- •For network administrators: Speed up resource allocation decisions under size constraints using quantum techniques to efficiently find near-optimal solutions.
A theory result. No direct application yet.
Authors
Yonggang Jiang, Xiaoming Sun, Penghui Yao, Zekun Ye, Jialin Zhang, Zhijie Zhang
Abstract
We study the quantum query complexity of maximizing a non-negative submodular function, considering both the unconstrained setting and, for monotone functions, a cardinality constraint $k$ on an $n$-element ground set. In the exact reversible digital value-oracle model, our unconstrained algorithm achieves an expected $(1/2-\varepsilon)$-approximation using only $O_\varepsilon(\log n)$ queries. In contrast, any classical randomized algorithm that attains a fixed expected ratio above $1/4$ requires $Ω(n/\log n)$ queries (Li, Feldman, Kazemi, and Karbasi, 2022), establishing an exponential separation in query complexity. For cardinality-constrained maximization, we give a bounded-error quantum algorithm that achieves a $(1-1/e-\varepsilon)$-approximation using $\widetilde O_\varepsilon(\min\{\sqrt n,n/k\})$ queries. When $k=o(n)$, our algorithm achieves at least a quadratic speedup up to logarithmic factors over classical randomized algorithms (Mirzasoleiman, Badanidiyuru, Karbasi, Vondrák, and Krause, 2015; Peng and Rubinstein, 2025). Moreover, when $k=cn$ for any fixed rational $c<1-1/e-\varepsilon$, the query complexity reduces to $O_{\varepsilon,c}(\log n)$, yielding an exponential separation from the classical $Ω(n/\log n)$ lower bound (Li, Feldman, Kazemi, and Karbasi, 2022). We further prove quantum lower bounds of $\exp(Ω(\varepsilon^2n))$ queries for achieving a ratio beyond $1/2+\varepsilon$ without constraints, and $\exp(Ω(\varepsilon^2k))$ queries for exceeding $1-1/e+\varepsilon$ when $k/n\le\varepsilon$. These barriers demonstrate that quantum computation offers no exponential speedup at these approximation thresholds.