論文の概要: 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 Algorithms for the Pathwise Lasso [1.8058773918890538]
  古典的LARS(Least Angle Regression)パスワイズアルゴリズムに基づく新しい量子高次元線形回帰アルゴリズムを提案する。 我々の量子アルゴリズムは、ペナルティ項が変化するにつれて、完全な正規化パスを提供するが、特定の条件下では、イテレーション毎に2次的に高速である。 我々は、KKT条件の近似バージョンと双対性ギャップにより、LARSアルゴリズムがエラーに対して堅牢であることを証明した。
  論文  参考訳（メタデータ） (2023-12-21T18:57:54Z)
• 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)
• Efficient quantum linear solver algorithm with detailed running costs [0.0]
  量子信号処理に基づくフィルタリング手法を用いて,アイデアダイアバティックな量子コンピューティングを組み合わせた量子線形解法アルゴリズムを提案する。 我々のプロトコルは、初期実装において、最先端技術に対する量子線形解決器のコストを桁違いに削減する。
  論文  参考訳（メタデータ） (2023-05-19T00:07:32Z)
• Quantum Clustering with k-Means: a Hybrid Approach [117.4705494502186]
  我々は3つのハイブリッド量子k-Meansアルゴリズムを設計、実装、評価する。 我々は距離の計算を高速化するために量子現象を利用する。 我々は、我々のハイブリッド量子k-平均アルゴリズムが古典的バージョンよりも効率的であることを示す。
  論文  参考訳（メタデータ） (2022-12-13T16:04:16Z)
• Quantum Worst-Case to Average-Case Reductions for All Linear Problems [66.65497337069792]
  量子アルゴリズムにおける最悪のケースと平均ケースの削減を設計する問題について検討する。 量子アルゴリズムの明示的で効率的な変換は、入力のごく一部でのみ正し、全ての入力で正しくなる。
  論文  参考訳（メタデータ） (2022-12-06T22:01:49Z)
• 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)

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

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