Quantum Submodular Maximization

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-\epsilon )$-approximation using only $O_{\epsilon }(\log n)$ queries. In contrast, any classical randomized algorithm that attains a fixed expected ratio above $1/4$ requires $\Omega (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-\epsilon )$-approximation using ${\tilde{O}}_{\epsilon }(\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-\epsilon$, the query complexity reduces to $O_{\epsilon ,c}(\log n)$, yielding an exponential separation from the classical $\Omega (n/\log n)$ lower bound (Li, Feldman, Kazemi, and Karbasi, 2022). We further prove quantum lower bounds of $\exp (\Omega ({\epsilon }^{2}n))$ queries for achieving a ratio beyond $1/2+\epsilon$ without constraints, and $\exp (\Omega ({\epsilon }^{2}k))$ queries for exceeding $1-1/e+\epsilon$ when $k/n\le \epsilon$. These barriers demonstrate that quantum computation offers no exponential speedup at these approximation thresholds.

62 pages; abstract shortened for arXiv