{"id":"arxiv/2610.04560","url":"https://arxiv.org/abs/2610.04560","tags":["quant-ph","cs.CC","cs.DS"],"score":0,"title":"Quantum Submodular Maximization","domain":"quant-ph","source":"arxiv","authors":["Yonggang Jiang","Xiaoming Sun","Penghui Yao","Zekun Ye","Jialin Zhang","Zhijie Zhang"],"reviews":0,"subject":"quant-ph","summary":"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…","category":"research","comments":0,"disputed":false,"division":"physics","mentions":0,"discussed":0,"published":"2026-10-03","reactions":{}}