論文の概要: Logarithmic-Regret Quantum Learning Algorithms for Zero-Sum Games

• arxiv url: http://arxiv.org/abs/2304.14197v2
• Date: Mon, 30 Sep 2024 15:59:21 GMT
• ステータス: 翻訳完了
• システム内更新日: 2024-10-01 22:00:35.815413
• Title: Logarithmic-Regret Quantum Learning Algorithms for Zero-Sum Games
• Title（参考訳）: ゼロサムゲームのための対数回帰量子学習アルゴリズム
• Authors: Minbo Gao, Zhengfeng Ji, Tongyang Li, Qisheng Wang,
• Abstract要約: ゼロサムゲームを解くための最初のオンライン量子アルゴリズムを提案する。 我々のアルゴリズムは簡潔な記述を伴う古典的な出力を生成する。 我々のアルゴリズムの核心は、ギブスサンプリング問題に対する高速な量子マルチサンプリング手法である。
• 参考スコア（独自算出の注目度）: 10.79781442303645
• License:
• Abstract: We propose the first online quantum algorithm for solving zero-sum games with $\widetilde O(1)$ regret under the game setting. Moreover, our quantum algorithm computes an $\varepsilon$-approximate Nash equilibrium of an $m \times n$ matrix zero-sum game in quantum time $\widetilde O(\sqrt{m+n}/\varepsilon^{2.5})$. Our algorithm uses standard quantum inputs and generates classical outputs with succinct descriptions, facilitating end-to-end applications. Technically, our online quantum algorithm "quantizes" classical algorithms based on the optimistic multiplicative weight update method. At the heart of our algorithm is a fast quantum multi-sampling procedure for the Gibbs sampling problem, which may be of independent interest.
• Abstract（参考訳）: ゲーム設定下では,$\widetilde O(1)$ regret を用いてゼロサムゲームを解くための最初のオンライン量子アルゴリズムを提案する。 さらに、我々の量子アルゴリズムは、量子時間$\widetilde O(\sqrt{m+n}/\varepsilon^{2.5})$における$m \times n$Matrix 0-sumゲームのナッシュ平衡を計算する。 我々のアルゴリズムは、標準的な量子入力を使用し、簡潔な記述で古典的な出力を生成し、エンドツーエンドのアプリケーションを容易にする。 技術的には、我々のオンライン量子アルゴリズムは楽観的な乗算重み更新法に基づいて古典的アルゴリズムを「量子化」する。 我々のアルゴリズムの核心は、ギブスサンプリング問題に対する高速な量子マルチサンプリング手順であり、これは独立した関心事であるかもしれない。

関連論文リスト

• Quantum multi-row iteration algorithm for linear systems with non-square coefficient matrices [7.174256268278207]
  古典的マルチロー反復法に着想を得た量子アルゴリズムを提案する。 本アルゴリズムは,不整合系の解法に適した係数行列の要求を小さくする。
  論文  参考訳（メタデータ） (2024-09-06T03:32:02Z)
• Quantum algorithms for Hopcroft's problem [45.45456673484445]
  計算幾何学の基本的な問題であるホップクロフト問題に対する量子アルゴリズムについて検討する。 この問題の古典的な複雑さはよく研究されており、最もよく知られているアルゴリズムは$O(n4/3)の時間で動作する。 我々の結果は、時間複雑性が$widetilde O(n5/6)$の2つの異なる量子アルゴリズムである。
  論文  参考訳（メタデータ） (2024-05-02T10:29:06Z)
• Generalized quantum Arimoto-Blahut algorithm and its application to quantum information bottleneck [55.22418739014892]
  量子アリーモト・ブラフトアルゴリズムをRamakrishnanらにより一般化する。 3つの量子系を持つ量子情報ボトルネックに対して,我々のアルゴリズムを適用した。 数値解析により,我々のアルゴリズムはアルゴリズムよりも優れていることが示された。
  論文  参考訳（メタデータ） (2023-11-19T00:06:11Z)
• A Quadratic Speedup in Finding Nash Equilibria of Quantum Zero-Sum Games [102.46640028830441]
  最適行列乗算重み更新(OMMWU)アルゴリズムを導入し,平均収束複雑性を$mathcalO(d/epsilon)$ to $epsilon$-Nash equilibriaとする。 この二次的なスピードアップは、量子ゼロサムゲームにおける$epsilon$-Nash平衡の計算のための新しいベンチマークを定めている。
  論文  参考訳（メタデータ） (2023-11-17T20:38:38Z)
• Quantum Worst-Case to Average-Case Reductions for All Linear Problems [66.65497337069792]
  量子アルゴリズムにおける最悪のケースと平均ケースの削減を設計する問題について検討する。 量子アルゴリズムの明示的で効率的な変換は、入力のごく一部でのみ正し、全ての入力で正しくなる。
  論文  参考訳（メタデータ） (2022-12-06T22:01:49Z)
• Predicting Gibbs-State Expectation Values with Pure Thermal Shadows [1.4050836886292868]
  本稿では,任意のギブス状態の線形関数を$M$で予測できる量子アルゴリズムを提案する。 このアルゴリズムは、8ビットの完全連結量子ボルツマンマシンをトレーニングするためのサブルーチンとしてうまく利用できることを示す。
  論文  参考訳（メタデータ） (2022-06-10T18:00:08Z)
• Entanglement and coherence in Bernstein-Vazirani algorithm [58.720142291102135]
  Bernstein-Vaziraniアルゴリズムは、オラクルに符号化されたビット文字列を決定できる。 我々はベルンシュタイン・ヴァジラニアルゴリズムの量子資源を詳細に分析する。 絡み合いがない場合、初期状態における量子コヒーレンス量とアルゴリズムの性能が直接関係していることが示される。
  論文  参考訳（メタデータ） (2022-05-26T20:32:36Z)
• Quantum Algorithm for Fidelity Estimation [8.270684567157987]
  2つの未知の混合量子状態 $rho$ と $sigma$ に対して、それらの忠実度 $F(rho,sigma)$ は基本的な問題である。 我々は、この問題を$namepoly(log (N), r, 1/varepsilon)$ timeで解く量子アルゴリズムを提案する。
  論文  参考訳（メタデータ） (2021-03-16T13:57:01Z)
• Quantum algorithms for escaping from saddle points [7.191453718557392]
  本研究では,サドル点からの脱出を保証できる保証付き量子アルゴリズムについて検討する。 我々の主な貢献は、勾配降下法における古典的摂動を置き換えるという考え方である。 また、Jordanによる量子勾配計算アルゴリズムの使い方を示す。
  論文  参考訳（メタデータ） (2020-07-20T16:42:53Z)
• Quantum Gram-Schmidt Processes and Their Application to Efficient State Read-out for Quantum Algorithms [87.04438831673063]
  本稿では、生成した状態の古典的ベクトル形式を生成する効率的な読み出しプロトコルを提案する。 我々のプロトコルは、出力状態が入力行列の行空間にある場合に適合する。 我々の技術ツールの1つは、Gram-Schmidt正則手順を実行するための効率的な量子アルゴリズムである。
  論文  参考訳（メタデータ） (2020-04-14T11:05:26Z)

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

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