論文の概要: 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/ε$バリアの破れ:スペクトルの計量部分規則性を一般化する
• 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] 法を指数的に高速化する。

関連論文リスト

• Quantum Speedups for Stochastic Optimization with Heavy-Tailed Noise [49.730496294398726]
  重み付き確率変数に対する新しい量子平均推定器を開発した。 尾指数>4/3$のより強い下界を導出し、次元への非自明な依存が避けられないことを示す。 凸目的関数に対して,量子射影勾配降下法を提案する。
  論文  参考訳（メタデータ） (2026-07-28T09:29:37Z)
• Certifying Quantum Optimization and Circuit Cutting by Using Quantum-Classical Moment Duality [0.0]
  次数-2$ Sum-of-Squares半定値プログラミングコーンに基づく直接量子古典双対性を確立する。 同じモーメント行列が基礎となるユニタリ回路のテンソル積構造を明らかにする。 このフレームワークは変分量子アルゴリズムのMax-Cutインスタンスと回路切断のランダム状態で検証される。
  論文  参考訳（メタデータ） (2026-06-19T12:48:36Z)
• Operator-Algebraic Methods for Asymptotic-Preserving Quantum Simulation of Open Systems [0.0]
  我々は,量子計算資源を用いたマルチスケール物理システムのシミュレーションを行うための,数学的に厳密なフレームワークを開発した。 自然アナログ進化や解析多様体射影による高速な緩和を実現する層状量子プロトコルがダイヤモンドノルムに一様に収束することを証明する。 この研究は、古典的マルチスケール数値解析と量子シミュレーションアルゴリズムの間に、原理化された数学的ブリッジを提供する。
  論文  参考訳（メタデータ） (2026-05-16T19:27:58Z)
• The Harder Path: Last Iterate Convergence for Uncoupled Learning in Zero-Sum Games with Bandit Feedback [46.50566806285207]
  ゼロサム行列ゲームにおいて繰り返しプレイやバンディットフィードバックで学習する問題について検討する。 プレイヤー間の通信なしに、最終項目のナッシュ均衡への収束を保証するアンカップリングアルゴリズムを提案する。
  論文  参考訳（メタデータ） (2026-04-17T14:17:09Z)
• Hardness of High-Dimensional Linear Classification [58.29089693778071]
  我々は、最大半空間離散性問題に対する次元下界の新たな指数関数を確立する。 どちらも計算幾何学と機械学習の基本的問題であり、その正確で近似的な形式である。
  論文  参考訳（メタデータ） (2026-03-19T15:53:41Z)
• Average-case quantum complexity from glassiness [45.57609001239456]
  グラスネス(Glassiness)は、物理学において、不安定な自由エネルギーの風景を特徴とする現象であり、安定な古典的アルゴリズムの難しさを意味する。 レプリカ対称性の破れに基づく標準的な量子ガラス性の概念は、ギブスサンプリングのための安定な量子アルゴリズムを妨げていることを証明している。
  論文  参考訳（メタデータ） (2025-10-09T17:37:33Z)
• Sublinear Time Quantum Sensitivity Sampling [57.356528942341534]
  本稿では、量子感応サンプリングのための統一的なフレームワークを提案し、量子コンピューティングの利点を古典近似問題の幅広いクラスに拡張する。 我々のフレームワークは、コアセットを構築するための合理化されたアプローチを提供し、クラスタリング、回帰、低ランク近似などのアプリケーションにおいて、大幅なランタイム改善を提供します。
  論文  参考訳（メタデータ） (2025-09-20T20:18:49Z)
• From Classical to Quantum: Explicit Classical Distributions Achieving Maximal Quantum $f$-Divergence [4.956709222278243]
  最大$f$-分数を達成するような古典的な明示的な状態が与えられ、松本の定理の簡単な証明が可能である。 我々の方法論は特に単純であり、精巧な行列解析機構は必要とせず、基本線型代数のみである。
  論文  参考訳（メタデータ） (2025-01-24T09:06:13Z)
• Slow Mixing of Quantum Gibbs Samplers [47.373245682678515]
  一般化されたボトルネック補題を用いて、これらのツールの量子一般化を示す。 この補題は、古典的なハミング距離に類似する距離の量子測度に焦点を当てるが、一意に量子原理に根ざしている。 ポアソン・ファインマン・カック法を用いて古典的な緩やかな混合結果を持ち上げる方法を示す。
  論文  参考訳（メタデータ） (2024-11-06T22:51:27Z)
• 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)
• Quantum Lower Bounds for Finding Stationary Points of Nonconvex Functions [8.495749905129278]
  非最適化に対する古典的な下界の進歩にもかかわらず、これらの境界は依然として広く開である。 最初の設定について、Omegabig(frac-1+ppp)$。 第二設定については、おめがの()$。 Omega()$ if 勾配関数は滑らかである。 Omega()$ if 勾配関数は滑らかである。 Omega()$ if 勾配関数は滑らかである。 Omega()$ if 勾配関数は滑らかである。
  論文  参考訳（メタデータ） (2022-12-07T19:02:36Z)
• 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)

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

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