論文の概要: Membership in the cone of quantum states over time is NP-hard

• arxiv url: http://arxiv.org/abs/2610.34972v1
• Date: Mon, 26 Oct 2026 07:41:18 GMT
• ステータス: 翻訳完了
• システム内更新日: 2026-10-29 18:30:16.319323
• Title: Membership in the cone of quantum states over time is NP-hard
• Title（参考訳）: 時間経過した量子状態の錐体のメンバーシップはNPハードである
• Abstract要約: Fawziの定理は、$widehatmathcalQ(A:A'R)$が$d=dim Age2$, $r=dim Rge2$, $d+r>5$のとき有限半定表現を認めないことを示唆している。
• 参考スコア（独自算出の注目度）: 0.0
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: A state over time (stote) pairs a state $ρ$ with a channel $\mathcal{E}$ as the Hermitian, generally non-positive operator $(ρ\otimes\mathbf{1})\star J_\mathcal{E}$. Characterizing the convex cone $\widehat{\mathcal{Q}}$ these operators generate was posed as an open problem in~\cite{HoogstederCalsamigliaWinter2025}. We exhibit a linear copy of the bipartite separable cone as an exposed face of $\widehat{\mathcal{Q}}$: for output systems of the form $B = A'R$ with $A'$ a copy of the input, there is an explicit witness $W_0\in\widehat{\mathcal{Q}}^*$ and an explicit injective linear map $L$ with $σ\in \mathrm{SEP}_{+}(A{:}R)\iff L(σ)\in\widehat{\mathcal{Q}}(A{:}A'R)$. Composing with the NP-hardness of separability shows that exact membership, weak membership, and weak optimization are NP-hard for $\widehat{\mathcal{Q}}$ and its dual. A quantitative stability bound makes the weak-membership reduction valid at inverse-polynomial accuracy. Thus polynomial-time membership tests do not exist unless $\mathrm{P}=\mathrm{NP}$. Independently of this complexity assumption, Fawzi's theorem implies that $\widehat{\mathcal{Q}}(A{:}A'R)$ admits no finite semidefinite representation when $d=\dim A\ge2$, $r=\dim R\ge2$, and $d+r>5$.
• Abstract（参考訳）: 時間が経過した状態は、状態 $ρ$ とチャネル $\mathcal{E}$ をエルミート的、一般に非正の作用素 $(ρ\otimes\mathbf{1})\star J_\mathcal{E}$ としてペアする。 convex cone $\widehat{\mathcal{Q}}$これらの演算子は、~\cite{HoogstederCalsamigliaWinter2025} においてオープン問題として提起された。 B = A'R$ with $A'$ という形の出力系には、明示的な証人 $W_0\in\widehat{\mathcal{Q}}^*$ と明示的な射影線型写像 $L$ with $σ\in \mathrm{SEP}_{+}(A{:}R)\iff L(σ)\in\widehat{\mathcal{Q}}(A{:}A'R)$ が存在する。 分離性のNP-ハードと組み合わせることで、$\widehat{\mathcal{Q}}$とその双対に対して、正確なメンバシップ、弱メンバシップ、弱最適化がNP-ハードであることが示される。 定量的安定性境界は、弱メンバーシップの低減を逆ポリノミカル精度で有効にする。 したがって、多項式時のメンバーシップテストは$\mathrm{P}=\mathrm{NP}$でない限り存在しない。 この複雑性の仮定とは独立に、ファウジの定理は、$\widehat{\mathcal{Q}}(A{:}A'R)$ が$d=\dim A\ge2$, $r=\dim R\ge2$, $d+r>5$ のとき有限半定値表現を認めないことを示唆する。

関連論文リスト

• A Note on Binary Quadratic Systems and their relation to complexity theory [0.0]
  Q_d$の評価マトロイドの基底集合として$(FF_2)n$を証明します。 また、ホイットニー型符号反転の帰納法を用いて、マトロイドポートの要素から$_1/2n$以下に$_1/2n$をプッシュできる条件のみを示す。
  論文  参考訳（メタデータ） (2026-09-07T17:19:05Z)
• Faster quantum linear system solver beyond the condition number [50.84794327094274]
  線形系の正規化解 $|xrangle$ を生成する2つの量子アルゴリズムを、条件数$=lVert A-1rVert$ に依存しない複雑性を持つ精度 $Ax=| b rangle$ に提示する。 フィルタベースのソルバは非常にシンプルで、実行時プレファクタが適しています。
  論文  参考訳（メタデータ） (2026-07-08T17:49:40Z)
• $\mathsf{P} \neq \mathsf{NP}$: A Non-Relativizing Proof via Quantale Weakness and Geometric Complexity [0.0]
  We work in the weak Quantale $w_Q=K_mathrmpoly(cdotmidcdot)$. ランダムな3ドルCNFをマスキングした効率よくサンプリング可能なアンサンブル$D_m$に対して、スイッチング・バイ・ウェイクネスの正規形式を証明する。
  論文  参考訳（メタデータ） (2025-10-09T21:01:17Z)
• Approximating the operator norm of local Hamiltonians via few quantum states [53.16156504455106]
  複素ヒルベルト空間上で作用するエルミート作用素 $A$ を 2n$ とする。 A$ がパウリ拡大において小さな次数を持つとき、あるいは言い換えれば、$A$ は局所 $n$-量子ハミルトニアンである。 A$ が $d$-local, textiti.e., $deg(A)le d$ であるときは常に、次の離散化型不等式を持つことを示す。
  論文  参考訳（メタデータ） (2025-09-15T14:26:11Z)
• Complexity of mixed Schatten norms of quantum maps [7.182449176083625]
  我々は、空間間の線型写像の混合Schatten $|Phi|_qto p$ノルムの計算の複雑さについて研究する。 Phi$ が完全に正であれば、$q geq p$ のとき、p$ に対して $| Phi |_q が効率的に計算可能であることを示す。
  論文  参考訳（メタデータ） (2025-07-11T07:20:25Z)
• Monogamy of entanglement between cones [43.57338639836868]
  モノガミーは量子論の特徴であるだけでなく、凸錐の一般対の極小テンソル積を特徴づけることを示した。 我々の証明は、アフィン同値まで単純化された生成物の新たな特徴を生かしている。
  論文  参考訳（メタデータ） (2022-06-23T16:23:59Z)
• Low-degree learning and the metric entropy of polynomials [44.99833362998488]
  少なくとも$Omega(sqrtvarepsilon)2dlog n leq log mathsfM(mathscrF_n,d,|cdot|_L,varepsilon)は2辺の推定値$c(1-varepsilon)2dlogを満たす。
  論文  参考訳（メタデータ） (2022-03-17T23:52:08Z)
• 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)

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

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