論文の概要: Verification Complexity and Extension of Classical Shadows

• arxiv url: http://arxiv.org/abs/2609.40107v1
• Date: Wed, 30 Sep 2026 16:39:25 GMT
• ステータス: 翻訳完了
• システム内更新日: 2026-10-01 18:57:28.094164
• Title: Verification Complexity and Extension of Classical Shadows
• Title（参考訳）: 古典的影の検証複雑性と拡張
• Abstract要約: 1)$S$が与えられたら、本当の$n$-qubit状態から$S$が来たことを有効に検証できるだろうか? 我々は、CSVが置換陰影、実数、フェルミオン、ボソニック陰影に対するQMAハード、および観測可能な族がすべての$n$キュービットパウリ弦からなるとき、coNPハードとQMAハードの両方に効率よく解けることを示した。
• 参考スコア（独自算出の注目度）: 0.8351309125845637
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: Classical shadows are an influential framework for compressing copies of a given quantum state $ρ$ into classical data $S$, enabling many properties of $ρ$ to be predicted from relatively few copies. In this work, we study two natural questions involving shadows: (1) Given $S$, when can one efficiently verify that $S$ came from a genuine $n$-qubit state? This is called the Classical Shadow Validity (CSV) problem, introduced by Karaiskos, Rudolph, Meyer, Eisert, and Gharibian [ICALP 2026]. (2) Given $S$ that allows one to capture 2-local properties of $ρ$, can one fake or spoof a shadow $S'$ which predicts 3-local properties of some state? For (1), we show CSV is efficiently solvable for permutation-invariant shadows, QMA-hard for real, fermionic, and bosonic shadows, and both coNP-hard and QMA-hard when the observable family consists of all $n$-qubit Pauli strings. A result of independent interest along the way is a new upper bound qc-$Σ_2$ $\subseteq$ $\mathrm{P}^{\mathrm{PP}}$, where qc-$Σ_2$ is a quantum analogue of the second level of the polynomial hierarchy in which the first proof is quantum. For (2), we show intractability: Given the 2-local marginals $S$ of a quantum state $ρ$, estimating the 3-local marginals of $ρ$ is intractable unless QCMA $\subseteq$ BPP, even if the state $ρ$ is the unique state consistent with $S$.
• Abstract（参考訳）: 古典的影は、与えられた量子状態$ρ$のコピーを古典的データ$S$に圧縮するための影響力のあるフレームワークであり、比較的少数のコピーから$ρ$の多くの特性を予測できる。 本研究では,シャドーに関する2つの自然問題について検討する。(1)$S$が与えられたとき,真の$n$-qubit状態から$S$が得られたことを有効に検証できるのか? これは、Karaiskos、Rudolph、Meyer、Eisert、Gharibian (ICALP 2026)によって導入された古典的影の妥当性問題と呼ばれる。 (2)$S$が$ρ$の2つのローカルプロパティをキャプチャできるので、ある状態の3つのローカルプロパティを予測するシャドウ$S'$を偽造または偽造できるだろうか? 1) の場合、CSV は置換不変影、実影、フェルミオン影、ボソニック影の QMA-hard 、観測可能な族がすべての$n$-qubit Pauli 弦からなる場合の coNP-hard および QMA-hard に対して効率的に解けることを示す。 途中の独立な関心の結果は、新しい上界 qc-$Σ_2$$\subseteq$$\mathrm{P}^{\mathrm{PP}}$, ここで qc-$Σ_2$ は、第一の証明が量子である多項式階層の第2レベルの量子アナログである。 量子状態 $ρ$ の 2-局所剰余項 $S$ が与えられたとき、QCMA$\subseteq$ BPP が QCMA$\subseteq$ BPP でない限り、$ρ$ の 3-局所余項を推定できる。

関連論文リスト

• On quantum interactive proofs with a laconic prover [0.8594140167290097]
  クラス $sf QIP_elltext-rm bit(2)$, $ell$ は証明者の応答の長さである。 QSD$[a,b]$(および$sf QIP_elltext-rm bit(2)$)が$sf QSZK$のとき、$a(n)-b(n)geq 1/O(log n)$のとき、$sf QIP_elltext-rm bit(2)$)が$sf QSZK$であり、これを$sf QIP_からの回答圧縮と組み合わせる。
  論文  参考訳（メタデータ） (2026-09-30T10:54:20Z)
• Exponential lower bounds for low-degree strategies in position-based quantum cryptography [0.764671395172401]
  非局所量子計算 (NLQC) は、2つの遠隔操作者による2部単位のU_AB$の実装に基づいている。 ユニタリな$U_AB$が存在するかどうかを知ることは、大きなオープンな問題である。 このような指数的下界は、位置ベースの量子暗号のセキュリティに不可欠である。
  論文  参考訳（メタデータ） (2026-09-28T16:43:48Z)
• Contextuality from the Projector Overlap Matrix [0.6372261626436676]
  我々は、Kochen-Speckerコンテキストのいくつかの既知の指標を単一の射影幾何学的フレームワークに配置する。 Tcal_ij = d-1tr[(hat P_i hat Q_j)2]$, $hat P_i$ と $hat Q_j$ は、2つの互換性のある可観測対の合同固有空間射影である。 KCBSペンタゴンのスピン-$1$実現において、各文脈における共有$m_s=0$固有状態が$c_MU = であることを示す。
  論文  参考訳（メタデータ） (2026-04-26T21:56:11Z)
• 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)
• Beyond the Berry Phase: Extrinsic Geometry of Quantum States [77.34726150561087]
  状態の量子多様体のすべての性質がゲージ不変のバーグマンによって完全に記述されることを示す。 偏光理論への我々の結果の即時適用について述べる。
  論文  参考訳（メタデータ） (2022-05-30T18:01:34Z)
• Testing matrix product states [5.225550006603552]
  未知の状態$|psirangle$が特性試験モデルにおける行列積状態(MPS)かどうかをテストする。 MPS(英: MPS)は、量子多体系の研究で生じる物理関連量子状態のクラスである。
  論文  参考訳（メタデータ） (2022-01-05T21:10:50Z)
• 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)
• Quantum Coupon Collector [62.58209964224025]
  我々は、$k$-要素集合$Ssubseteq[n]$が、その要素の一様重ね合わせ$|Srangleからいかに効率的に学習できるかを研究する。 我々は、$k$と$n$ごとに必要となる量子サンプルの数に厳密な制限を与え、効率的な量子学習アルゴリズムを与える。
  論文  参考訳（メタデータ） (2020-02-18T16:14:55Z)
• Tight Quantum Lower Bound for Approximate Counting with Quantum States [49.6558487240078]
  Aaronson, Kothari, Kretschmer, Thaler (2020) が考える数え上げ問題の次の変種に対する厳密な下界を証明する。 このタスクは、入力セット$xsubseteq [n]$が$k$か$k'=(1+varepsilon)k$であるかどうかを識別する。
  論文  参考訳（メタデータ） (2020-02-17T10:53:50Z)

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

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