論文の概要: Quantum Algorithms for Bandits with Knapsacks with Improved Regret and Time Complexities

• arxiv url: http://arxiv.org/abs/2507.04438v1
• Date: Sun, 06 Jul 2025 15:52:37 GMT
• ステータス: 翻訳完了
• システム内更新日: 2025-07-08 15:46:35.182015
• Title: Quantum Algorithms for Bandits with Knapsacks with Improved Regret and Time Complexities
• Title（参考訳）: レグレットと時間複雑性を改良したクナプサックを用いた帯域の量子アルゴリズム
• Authors: Yuexin Su, Ziyi Yang, Peiyuan Huang, Tongyang Li, Yinyu Ye,
• Abstract要約: knapsacks (BwK) を用いたバンドは、整数プログラミングとオンライン学習を組み合わせたモデルを構成する。 量子コンピューティングの設定において、報酬とリソース消費の両方を量子オラクルを介してアクセスすることができるBwKモデルについて検討する。 多腕バンディットの量子アルゴリズムに関するこれまでの研究と比較して、資源制約のあるバンディットモデルを考えるのはこれが初めてである。
• 参考スコア（独自算出の注目度）: 23.221938246770712
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: Bandits with knapsacks (BwK) constitute a fundamental model that combines aspects of stochastic integer programming with online learning. Classical algorithms for BwK with a time horizon $T$ achieve a problem-independent regret bound of ${O}(\sqrt{T})$ and a problem-dependent bound of ${O}(\log T)$. In this paper, we initiate the study of the BwK model in the setting of quantum computing, where both reward and resource consumption can be accessed via quantum oracles. We establish both problem-independent and problem-dependent regret bounds for quantum BwK algorithms. For the problem-independent case, we demonstrate that a quantum approach can improve the classical regret bound by a factor of $(1+\sqrt{B/\mathrm{OPT}_\mathrm{LP}})$, where $B$ is budget constraint in BwK and $\mathrm{OPT}_{\mathrm{LP}}$ denotes the optimal value of a linear programming relaxation of the BwK problem. For the problem-dependent setting, we develop a quantum algorithm using an inexact quantum linear programming solver. This algorithm achieves a quadratic improvement in terms of the problem-dependent parameters, as well as a polynomial speedup of time complexity on problem's dimensions compared to classical counterparts. Compared to previous works on quantum algorithms for multi-armed bandits, our study is the first to consider bandit models with resource constraints and hence shed light on operations research.
• Abstract（参考訳）: knapsacks (BwK) を用いたバンドは、確率的整数プログラミングとオンライン学習を組み合わせた基本モデルを構成する。 時間的地平線を持つ BwK の古典的アルゴリズムでは、$T$ は、${O}(\sqrt{T})$ の問題非依存後悔境界と${O}(\log T)$ の問題依存的境界を達成する。 本稿では、量子コンピューティングの設定におけるBwKモデルの研究を開始し、報酬とリソース消費の両方を量子オラクルを介してアクセスできるようにする。 我々は、量子BwKアルゴリズムに対して、問題非依存と問題依存の後悔境界の両方を確立する。 問題に依存しない場合、量子的アプローチは古典的後悔を$(1+\sqrt{B/\mathrm{OPT}_\mathrm{LP}})$で表すことができ、B$はBwKにおける予算制約であり、$\mathrm{OPT}_{\mathrm{LP}}$はBwK問題の線形プログラミング緩和の最適値を示す。 問題依存的な設定のために、不正確な量子線形計画解法を用いて量子アルゴリズムを開発する。 このアルゴリズムは、問題に依存したパラメータの2次改善と、古典的なパラメータと比較して問題次元における時間複雑性の多項式スピードアップを達成する。 マルチアームバンディットの量子アルゴリズムに関するこれまでの研究と比較して、資源制約のあるバンディットモデルを初めて検討し、運用研究に光を当てた。

関連論文リスト

