論文の概要: Calculating Nash Equilibrium on Quantum Annealers
- arxiv url: http://arxiv.org/abs/2112.12583v3
- Date: Fri, 29 Apr 2022 20:42:31 GMT
- ステータス: 処理完了
- システム内更新日: 2023-03-04 00:39:34.815274
- Title: Calculating Nash Equilibrium on Quantum Annealers
- Title（参考訳）: 量子アニール上のナッシュ平衡の計算
- Authors: Olga Okrut, Keith Cannon, Kareem H. El-Safty, Nada Elsokkary, Faisal
Shah Khan
- Abstract要約: 2人プレイヤ非協調ゲームにおいてナッシュ均衡を求める問題は、制約付き2倍の2次最適化問題である。
この問題は1964年にマンガリアンとストーンによって1つの制約付き二次最適化として定式化された。
ナッシュ平衡の二次関数の定式化にペナルティ項を加えることで、量子アニール上で実行可能な2進最適化問題が得られることを示す。
- 参考スコア（独自算出の注目度）: 0.5599792629509227
- License: http://creativecommons.org/licenses/by-nc-nd/4.0/
- Abstract: Adiabatic quantum computing is implemented on specialized hardware using the
heuristics of the quantum annealing algorithm. This setup requires the
addressed problems to be formatted as discrete quadratic functions without
constraints and the variables to take binary values only. The problem of
finding Nash equilibrium in two-player, non-cooperative games is a two-fold
quadratic optimization problem with constraints. This problem was formatted as
a single, constrained quadratic optimization in 1964 by Mangasarian and Stone.
Here, we show that adding penalty terms to the quadratic function formulation
of Nash equilibrium gives a quadratic unconstrained binary optimization (QUBO)
formulation of this problem that can be executed on quantum annealers. Three
examples are discussed to highlight the success of the formulation, and an
overall, time-to-solution (hardware + software processing) speed up of seven to
ten times is reported on quantum annealers developed by D-Wave System.
- Abstract（参考訳）: 断熱量子コンピューティングは、量子アニーリングアルゴリズムのヒューリスティックスを用いて、特殊なハードウェア上に実装されている。
このセットアップでは、問題は制約のない離散二次関数としてフォーマットされ、変数はバイナリ値のみを取る必要がある。
2人のプレイヤーで非協力的なゲームでナッシュ均衡を見つける問題は、制約付き2次元最適化問題である。
この問題は1964年にマンガサリアンとストーンによって1つの制約付き二次最適化として形式化された。
ここでは、ナッシュ平衡の二次関数の定式化にペナルティ項を加えることで、量子アンニール上で実行できるこの問題の2次非制約バイナリ最適化(QUBO)が得られることを示す。
定式化の成功を強調するために3つの例が議論され、d-waveシステムによって開発された量子アニーラー上で、7倍から10倍の時間対解速度(ハードウェア+ソフトウェア処理)が報告されている。
関連論文リスト
- Beyond QUBO and HOBO formulations, solving the Travelling Salesman Problem on a quantum boson sampler [0.0]
量子デバイスからの全ての出力が有効な経路にマッピングされるため、設計上、ペナルティ項は存在しない。
ボソンサンプルを用いて研究を行ったが、この新しい定式化は他の量子デバイスと関係があると信じている。
論文 参考訳（メタデータ） (2024-06-20T12:25:00Z) - Towards large-scale quantum optimization solvers with few qubits [59.63282173947468]
我々は、$m=mathcalO(nk)$バイナリ変数を$n$ qubitsだけを使って最適化するために、$k>1$で可変量子ソルバを導入する。
我々は,特定の量子ビット効率の符号化が,バレン高原の超ポリノミウム緩和を内蔵特徴としてもたらすことを解析的に証明した。
論文 参考訳（メタデータ） (2024-01-17T18:59:38Z) - 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) - The Role of Entanglement in Quantum-Relaxation Based Optimization
Algorithms [4.00916638804083]
量子ランダムアクセスコード(QRAC)は、バイナリ最適化の複数の変数を1量子ビットでエンコードする。
この結果から,QRAOは量子コンピュータに制限された二項最適化問題の解決可能なインスタンスをスケールできるだけでなく,量子絡み合いの恩恵を受けることが示唆された。
論文 参考訳（メタデータ） (2023-02-01T13:24:51Z) - Quantum Worst-Case to Average-Case Reductions for All Linear Problems [66.65497337069792]
量子アルゴリズムにおける最悪のケースと平均ケースの削減を設計する問題について検討する。
量子アルゴリズムの明示的で効率的な変換は、入力のごく一部でのみ正し、全ての入力で正しくなる。
論文 参考訳（メタデータ） (2022-12-06T22:01:49Z) - Quantum communication complexity of linear regression [0.05076419064097732]
量子コンピュータは、いくつかの基本的な線形代数問題に対する通信の観点から、証明可能かつ指数関数的なスピードアップを持つことを示す。
本稿では,量子特異値変換のための効率的な量子プロトコルを提案する。
論文 参考訳（メタデータ） (2022-10-04T13:27:01Z) - Q-FW: A Hybrid Classical-Quantum Frank-Wolfe for Quadratic Binary
Optimization [44.96576908957141]
本稿では,量子コンピュータ上での2次線形反復問題を解くために,フランク・ウルフアルゴリズム(Q-FW)に基づく古典量子ハイブリッドフレームワークを提案する。
論文 参考訳（メタデータ） (2022-03-23T18:00:03Z) - Adiabatic Quantum Graph Matching with Permutation Matrix Constraints [75.88678895180189]
3次元形状と画像のマッチング問題は、NPハードな置換行列制約を持つ二次代入問題(QAP)としてしばしば定式化される。
本稿では,量子ハードウェア上での効率的な実行に適した制約のない問題として,いくつかのQAPの再構成を提案する。
提案アルゴリズムは、将来の量子コンピューティングアーキテクチャにおいて、より高次元にスケールする可能性がある。
論文 参考訳（メタデータ） (2021-07-08T17:59:55Z) - Quantum Permutation Synchronization [88.4588059792167]
本稿では,コンピュータビジョンの文脈における量子ビジョン問題を解決する量子アルゴリズムQuantumSyncを提案する。
本稿では、QUBO 問題に置換制約を挿入し、アバスティック量子 DWave コンピュータの電流生成に関する制約付き QUBO 問題を解決する方法を示す。
論文 参考訳（メタデータ） (2021-01-19T17:51:02Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。