論文の概要: A Quadratic Speedup in Finding Nash Equilibria of Quantum Zero-Sum Games
- arxiv url: http://arxiv.org/abs/2311.10859v1
- Date: Fri, 17 Nov 2023 20:38:38 GMT
- ステータス: 処理完了
- システム内更新日: 2023-11-22 14:01:09.322681
- Title: A Quadratic Speedup in Finding Nash Equilibria of Quantum Zero-Sum Games
- Title（参考訳）: 量子ゼロサムゲームにおけるナッシュ平衡の擬似高速化
- Authors: Francisca Vasconcelos, Emmanouil-Vasileios Vlatakis-Gkaragkounis,
Panayotis Mertikopoulos, Georgios Piliouras, Michael I. Jordan
- Abstract要約: 最適行列乗算重み更新(OMMWU)アルゴリズムを導入し,平均収束複雑性を$mathcalO(d/epsilon)$ to $epsilon$-Nash equilibriaとする。
この二次的なスピードアップは、量子ゼロサムゲームにおける$epsilon$-Nash平衡の計算のための新しいベンチマークを定めている。
- 参考スコア（独自算出の注目度）: 102.46640028830441
- License: http://creativecommons.org/licenses/by/4.0/
- Abstract: Recent developments in domains such as non-local games, quantum interactive
proofs, and quantum generative adversarial networks have renewed interest in
quantum game theory and, specifically, quantum zero-sum games. Central to
classical game theory is the efficient algorithmic computation of Nash
equilibria, which represent optimal strategies for both players. In 2008, Jain
and Watrous proposed the first classical algorithm for computing equilibria in
quantum zero-sum games using the Matrix Multiplicative Weight Updates (MMWU)
method to achieve a convergence rate of $\mathcal{O}(d/\epsilon^2)$ iterations
to $\epsilon$-Nash equilibria in the $4^d$-dimensional spectraplex. In this
work, we propose a hierarchy of quantum optimization algorithms that generalize
MMWU via an extra-gradient mechanism. Notably, within this proposed hierarchy,
we introduce the Optimistic Matrix Multiplicative Weights Update (OMMWU)
algorithm and establish its average-iterate convergence complexity as
$\mathcal{O}(d/\epsilon)$ iterations to $\epsilon$-Nash equilibria. This
quadratic speed-up relative to Jain and Watrous' original algorithm sets a new
benchmark for computing $\epsilon$-Nash equilibria in quantum zero-sum games.
- Abstract（参考訳）: 非局所ゲーム、量子インタラクティブ証明、量子生成敵ネットワークなどの領域における最近の発展は、量子ゲーム理論、特に量子ゼロサムゲームに新たな関心を抱いている。
古典的なゲーム理論の中心はナッシュ平衡の効率的なアルゴリズム計算であり、両者の最適戦略を表している。
2008年、Jain と Watrous は Matrix Multiplicative Weight Updates (MMWU) 法を用いて量子ゼロサムゲームにおける平衡を計算するための最初の古典的アルゴリズムを提案し、$$\mathcal{O}(d/\epsilon^2)$ iterations to $\epsilon$-Nash equilibria in the four^d$-dimensional spectraplex とした。
本研究では,超勾配機構を用いてmmwuを一般化する量子最適化アルゴリズムの階層を提案する。
この階層内では、最適化行列乗算重み更新(OMMWU)アルゴリズムを導入し、平均収束複雑性を$\mathcal{O}(d/\epsilon)$ iterations to $\epsilon$-Nash equilibriaとして確立する。
このジャイナとワトラスのアルゴリズムに対する二次的なスピードアップは、量子ゼロサムゲームにおける$\epsilon$-Nash平衡の計算のための新しいベンチマークを設定する。
関連論文リスト
- Quantum multi-row iteration algorithm for linear systems with non-square coefficient matrices [7.174256268278207]
古典的マルチロー反復法に着想を得た量子アルゴリズムを提案する。
本アルゴリズムは,不整合系の解法に適した係数行列の要求を小さくする。
論文 参考訳（メタデータ） (2024-09-06T03:32:02Z) - Towards large-scale quantum optimization solvers with few qubits [59.63282173947468]
我々は、$m=mathcalO(nk)$バイナリ変数を$n$ qubitsだけを使って最適化するために、$k>1$で可変量子ソルバを導入する。
我々は,特定の量子ビット効率の符号化が,バレン高原の超ポリノミウム緩和を内蔵特徴としてもたらすことを解析的に証明した。
論文 参考訳（メタデータ） (2024-01-17T18:59:38Z) - Payoff-based learning with matrix multiplicative weights in quantum
games [35.111876815522116]
量子ゲーム(および半定値ゲーム)における学習の問題を、スカラーでペイオフに基づくフィードバックを用いて研究する。
本稿では,情報フレームワークに合わせた最小情報行列乗法(3MW)を提案する。
決定論的ペイオフフィードバックを持つ3MW法は,量子ミニマックスゲームにおけるバニラ,フル情報MMWアルゴリズムの収束率を保っていることを示す。
論文 参考訳（メタデータ） (2023-11-04T14:56:17Z) - Alleviating the quantum Big-$M$ problem [0.237499051649312]
古典的には "Big-$M$" 問題として知られており、物理的エネルギースケールに影響を与える。
我々は、量子ビッグ-M$問題を体系的に包含し、最適の$M$を見つけるのにNPハードネスを明らかにする。
本稿では,SDP緩和に基づく実用的な翻訳アルゴリズムを提案する。
論文 参考訳（メタデータ） (2023-07-19T18:00:05Z) - Logarithmic-Regret Quantum Learning Algorithms for Zero-Sum Games [10.79781442303645]
ゼロサムゲームを解くための最初のオンライン量子アルゴリズムを提案する。
我々のアルゴリズムは簡潔な記述を伴う古典的な出力を生成する。
我々のアルゴリズムの核心は、ギブスサンプリング問題に対する高速な量子マルチサンプリング手法である。
論文 参考訳（メタデータ） (2023-04-27T14:02:54Z) - 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) - Policy Optimization for Markov Games: Unified Framework and Faster
Convergence [81.3266426402464]
このアルゴリズムのステートワイド平均ポリシはゲームの近似ナッシュ平衡(NE)に収束することを示す。
このアルゴリズムをマルチプレイヤー一般のMarkov Gamesに拡張し、CCE(Correlated Equilibria)への$mathcalwidetildeO(T-1/2)$収束率を示す。
論文 参考訳（メタデータ） (2022-06-06T14:23:13Z) - Improving Quantum Simulation Efficiency of Final State Radiation with
Dynamic Quantum Circuits [1.3375143521862154]
我々は、QPSアルゴリズムのスケーリングを改善するために、動的量子コンピューティングと呼ばれる新しい量子ハードウェア機能を活用している。
量子パートンシャワー回路を改良し、古典情報に基づく中周期キュービット計測、リセット、量子演算を取り入れた。
論文 参考訳（メタデータ） (2022-03-18T15:31:19Z) - 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)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。