• A competitive NISQ and qubit-efficient solver for the LABS problem [0.0]
  パウリ相関。 (PCE)は、近年、変分量子アルゴリズムにおける問題を最適化するための量子ビット効率のアプローチとして導入されている。 我々はPCEベースのフレームワークを拡張し、LABS(Low Autocorrelation Binary Sequences)問題を解決する。
  論文  参考訳（メタデータ） (2025-06-20T18:00:02Z)
• A Quantum Constraint Generation Framework for Binary Linear Programs [0.0]
  量子コンピュータを用いたバイナリ線形プログラミング(BLP)のための新しい手法を提案する。 量子最適化アルゴリズム(ハイブリッドまたは量子専用)は現在、ICPのためのスタンドアロンの解法である。 本研究では,任意の量子最適化アルゴリズムを量子情報古典制約生成フレームワークにラップする。
  論文  参考訳（メタデータ） (2025-03-27T07:24:33Z)
• A quantum-classical hybrid algorithm with Ising model for the learning with errors problem [13.06030390635216]
  本稿では,Ising Model (HAWI) を用いた量子古典ハイブリッドアルゴリズムを提案し,LWE問題に対処する。 我々は、ハミルトンの低エネルギーレベルを同定して解を抽出し、現在のノイズの多い中間スケール量子(NISQ)デバイスの実装に適したものにする。 我々のアルゴリズムは反復であり、その時間複雑性はハミルトンの低エネルギーレベルを見つけるために使われる特定の量子アルゴリズムに依存する。
  論文  参考訳（メタデータ） (2024-08-15T05:11:35Z)
• Sum-of-Squares inspired Quantum Metaheuristic for Polynomial Optimization with the Hadamard Test and Approximate Amplitude Constraints [76.53316706600717]
  最近提案された量子アルゴリズムarXiv:2206.14999は半定値プログラミング(SDP)に基づいている SDPにインスパイアされた量子アルゴリズムを2乗和に一般化する。 この結果から,本アルゴリズムは大きな問題に適応し,最もよく知られた古典学に近似することが示唆された。
  論文  参考訳（メタデータ） (2024-08-14T19:04:13Z)
• Quantum Bayesian Optimization [64.58749619145908]
  本稿では,量子ガウスプロセスアップパー信頼度境界(Q-GP-UCB)アルゴリズムを提案する。 O(polylog T) は古典的設定における Omega(sqrt(T)) の左下限よりもかなり小さい。 線形核を持つQ-GP-UCBは、新しい信頼楕円体解析により、量子線形 UCB アルゴリズムよりも小さな後悔を実現する。
  論文  参考訳（メタデータ） (2023-10-09T03:10:42Z)
• Quantum Worst-Case to Average-Case Reductions for All Linear Problems [66.65497337069792]
  量子アルゴリズムにおける最悪のケースと平均ケースの削減を設計する問題について検討する。 量子アルゴリズムの明示的で効率的な変換は、入力のごく一部でのみ正し、全ての入力で正しくなる。
  論文  参考訳（メタデータ） (2022-12-06T22:01:49Z)
• Unbalanced penalization: A new approach to encode inequality constraints of combinatorial problems for quantum optimization algorithms [42.29248343585333]
  余分なスラック変数を必要としない代替手法を提案する。 我々は,旅行セールスマン問題,ビン包装問題,ナプサック問題に対するアプローチを評価した。 この新しいアプローチは、リソースの少ない不等式制約の問題を解決するために使用できる。
  論文  参考訳（メタデータ） (2022-11-25T06:05:18Z)
• A single $T$-gate makes distribution learning hard [56.045224655472865]
  この研究は、局所量子回路の出力分布の学習可能性に関する広範な評価を提供する。 ハイブリッド量子古典アルゴリズムを含む多種多様な学習アルゴリズムにおいて、深度$d=omega(log(n))$ Clifford回路に関連する生成的モデリング問題さえも困難であることを示す。
  論文  参考訳（メタデータ） (2022-07-07T08:04:15Z)

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

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