論文の概要: Complexity of mixed Schatten norms of quantum maps

• arxiv url: http://arxiv.org/abs/2507.08358v1
• Date: Fri, 11 Jul 2025 07:20:25 GMT
• ステータス: 翻訳完了
• システム内更新日: 2025-07-14 18:03:54.269795
• Title: Complexity of mixed Schatten norms of quantum maps
• Title（参考訳）: 量子写像の混合シャッテンノルムの複素性
• Authors: Jan Kochanowski, Omar Fawzi, Cambyse Rouzé,
• Abstract要約: 我々は、空間間の線型写像の混合Schatten $|Phi|_qto p$ノルムの計算の複雑さについて研究する。 Phi$ が完全に正であれば、$q geq p$ のとき、p$ に対して $| Phi |_q が効率的に計算可能であることを示す。
• 参考スコア（独自算出の注目度）: 7.182449176083625
• License: http://creativecommons.org/licenses/by-nc-sa/4.0/
• Abstract: We study the complexity of computing the mixed Schatten $\|\Phi\|_{q\to p}$ norms of linear maps $\Phi$ between matrix spaces. When $\Phi$ is completely positive, we show that $\| \Phi \|_{q \to p}$ can be computed efficiently when $q \geq p$. The regime $q \geq p$ is known as the non-hypercontractive regime and is also known to be easy for the mixed vector norms $\ell_{q} \to \ell_{p}$ [Boyd, 1974]. However, even for entanglement-breaking completely-positive trace-preserving maps $\Phi$, we show that computing $\| \Phi \|_{1 \to p}$ is $\mathsf{NP}$-complete when $p>1$. Moving beyond the completely-positive case and considering $\Phi$ to be difference of entanglement breaking completely-positive trace-preserving maps, we prove that computing $\| \Phi \|^+_{1 \to 1}$ is $\mathsf{NP}$-complete. In contrast, for the completely-bounded (cb) case, we describe a polynomial-time algorithm to compute $\|\Phi\|_{cb,1\to p}$ and $\|\Phi\|^+_{cb,1\to p}$ for any linear map $\Phi$ and $p\geq1$.
• Abstract（参考訳）: 我々は、混合シャッテン$\|\Phi\|_{q\to p} の線型写像のノルム$\Phi$ を行列空間間で計算する複雑性について研究する。 完全正のとき、$\| \Phi \|_{q \to p}$ は$q \geq p$ のときに効率的に計算できることを示す。 レジーム $q \geq p$ は非超収縮的レジームとして知られ、混合ベクトルノルム $\ell_{q} \to \ell_{p}$ [Boyd, 1974] に対して容易であることが知られている。 しかし、絡み合う完全正のトレース保存写像 $\Phi$ であっても、$p>1$ のとき、計算 $\| \Phi \|_{1 \to p}$ が $\mathsf{NP}$-完全であることを示す。 完全正の場合を超えて、完全正のトレース保存写像を破る絡み合いの差として$\Phi$を考えると、$\| \Phi \|^+_{1 \to 1}$が$\mathsf{NP}$-完全であることが証明される。 対照的に、完全有界(cb)の場合、任意の線型写像 $\Phi$ と $p\geq1$ に対して$\|\Phi\|_{cb,1\to p}$ と $\|\Phi\|^+_{cb,1\to p}$ を計算する多項式時間アルゴリズムを記述する。

関連論文リスト

• High-Dimensional Calibration from Swap Regret [40.9736612423411]
  任意の凸集合 $mathcalP 部分集合 mathbbRd$ 上での多次元予測のオンライン校正について検討する。 我々は、$O(sqrtrho T)$$$T$ラウンド後の最悪の後悔を保証できるならば、$T = exp(logd/epsilon2) の後、$epsilon$-calibrated 予測を得ることができることを示した。
  論文  参考訳（メタデータ） (2025-05-27T17:31:47Z)
• Learning and Computation of $Φ$-Equilibria at the Frontier of Tractability [85.07238533644636]
  $Phi$-equilibriaは、オンライン学習とゲーム理論の中心にある、強力で柔軟なフレームワークだ。 効率的なオンラインアルゴリズムは、$textpoly(d, k)/epsilon2$ラウンドを使用して、平均$Phi$-regretを最大$epsilon$で生成することを示す。 また、オンライン設定において、ほぼ一致した下限を示し、その結果、$Phi$-regretの学習可能性を取得する偏差の族が初めて得られる。
  論文  参考訳（メタデータ） (2025-02-25T19:08:26Z)
• PREM: Privately Answering Statistical Queries with Relative Error [91.98332694700046]
  合成データを生成する新しいフレームワークである$mathsfPREM$(Private Relative Error Multiplicative weight update)を紹介します。 我々はアルゴリズムをほぼ一致する下界で補完する。
  論文  参考訳（メタデータ） (2025-02-20T18:32:02Z)
• Mapping the space of quantum expectation values [0.0]
  ヒルベルト空間 $cal H$ of dimension $N$ を持つ量子系の場合、基本的な問題は集合 $E_S の部分集合 mathbbRn$ of points $vece$ を理解することである。 関連する質問は、与えられた期待値のセット$vec$が$E_S$にあるかどうかを決定することである。
  論文  参考訳（メタデータ） (2023-10-19T19:17:42Z)
• $\ell_p$-Regression in the Arbitrary Partition Model of Communication [59.89387020011663]
  コーディネータモデルにおける分散$ell_p$-regression問題のランダム化通信複雑性について考察する。 p = 2$、すなわち最小二乗回帰の場合、$tildeTheta(sd2 + sd/epsilon)$ bitsの最初の最適境界を与える。 p in (1,2)$ に対して、$tildeO(sd2/epsilon + sd/mathrmpoly(epsilon)$ upper bound を得る。
  論文  参考訳（メタデータ） (2023-07-11T08:51:53Z)
• Low-Rank Approximation with $1/\epsilon^{1/3}$ Matrix-Vector Products [58.05771390012827]
  我々は、任意のSchatten-$p$ノルムの下で、低ランク近似のためのクリロフ部分空間に基づく反復法について研究する。 我々の主な成果は、$tildeO(k/sqrtepsilon)$ matrix-vector productのみを使用するアルゴリズムである。
  論文  参考訳（メタデータ） (2022-02-10T16:10:41Z)
• The planted matching problem: Sharp threshold and infinite-order phase transition [25.41713098167692]
  ランダムに重み付けされた$ntimes n$ bipartite graphに隠された完全マッチング$M*$を再構築する問題について検討する。 任意の小さな定数 $epsilon>0$ に対して $sqrtd B(mathcalP,mathcalQ) ge 1+epsilon$ が成り立つ場合、任意の推定値の再構築誤差は $0$ から有界であることが示される。
  論文  参考訳（メタデータ） (2021-03-17T00:59:33Z)
• Linear Bandits on Uniformly Convex Sets [88.3673525964507]
  線形バンディットアルゴリズムはコンパクト凸作用集合上の $tildemathcalo(nsqrtt)$ pseudo-regret 境界を与える。 2種類の構造的仮定は、より良い擬似回帰境界をもたらす。
  論文  参考訳（メタデータ） (2021-03-10T07:33:03Z)
• The Average-Case Time Complexity of Certifying the Restricted Isometry Property [66.65353643599899]
  圧縮センシングにおいて、100万倍のN$センシング行列上の制限等尺性(RIP)はスパースベクトルの効率的な再構成を保証する。 Mtimes N$ matrices with i.d.$mathcalN(0,1/M)$ entry。
  論文  参考訳（メタデータ） (2020-05-22T16:55:01Z)

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

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