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−ε)-approximation using only Oε(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−ε)-approximation using Õε(min{√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−ε, the query complexity reduces to Oε,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(Ω(ε2n)) queries for achieving a ratio beyond 1/2+ε without constraints, and exp(Ω(ε2k)) queries for exceeding 1−1/e+ε when k/n≤ε. These barriers demonstrate that quantum computation offers no exponential speedup at these approximation thresholds.
Related
- Maximization of nuclear fusion reactivity via optimal energy distributions
- One ring to rule them all: syzygy maximization for Argyres-Douglas
- Maximization of accelerated charge in multibunch-driven plasma wakefield accelerators
- Constrained modularity maximization in complex networks via branch-and-price
- Charging of a quantum battery by a two-photon quantum pulse
BibTeX
@misc{jiang2026quantum,
title = {{Quantum Submodular Maximization}},
author = {Yonggang Jiang and Xiaoming Sun and Penghui Yao and Zekun Ye and Jialin Zhang and Zhijie Zhang},
howpublished = {arXiv},
year = {2026},
month = oct,
doi = {10.48550/arxiv.2610.04560},
eprint = {2610.04560},
archivePrefix = {arXiv},
url = {https://arxiv.org/abs/2610.04560},
note = {CC BY 4.0},
}
RIS
TY - UNPB
TI - Quantum Submodular Maximization
AU - Yonggang Jiang
AU - Xiaoming Sun
AU - Penghui Yao
AU - Zekun Ye
AU - Jialin Zhang
AU - Zhijie Zhang
PY - 2026
DA - 2026/10/03
PB - arXiv
DO - 10.48550/arxiv.2610.04560
UR - https://arxiv.org/abs/2610.04560
AB - 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−ε)-approximation using only O_ε(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−ε)-approximation using Õ_ε(min{√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−ε, the query complexity reduces to O_ε,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(Ω(ε^2n)) queries for achieving a ratio beyond 1/2+ε without constraints, and exp(Ω(ε^2k)) queries for exceeding 1−1/e+ε when k/n≤ε. These barriers demonstrate that quantum computation offers no exponential speedup at these approximation thresholds.
ER -