論文の概要: Quantum-over-classical Advantage in Solving Multiplayer Games

• arxiv url: http://arxiv.org/abs/2006.06965v1
• Date: Fri, 12 Jun 2020 06:36:07 GMT
• ステータス: 処理完了
• システム内更新日: 2023-05-15 22:33:37.832591
• Title: Quantum-over-classical Advantage in Solving Multiplayer Games
• Title（参考訳）: マルチプレイヤーゲームにおける量子オーバー古典的アドバンテージ
• Authors: Dmitry Kravchenko, Kamil Khadiev, Danil Serov and Ruslan Kapralov
• Abstract要約: サブトラクションゲームはワンヒープニムゲームと呼ばれることもある。 量子ゲーム理論において、サブトラクションゲームの部分集合は、ゼロサムゲームの最初の明示的に定義されたクラスとなった。 サブトラクションゲームのより狭い部分集合については、すべての決定論的アルゴリズムを超える正確な量子サブ線形アルゴリズムが知られている。
• 参考スコア（独自算出の注目度）: 0.0
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: We study the applicability of quantum algorithms in computational game theory and generalize some results related to Subtraction games, which are sometimes referred to as one-heap Nim games. In quantum game theory, a subset of Subtraction games became the first explicitly defined class of zero-sum combinatorial games with provable separation between quantum and classical complexity of solving them. For a narrower subset of Subtraction games, an exact quantum sublinear algorithm is known that surpasses all deterministic algorithms for finding solutions with probability $1$. Typically, both Nim and Subtraction games are defined for only two players. We extend some known results to games for three or more players, while maintaining the same classical and quantum complexities: $\Theta\left(n^2\right)$ and $\tilde{O}\left(n^{1.5}\right)$ respectively.
• Abstract（参考訳）: 計算ゲーム理論における量子アルゴリズムの適用性について検討し、一重ニムゲームと呼ばれるサブトラクションゲームに関連するいくつかの結果を一般化する。 量子ゲーム理論において、減算ゲームの部分集合は、それらの解の量子複雑性と古典的複雑性の間で証明可能な分離可能なゼロサムコンビネートゲームの最初の明示的に定義されたクラスとなった。 サブトラクションゲームのより狭い部分集合については、確率1ドルで解を見つけるための決定論的アルゴリズムを全て超える正確な量子サブ線形アルゴリズムが知られている。 通常、ニムゲームとサブトラクションゲームは2つのプレイヤーで定義されている。 既知の結果を3人以上のプレイヤーのゲームに拡張し、それぞれ$\Theta\left(n^2\right)$と$\tilde{O}\left(n^{1.5}\right)$という古典的および量子的複雑さを維持している。

関連論文リスト

• A bound on the quantum value of all compiled nonlocal games [49.32403970784162]
  暗号コンパイラは、任意の非ローカルゲームを単一の計算バウンド証明器で対話的プロトコルに変換する。 我々は、コンパイルされた2人プレイヤの非ローカルゲームに対して量子音響結果を確立する。
  論文  参考訳（メタデータ） (2024-08-13T08:11:56Z)
• Imperfect-Recall Games: Equilibrium Concepts and Their Complexity [74.01381499760288]
  エージェントが以前保持していた情報を忘れたとき、不完全なリコールの下で最適な意思決定を行う。 不完全なリコールを伴う広範囲形式のゲームフレームワークにおいて、マルチプレイヤー設定における平衡を求める際の計算複雑性を解析する。
  論文  参考訳（メタデータ） (2024-06-23T00:27:28Z)
• Repeated quantum game as a stochastic game: Effects of the shadow of the future and entanglement [0.0]
  本稿では,新しい繰り返しゲームプロトコルを用いて構築された量子ゲームについて,体系的な研究を行う。 2つの純粋な戦略の相違が、ディスカウント要因に大きく依存していることがわかりました。 量子ゲーム設定では、高い割引係数に対するティット・フォー・テイト戦略により、常に欠陥戦略を破ることができる。
  論文  参考訳（メタデータ） (2023-12-08T15:54:51Z)
• 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)
• Photonic implementation of the quantum Morra game [69.65384453064829]
  本研究は,古典ゲームを特殊なケースとして含めることにより,従来の研究を基盤とした2プレーヤ量子モラゲームの忠実な翻訳について研究する。 本稿では、アリスが古典ゲームのバランスを崩し、勝利の優位性を持つ量子状態におけるゲームの自然な変形を提案する。 量子情報と通信の研究における量子モラゲームの可能性について論じる。
  論文  参考訳（メタデータ） (2023-11-14T19:41:50Z)
• Logarithmic-Regret Quantum Learning Algorithms for Zero-Sum Games [10.79781442303645]
  ゼロサムゲームを解くための最初のオンライン量子アルゴリズムを提案する。 我々のアルゴリズムは簡潔な記述を伴う古典的な出力を生成する。 我々のアルゴリズムの核心は、ギブスサンプリング問題に対する高速な量子マルチサンプリング手法である。
  論文  参考訳（メタデータ） (2023-04-27T14:02:54Z)
• Learning Correlated Equilibria in Mean-Field Games [62.14589406821103]
  我々は平均場相関と粗相関平衡の概念を発展させる。 ゲームの構造に関する仮定を必要とせず,効率よくゲーム内で学習できることが示される。
  論文  参考訳（メタデータ） (2022-08-22T08:31:46Z)
• Winning Mastermind Overwhelmingly on Quantum Computers [0.2320417845168326]
  我々はMastermindをプレイするための量子戦略を体系的に研究している。 非適応性および適応性の両方の設定で最適量子アルゴリズムを構築する。 一般的な文字列学習問題に対して,量子アルゴリズムを設計するためのフレームワークを開発する。
  論文  参考訳（メタデータ） (2022-07-19T16:02:28Z)
• On the relation between completely bounded and $(1,cb)$-summing maps with applications to quantum XOR games [65.51757376525798]
  一般作用素空間から C$*$-代数の双対への線型写像が与えられたとき、その完全有界ノルムは、その$(''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''
  論文  参考訳（メタデータ） (2021-12-09T21:06:52Z)
• Infinitely Repeated Quantum Games and Strategic Efficiency [0.0]
  繰り返し量子ゲーム理論は、量子戦略を選択するプレイヤー間の長期の関係に対処する。 従来の量子ゲーム理論では、単一ラウンド量子ゲームや、ほとんどの有限繰り返しゲームが広く研究されている。
  論文  参考訳（メタデータ） (2020-05-12T07:39:42Z)

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

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