論文の概要: Complexity and Applications of Nearest Stabilizer Product State Problems

• arxiv url: http://arxiv.org/abs/2610.02037v1
• Date: Thu, 01 Oct 2026 16:50:13 GMT
• ステータス: 翻訳完了
• システム内更新日: 2026-10-03 01:19:24.311741
• Title: Complexity and Applications of Nearest Stabilizer Product State Problems
• Title（参考訳）: 近距離安定化器製品状態問題の複雑さと応用
• Abstract要約: この問題に対する解決策は、様々な設定で有用であることを示す。 我々は、この最も近い安定化製品状態問題の完全な複雑性分類を与える。
• 参考スコア（独自算出の注目度）: 1.8352113484137627
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: Consider the following optimization problem over stabilizer product states: given an $n$-qubit stabilizer state $\left|ψ\right\rangle$ and a set of single-qubit stabilizer states $S$, maximize $\left|\langle ψ| φ_1, \ldots, φ_n \rangle\right|^2$ over single-qubit stabilizer states $\left|φ_i\right\rangle \in S$. By varying the set $S$, we show that solutions to this problem can be useful in a variety of settings: tighter runtime bounds for certain classical simulation algorithms; measures of entanglement; and the complexity of low-rank matrix completion. Moreover, we give a complete complexity classification of this nearest stabilizer product state problem. After accounting for the symmetries in the Clifford group, there are $9$ distinct possible sets $S$, and we show that all but the two simplest of these are $\NP$-complete.
• Abstract（参考訳）: 安定化子状態に対する以下の最適化問題を考える:$n$-qubit 安定化子状態 $\left|\\right\rangle$ と単量子安定化子状態 $S$, max $\left|\langle >| φ_1, \ldots, φ_n \rangle\right|^2$ を単量子安定化子状態 $\left|φ_i\right\rangle \in S$ で与えられる。 S$のセットを変えることで、この問題に対する解決策は、ある種の古典的シミュレーションアルゴリズムの厳密なランタイム境界、絡み合いの尺度、低ランク行列補完の複雑さなど、様々な設定で有用であることが示される。 さらに、この最寄りの安定化製品状態問題の完全な複雑性分類を与える。 クリフォード群の対称性を説明すると、9$の異なる集合が$S$であり、最も単純な2つの集合を除いて全て$\NP$-完全であることを示す。

関連論文リスト

• The Sharp Tail of Uniform Stability [1.14219428942199]
  均一な安定性は、あるトレーニング例がテストポイントでの損失をどの程度変えられるかを制御する。 新しい対数自由な上界は、$[0,L]$の損失を持つ$$一様安定なアルゴリズムが、最大$O left(log(1/) +Lsqrtfraclog (1/)nright)$の一般化ギャップを持つことを示している。
  論文  参考訳（メタデータ） (2026-08-25T05:53:31Z)
• Faster quantum linear system solver beyond the condition number [50.84794327094274]
  線形系の正規化解 $|xrangle$ を生成する2つの量子アルゴリズムを、条件数$=lVert A-1rVert$ に依存しない複雑性を持つ精度 $Ax=| b rangle$ に提示する。 フィルタベースのソルバは非常にシンプルで、実行時プレファクタが適しています。
  論文  参考訳（メタデータ） (2026-07-08T17:49:40Z)
• Discrete Double-Bracket Flows for Isotropic-Noise Invariant Eigendecomposition [7.186083931122418]
  本研究では,行列ベクトル積 (MVP) のオラクルによる行列フリー固有分解について検討した。 標準的な近似法では、安定性を$|C_k|$に結合する固定ステップを使用するか、あるいは更新の消滅によって遅くなる適応ステップを使用する。 対角化目標と入力-状態安定性解析のための厳密なサドルと、トレースフリーな摂動の下での複雑さのスケーリングを$O(|C_e|2 / (2))$とすることで、グローバル収束を確立する。
  論文  参考訳（メタデータ） (2026-02-14T13:09:29Z)
• Near-Optimal Convergence of Accelerated Gradient Methods under Generalized and $(L_0, L_1)$-Smoothness [57.93371273485736]
  我々は、最近提案された$ell$-smoothness条件$|nabla2f(x)|| le ellleft(||nabla f(x)||right),$$$L$-smoothnessと$(L_0,L_1)$-smoothnessを一般化する関数を持つ凸最適化問題の一階法について検討する。
  論文  参考訳（メタデータ） (2025-08-09T08:28:06Z)
• Tolerant Testing of Stabilizer States with Mixed State Inputs [0.4604003661048266]
  特に、混合状態入力を受け入れる最初のアルゴリズムを与える。 我々のアルゴリズムは、サンプル複雑性 $textpoly (1/varepsilon)$と時間複雑性 $cdot textpoly (1/varepsilon)$の2つのケースを区別する。
  論文  参考訳（メタデータ） (2024-11-13T16:51:03Z)
• Optimal Query Complexities for Dynamic Trace Estimation [59.032228008383484]
  我々は,行列がゆっくりと変化している動的環境において,正確なトレース推定に必要な行列ベクトルクエリ数を最小化する問題を考える。 我々は、$delta$失敗確率で$epsilon$エラーまで、すべての$m$トレースを同時に推定する新しいバイナリツリー要約手順を提供する。 我々の下界(1)は、静的な設定においてもフロベニウスノルム誤差を持つ行列ベクトル積モデルにおけるハッチンソン推定子の第一の厳密な境界を与え、(2)動的トレース推定のための最初の無条件下界を与える。
  論文  参考訳（メタデータ） (2022-09-30T04:15:44Z)
• Lower Bounds on Stabilizer Rank [3.265773263570237]
  十分小さな定数$deltaの場合、それらの状態に対して$$-closeの任意の状態の安定化ランクが$Omega(sqrtn/log n)$であることを証明する。 これは、近似安定化器ランクに対する最初の非自明な下界である。
  論文  参考訳（メタデータ） (2021-06-06T19:27:51Z)
• An Optimal Separation of Randomized and Quantum Query Complexity [67.19751155411075]
  すべての決定木に対して、与えられた順序 $ellsqrtbinomdell (1+log n)ell-1,$ sum to at least $cellsqrtbinomdell (1+log n)ell-1,$ where $n$ is the number of variables, $d$ is the tree depth, $c>0$ is a absolute constant。
  論文  参考訳（メタデータ） (2020-08-24T06:50:57Z)
• Streaming Complexity of SVMs [110.63976030971106]
  本稿では,ストリーミングモデルにおけるバイアス正規化SVM問題を解く際の空間複雑性について検討する。 両方の問題に対して、$frac1lambdaepsilon$の次元に対して、$frac1lambdaepsilon$よりも空間的に小さいストリーミングアルゴリズムを得ることができることを示す。
  論文  参考訳（メタデータ） (2020-07-07T17:10:00Z)
• Second-Order Information in Non-Convex Stochastic Optimization: Power and Limitations [54.42518331209581]
  私たちは発見するアルゴリズムを見つけます。 epsilon$-approximate stationary point ($|nabla F(x)|le epsilon$) using $(epsilon,gamma)$surimateランダムランダムポイント。 ここでの私たちの下限は、ノイズのないケースでも新規です。
  論文  参考訳（メタデータ） (2020-06-24T04:41:43Z)

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

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