論文の概要: Approximating fixed size quantum correlations in polynomial time
- arxiv url: http://arxiv.org/abs/2507.12302v1
- Date: Wed, 16 Jul 2025 15:01:45 GMT
- ステータス: 翻訳完了
- システム内更新日: 2025-07-17 19:00:11.439125
- Title: Approximating fixed size quantum correlations in polynomial time
- Title（参考訳）: 多項式時間における固定サイズ量子相関の近似
- Authors: Julius A. Zeiss, Gereon Koßmann, Omar Fawzi, Mario Berta,
- Abstract要約: 固定サイズの2プレーヤフリーゲームの最適値に対する$varepsilon$-additive近似が時間内に計算可能であることを示す。
我々の主な結果は、制約付き量子分離性問題に適した新しいボース対称量子デフィネッティ定理に基づいている。
- 参考スコア（独自算出の注目度）: 8.099700053397278
- License: http://creativecommons.org/licenses/by/4.0/
- Abstract: We show that $\varepsilon$-additive approximations of the optimal value of fixed-size two-player free games with fixed-dimensional entanglement assistance can be computed in time $\mathrm{poly}(1/\varepsilon)$. This stands in contrast to previous analytic approaches, which focused on scaling with the number of questions and answers, but yielded only strict $\mathrm{exp}(1/\varepsilon)$ guarantees. Our main result is based on novel Bose-symmetric quantum de Finetti theorems tailored for constrained quantum separability problems. These results give rise to semidefinite programming (SDP) outer hierarchies for approximating the entangled value of such games. By employing representation-theoretic symmetry reduction techniques, we demonstrate that these SDPs can be formulated and solved with computational complexity $\mathrm{poly}(1/\varepsilon)$, thereby enabling efficient $\varepsilon$-additive approximations. In addition, we introduce a measurement-based rounding scheme that translates the resulting outer bounds into certifiably good inner sequences of entangled strategies. These strategies can, for instance, serve as warm starts for see-saw optimization methods. We believe that our techniques are of independent interest for broader classes of constrained separability problems in quantum information theory.
- Abstract（参考訳）: 固定次元エンタングルメントアシストを持つ固定サイズ2プレーヤフリーゲームの最適値の$\varepsilon$-additive近似は、時間$\mathrm{poly}(1/\varepsilon)$で計算できることを示す。
従来の分析手法とは対照的に、質問数や回答数によるスケーリングに重点を置いていたが、厳密な$\mathrm{exp}(1/\varepsilon)$の保証しか得られなかった。
我々の主な結果は、制約付き量子分離性問題に適した新しいボース対称量子デフィネッティ定理に基づいている。
これらの結果は、そのようなゲームの絡み合った値を近似するための半定値プログラミング(SDP)外階層を生み出す。
表現論的対称性の低減手法を用いることで、これらのSDPを計算複雑性$\mathrm{poly}(1/\varepsilon)$で定式化して解けることを示し、より効率的な$\varepsilon$-additive approximationsを可能にする。
さらに, 得られた外界を, 絡み合った戦略の内部配列に変換する, 測定に基づく丸め方式を導入する。
これらの戦略は、例えば、シーソー最適化メソッドのウォームスタートとして機能する。
我々は、量子情報理論における制約付き分離可能性問題のより広範なクラスに対して、我々の技術は独立した関心を持っていると信じている。
関連論文リスト
- Optimistic Online Learning in Symmetric Cone Games [3.124884279860061]
そこで我々は,Optimistic Symmetric Cone Multiplicative Weights Updateアルゴリズムを導入し,$mathcalO(1/epsilon)$の反復複雑性を確立し,$epsilon$-saddle点に達する。
重要な技術的貢献は、トレースワンノルムに対する対称錐負のエントロピーの強い凸性の新たな証明である。
論文 参考訳（メタデータ） (2025-04-04T16:59:19Z) - Computable entanglement cost under positive partial transpose operations [4.642647756403864]
我々は、量子演算の下でノイズの多い量子状態を作成する際の絡み合いコストを計算する問題を考える。
我々の知る限り、閉形式の公式が得られていないにもかかわらず、絡み合いの測度が効率的に計算可能であることを示すのはこれが初めてである。
論文 参考訳（メタデータ） (2024-05-15T18:00:01Z) - Projection by Convolution: Optimal Sample Complexity for Reinforcement Learning in Continuous-Space MDPs [56.237917407785545]
本稿では,円滑なベルマン作用素を持つ連続空間マルコフ決定過程(MDP)の一般クラスにおいて,$varepsilon$-optimal Policyを学習する問題を考察する。
我々のソリューションの鍵となるのは、調和解析のアイデアに基づく新しい射影技術である。
我々の結果は、連続空間 MDP における2つの人気と矛盾する視点のギャップを埋めるものである。
論文 参考訳（メタデータ） (2024-05-10T09:58:47Z) - Learning with Norm Constrained, Over-parameterized, Two-layer Neural Networks [54.177130905659155]
近年の研究では、再生カーネルヒルベルト空間(RKHS)がニューラルネットワークによる関数のモデル化に適した空間ではないことが示されている。
本稿では,有界ノルムを持つオーバーパラメータ化された2層ニューラルネットワークに適した関数空間について検討する。
論文 参考訳（メタデータ） (2024-04-29T15:04:07Z) - Reduced Contraction Costs of Corner-Transfer Methods for PEPS [0.0]
無限に投影された絡み合ったペア状態の収縮を抑えるための最優先計算コストを削減できる近似法を提案する。
計算コストの改善により、大きな結合次元の計算が可能となり、そのポテンシャルを拡大して課題を解決することができる。
論文 参考訳（メタデータ） (2023-06-14T02:54:12Z) - Pseudonorm Approachability and Applications to Regret Minimization [73.54127663296906]
我々は、高次元 $ell_infty$-approachability 問題を、低次元の擬ノルムアプローチ可能性問題に変換する。
我々は、$ell$や他のノルムに対するアプローチ可能性に関する以前の研究に類似した疑似ノルムアプローチ可能性のアルゴリズム理論を開発する。
論文 参考訳（メタデータ） (2023-02-03T03:19:14Z) - A Newton-CG based barrier-augmented Lagrangian method for general nonconvex conic optimization [53.044526424637866]
本稿では、2つの異なる対象の一般円錐最適化を最小化する近似二階定常点(SOSP)について検討する。
特に、近似SOSPを見つけるためのNewton-CGベースの拡張共役法を提案する。
論文 参考訳（メタデータ） (2023-01-10T20:43:29Z) - Stochastic Inexact Augmented Lagrangian Method for Nonconvex Expectation
Constrained Optimization [88.0031283949404]
多くの実世界の問題は複雑な非機能的制約を持ち、多くのデータポイントを使用する。
提案手法は,従来最もよく知られた結果で既存手法よりも優れた性能を示す。
論文 参考訳（メタデータ） (2022-12-19T14:48:54Z) - Explicit Second-Order Min-Max Optimization Methods with Optimal Convergence Guarantee [86.05440220344755]
我々は,非制約のmin-max最適化問題のグローバルなサドル点を求めるために,不正確な正規化ニュートン型手法を提案し,解析する。
提案手法は有界集合内に留まるイテレートを生成し、その反復は制限関数の項で$O(epsilon-2/3)$内の$epsilon$-saddle点に収束することを示す。
論文 参考訳（メタデータ） (2022-10-23T21:24:37Z) - On efficient algorithms for computing near-best polynomial
approximations to high-dimensional, Hilbert-valued functions from limited
samples [1.0650780147044159]
スパース近似は、限られたサンプルから滑らかで高次元の関数を近似するのに欠かせないものとなっている。
本稿では,指数的あるいは代数的収束率を主張するアルゴリズムと理論的保証と,サンプリング,アルゴリズム的,物理的離散化誤差に対する頑健性を紹介する。
論文 参考訳（メタデータ） (2022-03-25T20:56:07Z) - Nonparametric approximation of conditional expectation operators [0.3655021726150368]
最小の仮定の下で、$[Pf](x) := mathbbE[f(Y) mid X = x ]$ で定義される$L2$-operatorの近似について検討する。
我々は、再生されたカーネル空間上で作用するヒルベルト・シュミット作用素により、作用素ノルムにおいて$P$が任意に適切に近似できることを証明した。
論文 参考訳（メタデータ） (2020-12-23T19:06:12Z) - Learning Halfspaces with Tsybakov Noise [50.659479930171585]
テュバコフ雑音の存在下でのハーフスペースの学習可能性について検討する。
真半空間に関して誤分類誤差$epsilon$を達成するアルゴリズムを与える。
論文 参考訳（メタデータ） (2020-06-11T14:25:02Z) - 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)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。