論文の概要: Tailored First-order and Interior-point methods and a new semidefinite programming hierarchy for entanglement detection

• arxiv url: http://arxiv.org/abs/2508.05854v1
• Date: Thu, 07 Aug 2025 21:07:36 GMT
• ステータス: 翻訳完了
• システム内更新日: 2025-08-11 20:39:06.012763
• Title: Tailored First-order and Interior-point methods and a new semidefinite programming hierarchy for entanglement detection
• Title（参考訳）: 絡み付き検出のための第1次・内点法と新しい半定型プログラミング階層
• Authors: Javier Pena, Vikesh Siddhu, Sridhar Tayur,
• Abstract要約: 量子絡み合いは量子情報科学の核心にあるが、高次元またはノイズの多いシステムにおける信頼性の高い検出は、依然として基本的な計算課題である。 本稿では,EXT と DPS の間に挟まれた新しい SDP 階層 PST を導入する。 我々のアルゴリズムは数値的に安定しており、分離性の境界付近にある状態であっても、絡み合った証人や近接測度を生成することができる。
• 参考スコア（独自算出の注目度）: 2.4578723416255754
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: Quantum entanglement lies at the heart of quantum information science, yet its reliable detection in high-dimensional or noisy systems remains a fundamental computational challenge. Semidefinite programming (SDP) hierarchies, such as the Doherty-Parrilo-Spedalieri (DPS) and Extension (EXT) hierarchies, offer complete methods for entanglement detection, but their practical use is limited by exponential growth in problem size. In this paper, we introduce a new SDP hierarchy, PST, that is sandwiched between EXT and DPS--offering a tighter approximation to the set of separable states than EXT, while incurring lower computational overhead than DPS. We develop compact, polynomially-scalable descriptions of EXT and PST using partition mappings and operators. These descriptions in turn yield formulations that satisfy desirable properties such as the Slater condition and are well-suited to both first-order methods (FOMs) and interior-point methods (IPMs). We design a suite of entanglement detection algorithms: three FOMs (Frank-Wolfe, projected gradient, and fast projected gradient) based on a least-squares formulation, and a custom primal-dual IPM based on a conic programming formulation. These methods are numerically stable and capable of producing entanglement witnesses or proximity measures, even in cases where states lie near the boundary of separability. Numerical experiments on benchmark quantum states demonstrate that our algorithms improve the ability to solve deeper levels of the SDP hierarchy. In particular, the PST hierarchy combined with FOMs enables scalable and effective entanglement detection in relatively easy instances, while our IPM approach offers robustness and early witness recovery for the more difficult ones. Our results highlight the benefits of tailoring algorithmic formulations to hierarchy structure to advance entanglement detection at scale.
• Abstract（参考訳）: 量子絡み合いは量子情報科学の核心にあるが、高次元またはノイズの多いシステムにおける信頼性の高い検出は、依然として基本的な計算課題である。 半有限プログラミング(SDP)階層、例えばDoherty-Parrilo-Spedalieri (DPS) やExtension (EXT) 階層は、絡み検出の完全な方法を提供するが、その実用は問題サイズの指数的増加によって制限される。 本稿では,EXT と DPS の間に挟まれた新しい SDP 階層 PST を提案する。 分割写像と演算子を用いてEXTとPSTのコンパクトで多項式計算可能な記述を開発する。 これらの記述はスレーター条件のような望ましい性質を満足し、一階法(FOM)と内点法(IPM)の両方に適している。 3つのFOM (Frank-Wolfe, 射影勾配, 高速射影勾配) を最小二乗の定式化に基づいて設計し, 円錐型プログラミングの定式化を基本とした独自の原始双対IPMを設計する。 これらの方法は数値的に安定しており、分離性の境界付近にある状態であっても、絡み合った証人や近接測度を生成することができる。 ベンチマーク量子状態に関する数値実験により、我々のアルゴリズムはSDP階層のより深いレベルを解く能力を向上させることを示した。 特に、FOMと組み合わせたPST階層は、比較的簡単なインスタンスでスケーラブルで効果的な絡み合い検出を可能にします。 本研究は,階層構造に対するアルゴリズムの定式化を最適化し,大規模に絡み合う検出を高速化する利点を浮き彫りにした。

