論文の概要: Quantum Submodular Maximization

• arxiv url: http://arxiv.org/abs/2610.04560v1
• Date: Sat, 03 Oct 2026 14:51:06 GMT
• ステータス: 翻訳完了
• システム内更新日: 2026-10-11 18:50:21.731741
• Title: Quantum Submodular Maximization
• Title（参考訳）: 量子サブモジュラー最大化
• Abstract要約: 提案アルゴリズムは,O_varepsilon(log n)$クエリのみを用いて,期待される$(1/2-varepsilon)$-approximationを実現する。 対照的に、1/4$を超える固定予測比を達成するような古典的ランダム化アルゴリズムは、$(n/log n)$クエリを必要とする。 我々は、制約のない1/2+varepsilon$を超える比率を達成するために、$exp(varepsilon2n)$クエリの量子下界を証明した。
• 参考スコア（独自算出の注目度）: 14.165444015073307
• License: http://creativecommons.org/licenses/by/4.0/
• 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（参考訳）: 我々は、非負の部分モジュラ函数を最大化する量子クエリの複雑さについて、制約のない設定と単調な関数に対して、$n$-要素基底集合上の濃度制約$k$を考える。 正確な可逆的ディジタル値オークレモデルでは、制約のないアルゴリズムは、O_\varepsilon(\log n)$クエリのみを用いて、期待される$(1/2-\varepsilon)$-approximationを達成する。 対照的に、1/4$を超える固定された期待比に達する任意の古典的ランダム化アルゴリズムは、クエリー(Li, Feldman, Kazemi, Karbasi, 2022)に$Ω(n/\log n)を要求し、クエリーの複雑さを指数関数的に分離する。 1-1/e-\varepsilon)$-approximation with $\widetilde O_\varepsilon(\min\{\sqrt n,n/k\})$ query。 k=o(n)$のとき、我々のアルゴリズムは古典的ランダム化アルゴリズム(Mirzasoleiman, Badanidiyuru, Karbasi, Vondrák, Krause, 2015; Peng and Rubinstein, 2025)よりも、少なくとも2次的なスピードアップを達成する。 さらに、任意の固定有理数$c<1-1/e-\varepsilon$に対して$k=cn$となると、クエリ複雑性は$O_{\varepsilon,c}(\log n)$に減少し、古典的な$Ω(n/\log n)$下界(Li, Feldman, Kazemi, Karbasi, 2022)から指数的に分離する。 さらに、制約なしで1/2+\varepsilon$を超える比を得るための$\exp(Ω(\varepsilon^2n))$クエリと、1-1/e+\varepsilon$を超える場合の$\exp(Ω(\varepsilon^2k))$クエリをさらに証明する。 これらの障壁は、量子計算がこれらの近似しきい値において指数的なスピードアップを提供しないことを示す。

関連論文リスト

• A Sharp Barrier for Consistent Submodular Maximization: Any Improvement over $2-\sqrt{2}$ Entails Exponential Queries or Linear Recourse [50.69285844345291]
  我々は、要素が時間とともに到着する際のソリューションの品質と安定性のトレードオフについて研究する。 我々のアルゴリズムは,有理オラクル$を$O(varepsilon-1)$recourseで実装し,そのアルゴリズムから普遍価格証明書の存在を分離する。
  論文  参考訳（メタデータ） (2026-09-09T10:13:43Z)
• Faster quantum linear system solver beyond the condition number [50.84794327094274]
  線形系の正規化解 $|xrangle$ を生成する2つの量子アルゴリズムを、条件数$=lVert A-1rVert$ に依存しない複雑性を持つ精度 $Ax=| b rangle$ に提示する。 フィルタベースのソルバは非常にシンプルで、実行時プレファクタが適しています。
  論文  参考訳（メタデータ） (2026-07-08T17:49:40Z)
• Min-Max Optimization Requires Exponentially Many Queries [71.85811744604827]
  非min-nonconcave 関数 $f$ $[0,1] のクエリ複雑性。 f$ へのクエリとその勾配点が 1 ord$ で指数関数的な点を成さなければならないことを示す。
  論文  参考訳（メタデータ） (2026-05-13T17:34:24Z)
• Sublinear Time Quantum Sensitivity Sampling [57.356528942341534]
  本稿では、量子感応サンプリングのための統一的なフレームワークを提案し、量子コンピューティングの利点を古典近似問題の幅広いクラスに拡張する。 我々のフレームワークは、コアセットを構築するための合理化されたアプローチを提供し、クラスタリング、回帰、低ランク近似などのアプリケーションにおいて、大幅なランタイム改善を提供します。
  論文  参考訳（メタデータ） (2025-09-20T20:18:49Z)
• Exponential Lindbladian fast forwarding and exponential amplification of certain Gibbs state properties [3.3728077347699497]
  リンドブラディアン高速フォワード法とそのギブス状態特性推定への応用について検討する。 ファストフォワード(Fast-forwarding)とは、$t$よりもはるかに少ないクエリや回路深度を用いて、時間$t$のシステムをシミュレートする機能である。
  論文  参考訳（メタデータ） (2025-09-11T14:57:53Z)
• Efficient Non-Adaptive Quantum Algorithms for Tolerant Junta Testing [18.89209417623036]
  我々は、$n$-qubitユニタリが$varepsilon$-close to some $k$-junta or $varepsilon$-far from every $k$-junta。 単一量子ビット演算のみを用いて実装される最初の2つの量子アルゴリズムに適応し、実験可能性を高める。
  論文  参考訳（メタデータ） (2025-08-24T11:15:40Z)
• Quantum spectral method for gradient and Hessian estimation [4.193480001271463]
  勾配降下は連続最適化問題を解くための最も基本的なアルゴリズムの1つである。 本稿では、クエリの複雑さを$widetildeO (1/varepsilon)$とすることで、その勾配の$varepsilon$-approximationを返す量子アルゴリズムを提案する。 また、ニュートン法の量子アナログを改善することを目的としたヘッセン推定のための2つの量子アルゴリズムを提案する。
  論文  参考訳（メタデータ） (2024-07-04T11:03:48Z)
• An Optimal Separation of Randomized and Quantum Query Complexity [67.19751155411075]
  すべての決定木に対して、与えられた順序 $ellsqrtbinomdell (1+log n)ell-1,$ sum to at least $cellsqrtbinomdell (1+log n)ell-1,$ where $n$ is the number of variables, $d$ is the tree depth, $c>0$ is a absolute constant。
  論文  参考訳（メタデータ） (2020-08-24T06:50:57Z)
• Continuous Submodular Maximization: Beyond DR-Submodularity [48.04323002262095]
  最初に、バニラ座標の昇華の単純な変種を証明し、Coordinate-Ascent+ と呼ぶ。 次にCoordinate-Ascent++を提案し、同じ回数のイテレーションを実行しながら(1-1/e-varepsilon)$-approximationを保証する。 Coordinate-Ascent++の各ラウンドの計算は容易に並列化でき、マシン当たりの計算コストは$O(n/sqrtvarepsilon+nlog n)$である。
  論文  参考訳（メタデータ） (2020-06-21T06:57:59Z)

関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。

指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。