{
  "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.",
  "abstract_shown": true,
  "affiliations": [],
  "article_type": null,
  "arxiv": "2610.04560",
  "author_total": 6,
  "authors": [
    {
      "name": "Yonggang Jiang"
    },
    {
      "name": "Xiaoming Sun"
    },
    {
      "name": "Penghui Yao"
    },
    {
      "name": "Zekun Ye"
    },
    {
      "name": "Jialin Zhang"
    },
    {
      "name": "Zhijie Zhang"
    }
  ],
  "bibtex": "https://research.draconitic.com/paper/f9f9qs0qsgkh8.bib",
  "cited_by": 0,
  "doi": "10.48550/arxiv.2610.04560",
  "fulltext_url": null,
  "id": "f9f9qs0qsgkh8",
  "issns": [],
  "landing_url": "https://arxiv.org/abs/2610.04560",
  "language": null,
  "licence": "CC-BY-4.0",
  "licence_label": "CC BY 4.0",
  "licence_source": "article",
  "licence_url": "http://creativecommons.org/licenses/by/4.0/",
  "metadata_licence": "CC0-1.0",
  "native_subjects": [
    [
      "arxiv",
      "cs.CC"
    ],
    [
      "arxiv",
      "cs.DS"
    ],
    [
      "arxiv",
      "quant-ph"
    ],
    [
      "openalex",
      "1702|Quantum Computing Algorithms and Architecture"
    ]
  ],
  "openalex": "W7220671965",
  "pdf_url": "https://arxiv.org/pdf/2610.04560",
  "pmcid": null,
  "pmid": null,
  "published": "2026-10-03",
  "publisher": null,
  "ris": "https://research.draconitic.com/paper/f9f9qs0qsgkh8.ris",
  "sources": [
    {
      "first_seen": "2026-10-30T12:27:01Z",
      "native_id": "2610.04560",
      "source": "arxiv",
      "url": "https://arxiv.org/abs/2610.04560"
    }
  ],
  "subjects": [
    {
      "field": "physics",
      "origin": "arxiv:quant-ph",
      "subfield": "quantum"
    }
  ],
  "title": "Quantum Submodular Maximization",
  "title_text": "Quantum Submodular Maximization",
  "type": "preprint",
  "updated_at": "2026-10-30T12:27:01Z",
  "url": "https://research.draconitic.com/paper/f9f9qs0qsgkh8",
  "venue": "arXiv",
  "versions": []
}