論文の概要: A Simple Algorithm for Best Separable State

• arxiv url: http://arxiv.org/abs/2608.10147v1
• Date: Mon, 10 Aug 2026 19:04:15 GMT
• ステータス: 翻訳完了
• システム内更新日: 2026-08-12 19:14:45.790957
• Title: A Simple Algorithm for Best Separable State
• Title（参考訳）: 最良の分離可能な状態に対する簡易アルゴリズム
• Abstract要約: 本研究では,無絡状態上での量子測定の最大受容確率を求める最適分離状態問題 (BSS) について検討する。 古典的な意味での目標は、$langle(x otimes y), M (x otimes y)rangle$ over unit vectors $x,y$ where $0 preceq M preceq I$である。
• 参考スコア（独自算出の注目度）: 5.5559749120901385
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: We study the best separable state problem (BSS), which asks for the maximum acceptance probability of a quantum measurement over unentangled states. In classical terms, the goal is to maximize $\langle(x \otimes y), M (x \otimes y)\rangle$ over unit vectors $x,y$ where $0 \preceq M \preceq I$; we call this value $\mathrm{BSS}(M)$. We study $\mathrm{BSS}$ in the "perfect completeness" regime, where given $M$ such that $\mathrm{BSS}(M) = 1$ the goal is to find the best possible solution $x,y$ -- this generalizes the problem of finding a rank-one matrix as close as possible to a given subspace of $\mathbb{R}^{n \times n}$ guaranteed to contain a rank-one matrix. The strongest known algorithmic guarantees for this problem are: (1) an algorithm which finds a solution with value $1-\varepsilon$ in time $\exp(\sqrt{n} (\log n)^{O(1)} / \varepsilon^2)$, due to Barak, Kothari, and Steurer, and (2) an algorithm which finds a solution with value $q/n$ in time roughly $n^{O(q)}$, due to Bhattiprolu, Ghosh, Guruswami, Lee, and Tulsiani. We give a much simpler approach to rounding the SoS relaxation, generalizing the canonical "global correlation rounding" technique, and obtain a better running time. Given $M$ with $\mathrm{BSS}(M) = 1$, our algorithm finds a solution with value $1-ε$ in time $n^{O(\sqrt{n/\varepsilon})}$, and a solution of value $q/n$ in time $n^{O(\sqrt q)}$. Using the same techniques, we prove a new variant of the "pinning lemma", a measure-decomposition theorem widely used in LP/SDP rounding, high-dimensional probability, and statistical physics, which we believe is of independent interest.
• Abstract（参考訳）: 本研究では,無絡状態上での量子測定の最大受容確率を求める最適分離状態問題 (BSS) について検討する。 古典的な言い方をすれば、目標は、$\langle(x \otimes y), M (x \otimes y)\rangle$ over unit vectors $x,y$ where $0 \preceq M \preceq I$; この値を$\mathrm{BSS}(M)$と呼ぶことである。 ここでは、$M$が与えられたとき、$\mathrm{BSS}(M) = 1$が最適解を求めること -- これは、階数 1 の行列が $\mathbb{R}^{n \times n} の与えられた部分空間にできるだけ近いものを見つけるという問題を一般化する。 この問題に対する最も強力なアルゴリズム保証は、(1)バラック、コサリ、シュテューラーによる1-\varepsilon$ in time $\exp(\sqrt{n} (\log n)^{O(1)} / \varepsilon^2)$、(2)バッティプラル、ゴッシュ、グルスワミ、リー、トゥルシアニによる1-\varepsilon$ in time $q/n$ in time $n^{O(q)}$の解を求めるアルゴリズムである。 我々は、SoS緩和を円滑化し、標準的な「グローバル相関ラウンドリング」手法を一般化し、より良いランニング時間を得るためのより単純なアプローチを提案する。 M$ with $\mathrm{BSS}(M) = 1$とすると、我々のアルゴリズムは1-ε$ in time $n^{O(\sqrt{n/\varepsilon})}$と$q/n$ in time $n^{O(\sqrt q)}$の解を求める。 同じ手法を用いて、LP/SDPラウンドリング、高次元確率、統計物理学で広く用いられている測度分解定理である「ピンニング補題」の新たな変種を証明し、これは独立な関心事であると考えている。

関連論文リスト

• Proper Agnostic Learning of Functions of Halfspaces under Gaussian Marginals [5.7652356955571085]
  i.d.ラベル付きサンプルが$mathbbRd times pm 1$上の未知の分布からサンプリングされ、$mathbbRd$がガウシアンであることを考えると、目標はターゲットクラス$mathcalF$から仮説を出力することである。 我々のアルゴリズムは、$dO(K2 log (1/)/2) + (K/)O(K) で実行されます。
  論文  参考訳（メタデータ） (2026-05-26T19:07:06Z)
