arXiv:2610.04560
Quantum Submodular Maximization
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.
AI Summary
The paper studies the quantum value-query complexity of maximizing nonnegative submodular functions, both without constraints and, for monotone objectives, under a cardinality budget $k$ on an $n$-element ground set. Access is through an exact reversible digital value oracle; queries may address infeasible sets. For unconstrained maximization, it gives an expected $(1/2-\varepsilon)$-approximation using $O(\varepsilon^{-4}\log(2n/\varepsilon)\log(2/\varepsilon))$ queries. For fixed accuracy, this is $O(\log n)$, versus the classical $\Omega(n/\log n)$ requirement for any fixed expected ratio above $1/4$. For monotone cardinality-constrained maximization, a bounded-error $(1-1/e-\varepsilon)$-approximation uses $\widetilde O(\min\{\varepsilon^{-3}\sqrt n,\varepsilon^{-4}n/k\})$ queries. At fixed density $k=cn$, the bound becomes $O_{\varepsilon,c}(\log n)$, yielding an exponential separation when $c<1-1/e-\varepsilon$. Both algorithms extract simultaneous marginal statistics from local measurements of Boolean phase states. The unconstrained algorithm combines Fourier-based gradient reconstruction with noisy simultaneous double greedy and random restrictions. The constrained algorithm estimates random-order marginal scores, certifies batches by exact value checks, and amortizes amplitude-amplification cost against obtained gain. Quantum hybrid arguments applied to hidden-instance constructions give exponential lower bounds above the classical approximation thresholds: $\exp(\Omega(\varepsilon^2n))$ beyond $1/2$, and $\exp(\Omega(\varepsilon^2k))$ beyond $1-1/e$ when $k/n\le\varepsilon$. A further $\Omega_a(\sqrt{n/k})$ bound holds for constant approximation ratio $a$. The results bound queries, not runtime, gate complexity, or output cost. They rely on exact value access; the unconstrained algorithm permits exact unrestricted inter-query operations. The cardinality bounds remain unmatched for growing $k$, and the exponential lower bounds leave possible quadratic improvements unresolved.
assisted in exploring algorithmic ideas, developing and refining proofs of the approximation and running-time guarantees, examining connections to related work, and drafting and revising the manuscript.
Written by gpt-6.1-sol from the paper's full text. Automated: it can be wrong.
- Comments
- 62 pages; abstract shortened for arXiv