論文の概要: Quantum Potential Games, Replicator Dynamics, and the Separability
Problem
- arxiv url: http://arxiv.org/abs/2302.04789v2
- Date: Mon, 26 Jun 2023 06:42:28 GMT
- ステータス: 処理完了
- システム内更新日: 2023-06-27 23:37:30.605195
- Title: Quantum Potential Games, Replicator Dynamics, and the Separability
Problem
- Title（参考訳）: 量子ポテンシャルゲーム、リプリケータダイナミクス、および分離性問題
- Authors: Wayne Lin, Georgios Piliouras, Ryann Sim, Antonios Varvitsiotis
- Abstract要約: ゲーミフィケーション(Gamification)は、ゲームのようなシナリオに変換することで最適化問題を解決する新しいアプローチを提供する機械学習分野における新たなトレンドである。
我々はこのパラダイムシフトを用いて、分離可能な量子状態の集合に対する線形最適化を含む量子情報理論の基本的な問題であるBest Separable State (BSS)問題に取り組む。
BSSインスタンスのKKT(一階定常点)と対応する量子CIGのナッシュ平衡の等価性を確立することにより、最適化とゲーム理論のギャップを埋める。
- 参考スコア（独自算出の注目度）: 29.848128619774133
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: Gamification is an emerging trend in the field of machine learning that
presents a novel approach to solving optimization problems by transforming them
into game-like scenarios. This paradigm shift allows for the development of
robust, easily implementable, and parallelizable algorithms for hard
optimization problems. In our work, we use gamification to tackle the Best
Separable State (BSS) problem, a fundamental problem in quantum information
theory that involves linear optimization over the set of separable quantum
states. To achieve this we introduce and study quantum analogues of
common-interest games (CIGs) and potential games where players have density
matrices as strategies and their interests are perfectly aligned. We bridge the
gap between optimization and game theory by establishing the equivalence
between KKT (first-order stationary) points of a BSS instance and the Nash
equilibria of its corresponding quantum CIG. Taking the perspective of learning
in games, we introduce non-commutative extensions of the continuous-time
replicator dynamics and the discrete-time Baum-Eagon/linear multiplicative
weights update for learning in quantum CIGs, which also serve as decentralized
algorithms for the BSS problem. We show that the common utility/objective value
of a BSS instance is strictly increasing along trajectories of our algorithms,
and finally corroborate our theoretical findings through extensive experiments.
- Abstract（参考訳）: ゲーミフィケーション(Gamification)は、ゲームのようなシナリオに変換することで最適化問題を解決する新しいアプローチを提供する機械学習分野における新たなトレンドである。
このパラダイムシフトにより、ハード最適化問題に対する堅牢で実装が容易で並列化可能なアルゴリズムの開発が可能になる。
本研究では,分割可能な量子状態の集合に対する線形最適化を含む量子情報理論の基本問題であるBest Separable State (BSS)問題に,ゲーミフィケーションを用いて取り組む。
これを実現するため、我々は共通興味ゲーム(cig)と、プレイヤーが戦略として密度行列を持ち、その興味が完全に一致した潜在的なゲームの量子アナログを導入し、研究する。
BSSインスタンスのKKT(一階定常点)と対応する量子CIGのナッシュ平衡の等価性を確立することにより、最適化とゲーム理論のギャップを埋める。
ゲームにおける学習の視点から,連続時間レプリケータダイナミクスの非可換拡張と,bss問題の分散アルゴリズムとしても機能する量子サイグスにおける学習のための離散時間baum-eagon/linear multiplicative weights updateを導入する。
bssインスタンスの共通のユーティリティ/目的値が、我々のアルゴリズムの軌跡に沿って厳密に増加しており、最終的に広範な実験を通じて理論的な結果と一致していることを示す。
関連論文リスト
- Entanglement-assisted variational algorithm for discrete optimization problems [0.0]
離散最適化問題は、しばしば正確に難解であり、近似メソッドの使用を必要とする。
古典物理学に触発されたヒューリスティックスは、長い間この領域において中心的な役割を果たしてきた。
量子アニールは、アナログおよびデジタル量子デバイスの両方で実現されたハードウェア実装によって、有望な代替手段として登場した。
論文 参考訳（メタデータ） (2025-01-15T19:00:10Z) - Quantum Annealing and Tensor Networks: a Powerful Combination to Solve Optimization Problems [0.0]
この論文の目的は、量子デバイスとテンソルネットワークアルゴリズムを比較することではない。
これらの技術間のシナジーの可能性を探究し、2つのフラッグシップアルゴリズムが将来的にどのように協力するかに焦点を当てる。
本論は, 有限オートマトンを用いたこの問題に対するアプローチを概説し, ケーススタディのMPO構築に応用する。
論文 参考訳（メタデータ） (2024-12-07T09:20:20Z) - Efficient Learning for Linear Properties of Bounded-Gate Quantum Circuits [63.733312560668274]
d可変RZゲートとG-dクリフォードゲートを含む量子回路を与えられた場合、学習者は純粋に古典的な推論を行い、その線形特性を効率的に予測できるだろうか?
我々は、d で線形にスケーリングするサンプルの複雑さが、小さな予測誤差を達成するのに十分であり、対応する計算の複雑さは d で指数関数的にスケールすることを証明する。
我々は,予測誤差と計算複雑性をトレードオフできるカーネルベースの学習モデルを考案し,多くの実践的な環境で指数関数からスケーリングへ移行した。
論文 参考訳（メタデータ） (2024-08-22T08:21:28Z) - Quantum Subroutine for Variance Estimation: Algorithmic Design and Applications [80.04533958880862]
量子コンピューティングは、アルゴリズムを設計する新しい方法の基礎となる。
どの場の量子スピードアップが達成できるかという新たな課題が生じる。
量子サブルーチンの設計は、従来のサブルーチンよりも効率的で、新しい強力な量子アルゴリズムに固い柱を向ける。
論文 参考訳（メタデータ） (2024-02-26T09:32:07Z) - Challenges and Opportunities in Quantum Optimization [14.7608536260003]
量子コンピュータの最近の進歩は、ブラトフォース古典シミュレーションを超えるスケールで問題を解決する能力を示している。
計算機科学や物理学全般において、主要な最適化問題に対するアプローチは様々である。
論文 参考訳（メタデータ） (2023-12-04T19:00:44Z) - 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) - No-Regret Learning and Equilibrium Computation in Quantum Games [29.768913836823973]
非回帰アルゴリズムは時間平均における分離可能な量子ナッシュ平衡に収束することを示す。
一般的なマルチプレイヤー量子ゲームの場合、我々の研究は、分離可能な量子粗相関平衡の新たな解の概念へと導かれる。
論文 参考訳（メタデータ） (2023-10-12T16:29:56Z) - Exploring the topological sector optimization on quantum computers [5.458469081464264]
トポロジカルセクター最適化(TSO)問題は、量子多体物理学コミュニティにおいて特に関心を集めている。
TSO問題の最適化の難しさは、ギャップレス性に限らず、トポロジカル性にも起因していることを示す。
TSO問題を解決するために、量子コンピュータ上で実現可能な量子想像時間進化(QITE)を利用する。
論文 参考訳（メタデータ） (2023-10-06T14:51:07Z) - Quantum Annealing for Single Image Super-Resolution [86.69338893753886]
単一画像超解像(SISR)問題を解くために,量子コンピューティングに基づくアルゴリズムを提案する。
提案したAQCアルゴリズムは、SISRの精度を維持しつつ、古典的なアナログよりも向上したスピードアップを実現する。
論文 参考訳（メタデータ） (2023-04-18T11:57:15Z) - Quantum algorithms for quantum dynamics: A performance study on the
spin-boson model [68.8204255655161]
量子力学シミュレーションのための量子アルゴリズムは、伝統的に時間進化作用素のトロッター近似の実装に基づいている。
変分量子アルゴリズムは欠かせない代替手段となり、現在のハードウェア上での小規模なシミュレーションを可能にしている。
量子ゲートコストが明らかに削減されているにもかかわらず、現在の実装における変分法は量子的優位性をもたらすことはありそうにない。
論文 参考訳（メタデータ） (2021-08-09T18:00:05Z) - Quantum Geometric Machine Learning for Quantum Circuits and Control [78.50747042819503]
我々は、量子幾何学的制御問題に対するディープラーニングの適用をレビューし、拡張する。
量子回路合成問題における時間-最適制御の強化について述べる。
我々の研究結果は、時間-最適制御問題に対する機械学習と幾何学的手法を組み合わせた量子制御と量子情報理論の研究者にとって興味深いものである。
論文 参考訳（メタデータ） (2020-06-19T19:12:14Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。