• Information-Computation Tradeoffs for Noiseless Linear Regression with Oblivious Contamination [65.37519531362157]
  このタスクに対する効率的な統計的クエリアルゴリズムは、VSTATの複雑さを少なくとも$tildeOmega(d1/2/alpha2)$で要求する。
  論文  参考訳（メタデータ） (2025-10-12T15:42:44Z)
• Sublinear-Time Algorithms for Diagonally Dominant Systems and Applications to the Friedkin-Johnsen Model [5.101318208537081]
  線形系を解くための準線形時間アルゴリズムについて研究し、$Sz = b$, ここでは$S$は対角的に支配的な行列である。 任意の$u in [n]$に対して、加算誤差のある$z_u$ of $z*_u$を返します。 また、一致する下界を証明し、$S_max$ に対する線型依存が最適であることを示す。
  論文  参考訳（メタデータ） (2025-09-16T14:13:31Z)
• The Communication Complexity of Approximating Matrix Rank [50.6867896228563]
  この問題は通信複雑性のランダム化を$Omega(frac1kcdot n2log|mathbbF|)$とする。 アプリケーションとして、$k$パスを持つ任意のストリーミングアルゴリズムに対して、$Omega(frac1kcdot n2log|mathbbF|)$スペースローバウンドを得る。
  論文  参考訳（メタデータ） (2024-10-26T06:21:42Z)
• Solving Dense Linear Systems Faster Than via Preconditioning [1.8854491183340518]
  我々のアルゴリズムは$tilde O(n2)$ if $k=O(n0.729)$であることを示す。 特に、我々のアルゴリズムは$tilde O(n2)$ if $k=O(n0.729)$である。 主アルゴリズムはランダム化ブロック座標降下法とみなすことができる。
  論文  参考訳（メタデータ） (2023-12-14T12:53:34Z)
• Matrix Completion in Almost-Verification Time [37.61139884826181]
  99%の行と列で$mathbfM$を完了するアルゴリズムを提供する。 本稿では,この部分完備保証を完全行列補完アルゴリズムに拡張する方法を示す。
  論文  参考訳（メタデータ） (2023-08-07T15:24:49Z)
• Fast $(1+\varepsilon)$-Approximation Algorithms for Binary Matrix Factorization [54.29685789885059]
  本稿では, 2次行列分解(BMF)問題に対する効率的な$(1+varepsilon)$-approximationアルゴリズムを提案する。 目標は、低ランク因子の積として$mathbfA$を近似することである。 我々の手法はBMF問題の他の一般的な変種に一般化する。
  論文  参考訳（メタデータ） (2023-06-02T18:55:27Z)
• Randomized and Deterministic Attention Sparsification Algorithms for Over-parameterized Feature Dimension [18.57735939471469]
  我々は注意問題のスパシフィケーションを考慮する。 超大規模特徴量の場合、文の長さをほぼ線形に縮めることができる。
  論文  参考訳（メタデータ） (2023-04-10T05:52:38Z)
• Threshold Phenomena in Learning Halfspaces with Massart Noise [56.01192577666607]
  ガウス境界の下でのマスアートノイズ付きmathbbRd$におけるPAC学習ハーフスペースの問題について検討する。 この結果は,Massartモデルにおける学習ハーフスペースの複雑さを定性的に特徴づけるものである。
  論文  参考訳（メタデータ） (2021-08-19T16:16:48Z)
• Learning a Latent Simplex in Input-Sparsity Time [58.30321592603066]
  我々は、$AinmathbbRdtimes n$へのアクセスを考えると、潜入$k$-vertex simplex $KsubsetmathbbRdtimes n$を学習する問題を考える。 実行時間における$k$への依存は、トップ$k$特異値の質量が$a$であるという自然な仮定から不要であることを示す。
  論文  参考訳（メタデータ） (2021-05-17T16:40:48Z)
• Streaming Complexity of SVMs [110.63976030971106]
  本稿では,ストリーミングモデルにおけるバイアス正規化SVM問題を解く際の空間複雑性について検討する。 両方の問題に対して、$frac1lambdaepsilon$の次元に対して、$frac1lambdaepsilon$よりも空間的に小さいストリーミングアルゴリズムを得ることができることを示す。
  論文  参考訳（メタデータ） (2020-07-07T17:10:00Z)
• Maximizing Determinants under Matroid Constraints [69.25768526213689]
  我々は、$det(sum_i in Sv_i v_i v_itop)$が最大になるような基底を$S$$$$M$とする問題を研究する。 この問題は、実験的なデザイン、商品の公平な割り当て、ネットワーク設計、機械学習など、さまざまな分野に現れている。
  論文  参考訳（メタデータ） (2020-04-16T19:16:38Z)

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

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