Quantum Submodular Maximization

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(n) queries. In contrast, any classical randomized algorithm that attains a fixed expected ratio above 1/4 requires Ω(n/ 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 O epsilon(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(n), yielding an exponential separation from the classical Ω(n/ n) lower bound (Li, Feldman, Kazemi, and Karbasi, 2022). We further prove quantum lower bounds of (Ω(epsilon 2n)) queries for achieving a ratio beyond 1/2+ epsilon without constraints, and (Ω(epsilon 2k)) queries for exceeding 1-1/e+ epsilon when k/n epsilon. These barriers demonstrate that quantum computation offers no exponential speedup at these approximation thresholds.