論文の概要: Breaking $1/ε$ Barrier in Quantum Zero-Sum Games: Generalizing Metric Subregularity for Spectraplexes

• arxiv url: http://arxiv.org/abs/2509.21570v1
• Date: Thu, 25 Sep 2025 20:51:13 GMT
• ステータス: 翻訳完了
• システム内更新日: 2025-09-29 20:57:54.004719
• Title: Breaking $1/ε$ Barrier in Quantum Zero-Sum Games: Generalizing Metric Subregularity for Spectraplexes
• Title（参考訳）: 量子ゼロサムゲームにおける1/ε$バリアの破れ:スペクトルの計量部分規則性を一般化する
• Authors: Yiheng Su, Emmanouil-Vasileios Vlatakis-Gkaragkounis, Pucheng Xiong,
• Abstract要約: 我々は、$textitNesterov の反復滑らか化の行列変種が、量子零サムゲームにおいて線形速度で終点収束を達成することを証明した。 副産物として、厳密な正の半定値プログラムの並列近似のための古典的ジャイナ・ワトラス [arXiv:0808.2775] 法を指数関数的に高速化する。
• 参考スコア（独自算出の注目度）: 2.7340036787711646
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: Long studied as a toy model, quantum zero-sum games have recently resurfaced as a canonical playground for modern areas such as non-local games, quantum interactive proofs, and quantum machine learning. In this simple yet fundamental setting, two competing quantum players send iteratively mixed quantum states to a referee, who performs a joint measurement to determine their payoffs. In 2025, Vasconcelos et al. [arXiv:2311.10859] connected quantum communication channels with a hierarchy of quantum optimization algorithms that generalize Matrix Multiplicative Weights Update ($\texttt{MMWU}$) through extra-gradient mechanisms, establishing an average-iterate convergence rate of $\mathcal{O}(1/\epsilon)$ iterations to $\epsilon$-Nash equilibria. While a long line of work has shown that bilinear games over polyhedral domains admit gradient methods with linear last-iterate convergence rates of $\mathcal{O}(\log(1/\epsilon))$, it has been conjectured that a fundamental performance gap must persist between quantum feasible sets (spectraplexes) and classical polyhedral sets (simplices). We resolve this conjecture in the negative. We prove that matrix variants of $\textit{Nesterov's iterative smoothing}$ ($\texttt{IterSmooth}$) and $\textit{Optimistic Gradient Descent-Ascent}$ ($\texttt{OGDA}$) achieve last-iterate convergence at a linear rate in quantum zero-sum games, thereby matching the classical polyhedral case. Our analysis relies on a new generalization of error bounds in semidefinite programming geometry, establishing that (SP-MS) holds for monotone operators over spectrahedra, despite their uncountably many extreme points. Finally, as a byproduct, we obtain an exponential speed-up over the classical Jain-Watrous [arXiv:0808.2775] method for parallel approximation of strictly positive semidefinite programs.
• Abstract（参考訳）: 長い間、玩具モデルとして研究されてきた量子ゼロサムゲームは、最近、非局所ゲーム、量子インタラクティブ証明、量子機械学習などの現代領域の標準グラウンドとして再浮上した。 この単純だが基本的な設定では、2人の競合する量子プレーヤーが反復的に混合された量子状態を審判に送信する。 2025年、Vasconcelos et al [arXiv:2311.10859] は Matrix Multiplicative Weights Update (\texttt{MMWU}$) を指数関数的に一般化する量子最適化アルゴリズムの階層と接続し、平均収束速度を $\mathcal{O}(1/\epsilon)$ $\epsilon$-Nash equilibria に設定した。 長い研究の行は、多面体領域上の双線型ゲームは、線形終点収束率$\mathcal{O}(\log(1/\epsilon))$の勾配法を許容することを示しているが、基本的なパフォーマンスギャップは量子可能集合(スペクトル)と古典的多面体集合(単純集合)の間に持続しなければならないと推測されている。 我々はこの予想を否定的に解決する。 我々は、$\textt{Nesterov's iterative smoothing}$$$\texttt{IterSmooth}$) および$\textit{Optimistic Gradient Descent-Ascent}$$$\textt{OGDA}$) の行列変種が、量子零サムゲームにおける線形速度で最終点収束を達成し、古典的多面体の場合と一致することを証明した。 我々の解析は、半定値プログラミング幾何学における誤り境界の新しい一般化に依存し、(SP-MS) がスペクトルヘドラ上の単調作用素に対して成り立つことを証明している。 最後に、副生成物として、厳密な正の半定値プログラムの並列近似のための古典的Jain-Watrous [arXiv:0808.2775] 法を指数的に高速化する。

関連論文リスト

• Sublinear Time Quantum Sensitivity Sampling [57.356528942341534]
  本稿では、量子感応サンプリングのための統一的なフレームワークを提案し、量子コンピューティングの利点を古典近似問題の幅広いクラスに拡張する。 我々のフレームワークは、コアセットを構築するための合理化されたアプローチを提供し、クラスタリング、回帰、低ランク近似などのアプリケーションにおいて、大幅なランタイム改善を提供します。
  論文  参考訳（メタデータ） (2025-09-20T20:18:49Z)
• 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 [95.50895904060309]
  最適行列乗算重み更新(OMMWU)アルゴリズムを導入し,平均収束複雑性を$mathcalO(d/epsilon)$ to $epsilon$-Nash equilibriaとする。 この二次的なスピードアップは、量子ゼロサムゲームにおける$epsilon$-Nash平衡の計算のための新しいベンチマークを定めている。
  論文  参考訳（メタデータ） (2023-11-17T20:38:38Z)
• Last-Iterate Convergence Properties of Regret-Matching Algorithms in Games [71.73971094342349]
  本稿では,Regret$+$ (RM$+$) に基づく2プレーヤゼロサムゲーム解決アルゴリズムの終点収束特性について検討する。 我々の分析は、アルゴリズムの極限点の幾何学的構造を新たに解析し、最終点収束に関する文献の大半から大きく離れていることを示す。
  論文  参考訳（メタデータ） (2023-11-01T17:34:58Z)
• Quasi-polynomial time algorithms for free quantum games in bounded dimension [11.56707165033]
  2プレイヤフリーゲームの値に対する加法$epsilon$-approximationsを計算するために、$exp(mathcalObig(T12(log2(AT)+log(Q)log(AT))/epsilon2big))という半定値プログラムを与える。 量子分離性問題と接続し、線形制約を伴う改良された多部量子デ・フィネッティ定理を用いる。
  論文  参考訳（メタデータ） (2020-05-18T16:55:08Z)

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

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