論文の概要: Polynomial-Time Algorithms for Nuclear Tensor Norms and Multipartite Separability

• arxiv url: http://arxiv.org/abs/2610.03637v1
• Date: Fri, 02 Oct 2026 17:27:10 GMT
• ステータス: 翻訳完了
• システム内更新日: 2026-10-06 00:14:30.516418
• Title: Polynomial-Time Algorithms for Nuclear Tensor Norms and Multipartite Separability
• Title（参考訳）: 核テンソルノルムの多項式時間アルゴリズムと多部分離性
• Abstract要約: 有界フロベニウスノルムを持つテンソルに対して、次元$d$の局所因子のそれぞれが凸集合から選択されるような多重線型最適化問題を研究する。 定数加法近似に対して、時間で$dO(k)$で実行される決定論的アルゴリズムを与える。 これらの設定では、$textpoly(k)$ copyと$textpoly(klog d)$ timeを使ってFrobenius-normセパビリティテストを解決するアルゴリズムを得る。
• 参考スコア（独自算出の注目度）: 19.676761365242193
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: We study a multilinear optimization problem for tensors with bounded Frobenius norm, where each of the $k$ local factors of dimension $d$ is chosen from a convex set. We give a deterministic algorithm running in time $d^{O(k)}$ for constant additive approximations. As applications, we obtain the first polynomial-time algorithms at constant accuracy for weak membership in the nuclear-norm unit ball of high-order tensors and for multipartite quantum separability in Frobenius norm. Our approach views tensor optimization as a cooperative multiprover game and combines this perspective with a recursive spectral compression procedure. We then show that related ideas admit a quantum implementation when the input state is given through copies, rather than an explicit classical description. In these settings we obtain an algorithm to solve Frobenius-norm separability testing using $\text{poly}(k)$ copies and $\text{poly}(k\log d)$ time.
• Abstract（参考訳）: 有界フロベニウスノルムを持つテンソルに対して、次元$d$の局所因子のそれぞれが凸集合から選択されるような多重線型最適化問題を研究する。 定数加法近似に対して、時間で$d^{O(k)}$で実行される決定論的アルゴリズムを与える。 応用として、高次テンソルの核ノルム単位球の弱メンバシップとフロベニウスノルムの多部量子分離性について、定数精度で最初の多項式時間アルゴリズムを得る。 提案手法は,テンソル最適化を協調型マルチプロデューサゲームとみなし,この視点を再帰的なスペクトル圧縮手法と組み合わせる。 次に、関連するアイデアは、明示的な古典的記述ではなく、コピーを通じて入力状態が与えられるときの量子的実装を認めることを示す。 これらの設定では、$\text{poly}(k)$ copy と $\text{poly}(k\log d)$ time を用いてフロベニウス-ノルム分離性テストを解決するアルゴリズムを得る。

関連論文リスト

• Solving Sparse SDPs in Sublinear Time: A Classical Algorithm Inspired by the Quantum OR Lemma [70.99943094379263]
  有界ラディウス系におけるスパース半定値プログラムに対する最初の準時間古典的解法を与える。 我々の主な技術的貢献は、ハミルトンのギブス状態を同時に表す古典的な手続きである。
  論文  参考訳（メタデータ） (2026-09-30T17:51:21Z)
• Exponential Reduction of Mesh Dependence in Quantum Estimation of Parabolic PDE Observables [3.3636842548621275]
  線形および二次可観測物を推定し、測定前に回路内部に粗いキャンセリングを配置する量子PDEアルゴリズムを開発した。 また、1次元のエネルギー直交ダイアド中間点の詳細に基づく非フーリエ実現を与える。
  論文  参考訳（メタデータ） (2026-07-20T16:09:24Z)
• Quantum Algorithms for Gowers Norm Estimation, Polynomial Testing, and Arithmetic Progression Counting over Finite Abelian Groups [0.0]
  有限アーベル群上のゴワーズノルム$Uk$を推定するための量子アルゴリズム群を提案する。 これらのアルゴリズムは、ガウワーズノルムに対する最近の逆定理と振幅推定を利用して高次相関を明らかにする。
  論文  参考訳（メタデータ） (2025-08-02T06:58:12Z)
• Sum-of-Squares inspired Quantum Metaheuristic for Polynomial Optimization with the Hadamard Test and Approximate Amplitude Constraints [76.53316706600717]
  最近提案された量子アルゴリズムarXiv:2206.14999は半定値プログラミング(SDP)に基づいている SDPにインスパイアされた量子アルゴリズムを2乗和に一般化する。 この結果から,本アルゴリズムは大きな問題に適応し,最もよく知られた古典学に近似することが示唆された。
  論文  参考訳（メタデータ） (2024-08-14T19:04:13Z)
• A quantum-classical performance separation in nonconvex optimization [7.427989325451079]
  我々は最近提案された量子ハミルトニアン(QHD)アルゴリズムが、このファミリーから$d$Dのクエリを解くことができることを証明した。 一方、総合的な実証研究により、最先端の古典的アルゴリズム/解法はそのような問合せを解決するのにスーパーポリノミカルな時間を必要とすることが示唆されている。
  論文  参考訳（メタデータ） (2023-11-01T19:51:00Z)
• Quantum Algorithms for Sampling Log-Concave Distributions and Estimating Normalizing Constants [8.453228628258778]
  我々は,対数凹分布をサンプリングし,正規化定数を推定するための量子アルゴリズムを開発した。 我々はモンテカルロ法と量子ウォークの量子アナログを利用する。 また、正規化定数を推定するための1/epsilon1-o(1)$量子下界も証明する。
  論文  参考訳（メタデータ） (2022-10-12T19:10:43Z)
• Quantum Goemans-Williamson Algorithm with the Hadamard Test and Approximate Amplitude Constraints [62.72309460291971]
  本稿では,n+1$ qubitsしか使用しないGoemans-Williamsonアルゴリズムの変分量子アルゴリズムを提案する。 補助量子ビット上で適切にパラメータ化されたユニタリ条件として目的行列を符号化することにより、効率的な最適化を実現する。 各種NPハード問題に対して,Goemans-Williamsonアルゴリズムの量子的効率的な実装を考案し,提案プロトコルの有効性を実証する。
  論文  参考訳（メタデータ） (2022-06-30T03:15:23Z)
• Higher-order Derivatives of Weighted Finite-state Machines [68.43084108204741]
  本研究では、重み付き有限状態機械の正規化定数に関する高次微分の計算について検討する。 文献に記載されていないすべての順序の導関数を評価するための一般アルゴリズムを提案する。 我々のアルゴリズムは以前のアルゴリズムよりもはるかに高速である。
  論文  参考訳（メタデータ） (2021-06-01T19:51:55Z)
• Quantum algorithms for spectral sums [50.045011844765185]
  正半定値行列(PSD)のスペクトル和を推定するための新しい量子アルゴリズムを提案する。 本稿では, スペクトルグラフ理論における3つの問題に対して, アルゴリズムと手法が適用可能であることを示す。
  論文  参考訳（メタデータ） (2020-11-12T16:29:45Z)
• 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)

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

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