関連論文リスト

• A Hybrid Early-Exit Algorithm for Large Language Models Based on Space Alignment Decoding (SPADE) [3.1775609005777024]
  大規模言語モデルは、その深い構造のために計算コストが高い。 中間層表現を出力層に整合させる新しい復号法であるSPADEを提案する。 我々は,SPADEを用いて高品質な出力を生成しながら,信頼度を監視し,中間層での推論を停止するハイブリッド・アーリーエグジットアルゴリズムを開発した。
  論文  参考訳（メタデータ） (2025-07-23T15:49:03Z)
• Offline RL via Feature-Occupancy Gradient Ascent [9.983014605039658]
  大規模無限水平割引マルコフ決定過程(MDP)におけるオフライン強化学習の研究 我々は,特徴占有空間における勾配上昇の形式を実行する新しいアルゴリズムを開発した。 結果として得られた単純なアルゴリズムは、強い計算とサンプルの複雑さの保証を満たすことを示す。
  論文  参考訳（メタデータ） (2024-05-22T15:39:05Z)
• Towards Instance-Optimality in Online PAC Reinforcement Learning [28.156332484814616]
  そこで本研究では,PACの同定に要するサンプルの複雑さに対する最初のインスタンス依存下限について提案する。 我々は、citeWagenmaker22linearMDPのPEDELアルゴリズムのサンプル複雑さがこの下界に近づいたことを実証する。
  論文  参考訳（メタデータ） (2023-10-31T19:26:36Z)
• Provably Efficient UCB-type Algorithms For Learning Predictive State Representations [55.00359893021461]
  逐次決定問題は、予測状態表現(PSR)によってモデル化された低ランク構造が認められる場合、統計的に学習可能である 本稿では,推定モデルと実モデル間の全変動距離を上限とする新しいボーナス項を特徴とする,PSRに対する最初のUCB型アプローチを提案する。 PSRに対する既存のアプローチとは対照的に、UCB型アルゴリズムは計算的トラクタビリティ、最優先の準最適ポリシー、モデルの精度が保証される。
  論文  参考訳（メタデータ） (2023-07-01T18:35:21Z)
• Embed to Control Partially Observed Systems: Representation Learning with Provable Sample Efficiency [105.17746223041954]
  部分的に観察されたマルコフ決定過程(POMDP)における強化学習は2つの課題に直面している。 しばしば、未来を予測するのに完全な歴史を要し、地平線と指数関数的にスケールするサンプルの複雑さを誘導する。 本稿では,2段階の表現を最適化しながら学習するETC(Embed to Control)という強化学習アルゴリズムを提案する。
  論文  参考訳（メタデータ） (2022-05-26T16:34:46Z)
• Reinforcement Learning from Partial Observation: Linear Function Approximation with Provable Sample Efficiency [111.83670279016599]
  部分観察決定過程(POMDP)の無限観測および状態空間を用いた強化学習について検討した。 線形構造をもつPOMDPのクラスに対する部分可観測性と関数近似の最初の試みを行う。
  論文  参考訳（メタデータ） (2022-04-20T21:15:38Z)
• Adaptive Sampling for Best Policy Identification in Markov Decision Processes [79.4957965474334]
  本稿では,学習者が生成モデルにアクセスできる場合の,割引マルコフ決定(MDP)における最良の政治的識別の問題について検討する。 最先端アルゴリズムの利点を論じ、解説する。
  論文  参考訳（メタデータ） (2020-09-28T15:22:24Z)
• Accelerated Message Passing for Entropy-Regularized MAP Inference [89.15658822319928]
  離散値のランダムフィールドにおけるMAP推論の最大化は、機械学習の基本的な問題である。 この問題の難しさから、特殊メッセージパッシングアルゴリズムの導出には線形プログラミング(LP)緩和が一般的である。 古典的加速勾配の根底にある手法を活用することにより,これらのアルゴリズムを高速化するランダム化手法を提案する。
  論文  参考訳（メタデータ） (2020-07-01T18:43:32Z)

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

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