論文の概要: Semidefinite extension complexity of the separable set, with applications to approximate disentanglers
- arxiv url: http://arxiv.org/abs/2609.09033v1
- Date: Tue, 08 Sep 2026 17:00:11 GMT
- ステータス: 翻訳完了
- システム内更新日: 2026-09-11 20:28:38.521468
- Title: Semidefinite extension complexity of the separable set, with applications to approximate disentanglers
- Title（参考訳）: 可分集合の半定拡張複雑性と近似ディスタングルへの応用
- Abstract要約: 分離可能な状態における測定値の最大受容確率を近似する半定値プログラムを考える。
我々の証明は、Lee, Raghavendra, Steurer の量的擬似密度定理と明示的なブロック陽性作用素とチェビシェフ増幅を組み合わせたものである。
- 参考スコア（独自算出の注目度）: 0.6117371161379209
- License: http://creativecommons.org/licenses/by/4.0/
- Abstract: We prove quantitative lower bounds on the semidefinite extension complexity of the set of separable quantum states on $\mathbb{C}^d\otimes\mathbb{C}^d$. We consider semidefinite programs (SDPs) that approximate the maximum acceptance probability of a measurement over separable states, the optimization problem underlying QMA(2). In the extended-formulation model of Harrow, Natarajan, and Wu (HNW), all measurements share a common feasible region and an objective-independent embedding of product states that exactly reproduces their acceptance probabilities. For every $0<θ<2/7$, there are constants $c_θ,a_θ>0$ such that, for sufficiently large $d$, any such SDP with uniform additive error $0<a\le a_θ$ has size at least $d^{c_θ\min\{a^{-1/3},d^θ\}}$. The bound applies at sufficiently small constant error, is superpolynomial in $d$ whenever $a=o(1)$, and becomes $d^{Ω(d^θ)}$ when $a\le d^{-3θ}$, improving HNW's quasipolynomial bound at inverse- square error. The same bound holds for any SDP-representable convex set of states that contains all separable states and lies within trace distance $a$ of them, giving a quantitative counterpart to Fawzi's theorem that the separable set has no exact semidefinite representation. Our proof combines the quantitative pseudo-density theorem of Lee, Raghavendra, and Steurer with explicit block-positive operators and Chebyshev amplification. Our main results are supported by Lean proofs.
- Abstract（参考訳）: 我々は、$\mathbb{C}^d\otimes\mathbb{C}^d$ 上の分離可能な量子状態の集合の半定拡張複雑性に対する定量的な下界を証明した。
我々は、分離可能な状態における測定の最大受容確率を近似する半定値プログラム(SDP)、すなわちQMA(2)の根底にある最適化問題を考える。
Harrow, Natarajan, Wu (HNW) の拡張形式モデルでは、すべての測定値が共通の実現可能な領域と、その受容確率を正確に再現する積状態の客観的に依存しない埋め込みを共有している。
すべての$0<θ<2/7$に対して、十分大きな$d$に対して、一様加法誤差が 0<a\le a_θ$ を持つ任意の SDP が少なくとも$d^{c_θ\min\{a^{-1/3},d^θ\}}$ であるような定数 $c_θ,a_θ>0$ が存在する。
境界は十分小さな定数誤差で適用され、$a=o(1)$のときいつでも$d$で超多項式であり、$a\le d^{-3θ}$のとき$d^{Ω(d^θ)}$となり、HNWの準多項式境界を逆二乗誤差で改善する。
同じ境界は、すべての分離可能な状態を含む任意の SDP 表現可能な凸集合に対して成り立ち、その中のトレース距離$a$ の範囲内にあり、分離可能な集合は完全半定値表現を持たないというフォウジの定理と定量的に一致する。
我々の証明は、Lee, Raghavendra, Steurer の量的擬似密度定理と明示的なブロック陽性作用素とチェビシェフ増幅を組み合わせたものである。
私たちの主な成果はリーンの証明によって支えられています。
関連論文リスト
- The I3322 quantum value is attained spatially but not in finite dimension [0.0]
S$ をコリンズ・ギシン正規化の $I_3322$ Bell 関数の量子超越(古典的境界 0; 2量子ビット最大値 1/4)とする。
i) 有限次元の量子戦略が$S$(任意の有限局所次元、純粋または混合状態、射影またはPOVM測定)に達することはないこと、PalとVertesi(2010)を証明すること。
次元複雑性も決定する:$S_d$で局所次元$le d$と$D()=mind:S-S_dの最適値
論文 参考訳（メタデータ） (2026-09-03T15:48:01Z) - Deterministic Minimum-Output-Entropy Nonadditivity via Haagerup's Inequality and Near-Free Permutation Representations [6.9022592726569085]
コリンズの最小出力エントロピー非付加性の混合単位証明に基づく有限次元二次証明を実現する。
論文 参考訳（メタデータ） (2026-08-31T16:53:42Z) - Uniform Statistical Convergence of Empirical Sinkhorn Potentials with Exponential and Polynomial Dependence on the Regularization Parameter [3.6552781109515853]
本研究では,一様損失下でのエントロピー最適輸送電位の実験的シンクホーン推定器について検討した。
固定正規化パラメータ $varepsilon>0$ に対して、漸近的でない統計レート $n-1/2$ を確立する。
鍵となる要件は、シンクホーン写像の残留安定度推定である。
論文 参考訳（メタデータ） (2026-08-29T08:59:00Z) - Quantum Change Interval: Exact Asymptotics for Minimum Error Localization [8.906035369693457]
我々は、あるソースが1つの間隔で$lvertrangle$と$lvert0rangle$を出力する復帰量子変化間隔について研究する。
Toeplitz 比較と Flner 変換を用いて行列を解析し,励起数と間隔包による正確な分解を行った。
論文 参考訳（メタデータ） (2026-08-25T13:30:26Z) - Research Report on Noise-Shaped One-Bit Coefficients in Discrete Polynomial Fourier Extension [0.0]
本報告では、正規化離散フーリエ展開におけるノイズ形状の1ビット係数について検討する。
一階のシグマ量子化の場合、誤差は$e_k=u_k-q_k=v_k$と書かれ、一様有界である。
パラボリックな$_x,t()=x+t2$の場合、境界は$J(x,t)=int_01 |x+2t|d$で表され、均一な$N-1$レートはシャープである。
論文 参考訳（メタデータ） (2026-07-26T21:51:41Z) - Near-Optimal Dimension Lower Bounds for Single-Vector Embeddings of Maximum Inner Product Similarity [75.14269295861845]
シングルトンクエリでは、Chamferは最大内部積類似度(MAX-IP)になる。
すべての固定$in(0,1)$に対して、定数は$A_,c_>0$である。
単位球MAX-IPマトリクスは、DNFパターンマトリクスの正確な2値アフィンイメージであり、少なくとも8ドルのギャップがある。
論文 参考訳（メタデータ） (2026-07-22T17:27:20Z) - No Finite NPA Level Characterizes the Complete Quantum Set in the Simplest Bell Scenario [0.0]
エンフィノ有限レベルが正確であることを示す。
測定プロジェクタ内の単語の固定有限リストに基づく標準NPA緩和はすべて、完全量子集合を厳密に含んでいる。
論文 参考訳（メタデータ） (2026-07-16T04:52:11Z) - Optimal Dimension-Free Sampling for Regularized Classification [56.72526267755301]
我々は、リプシッツ連続分類損失関数の幅広いクラスに対して、$(1pmvarepsilon)$-relativeエラーを達成する最適サンプリング境界を証明した。
これにはロジスティックやシグモイドの損失、ヒンジの損失、ReLUの損失といった重要な機能が含まれており、顕著で一般的な例である。
論文 参考訳（メタデータ） (2026-05-22T15:05:33Z) - Hardness of High-Dimensional Linear Classification [58.29089693778071]
我々は、最大半空間離散性問題に対する次元下界の新たな指数関数を確立する。
どちらも計算幾何学と機械学習の基本的問題であり、その正確で近似的な形式である。
論文 参考訳（メタデータ） (2026-03-19T15:53:41Z) - Measuring quantum relative entropy with finite-size effect [53.64687146666141]
相対エントロピー$D(rho|sigma)$を$sigma$が知られているときに推定する。
我々の推定器は次元$d$が固定されたときにCram'er-Rao型境界に達する。
論文 参考訳（メタデータ） (2024-06-25T06:07:20Z) - Near Sample-Optimal Reduction-based Policy Learning for Average Reward
MDP [58.13930707612128]
この研究は、平均報酬マルコフ決定過程(AMDP)における$varepsilon$-Optimal Policyを得る際のサンプルの複雑さを考察する。
我々は、状態-作用対当たりの$widetilde O(H varepsilon-3 ln frac1delta)$サンプルを証明し、$H := sp(h*)$は任意の最適ポリシーのバイアスのスパンであり、$varepsilon$は精度、$delta$は失敗確率である。
論文 参考訳（メタデータ） (2022-12-01T15:57:58Z) - A Law of Robustness beyond Isoperimetry [84.33752026418045]
我々は、任意の分布上でニューラルネットワークパラメータを補間する頑健性の低い$Omega(sqrtn/p)$を証明した。
次に、$n=mathrmpoly(d)$のとき、スムーズなデータに対する過度なパラメータ化の利点を示す。
我々は、$n=exp(omega(d))$ のとき、$O(1)$-Lipschitz の頑健な補間関数の存在を否定する。
論文 参考訳（メタデータ） (2022-02-23T16:10:23Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。