論文の概要: Lower Bounds on Relative Error Quantum Compression and Classical Shadows

• arxiv url: http://arxiv.org/abs/2506.21345v1
• Date: Thu, 26 Jun 2025 14:58:23 GMT
• ステータス: 翻訳完了
• システム内更新日: 2025-06-27 19:53:10.145265
• Title: Lower Bounds on Relative Error Quantum Compression and Classical Shadows
• Title（参考訳）: 相対誤差量子圧縮と古典影の下位境界
• Authors: Kaushik Sankar,
• Abstract要約: タスクは、量子学習理論においてよく知られた古典的シャドウ問題の純粋状態の場合の、完全に古典的なバージョンと考えることができる。 まず、通信問題の相対誤差バージョンを検討し、一方通行のランダム化された古典的通信において、$Omega(sqrt2n)$の低い境界を証明した。 この下界は、すべての可観測体の集合だけでなく、パウリ可観測体のクラスに制限された場合にも成り立つことを示す。
• 参考スコア（独自算出の注目度）: 0.0
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: We study the question of how much classical communication is needed when Alice is given a classical description of a quantum state $|\psi\rangle$ for Bob to recover any expectation value $\langle \psi | M |\psi\rangle$ given an observable $M$ with $M$ Hermitian and $||M||_{\text{op}} \leq 1$. This task, whose study was initiated by Raz (ACM 1999) and more recently investigated by Gosset and Smolin (TQC 2019), can be thought of as a fully classical version of the pure state case of the well-known classical shadows problem in quantum learning theory. We show how the hardness of these two seemingly distinct problems are connected. We first consider the relative error version of the communication question and prove a lower bound of $\Omega(\sqrt{2^{n}}\epsilon^{-2})$ on the one-way randomized classical communication, improving upon an additive error lower bound of $\Omega(\sqrt{2^{n}})$ as shown by Gosset and Smolin. Notably, we show that this lower bound holds not only for the set of all observables but also when restricted to just the class of Pauli observables. This fact implies a $\Omega(\sqrt{2^{n}})$ versus $O(\text{poly}(n))$ separation in the compression size between the relative and additive error settings for non-adaptive Pauli classical shadows with classical memory. Extending this framework, we prove randomized communication lower bounds for other relative error one-way classical communication tasks: an $\Omega(2^{n}\epsilon^{-2})$ lower bound when instead Alice is given an observable and Bob is given a quantum state and they are asked to estimate the expectation value, an $\Omega(\sqrt{n}\epsilon^{-2})$ lower bound when restricted to Paulis, and an $\Omega(\sqrt{2^{n}}\epsilon^{-2})$ lower bound when Alice and Bob are both given quantum states and asked to estimate the inner product.
• Abstract（参考訳）: Alice が量子状態 $|\psi\rangle$ の古典的な記述を与えられたとき、どれだけの古典的なコミュニケーションが必要なのかという問題について、Bob が期待値 $\langle \psi | M |\psi\rangle$ を$M$ Hermitian と $||M|||_{\text{op}} \leq 1$ で観測可能な$M$ を与える。 このタスクは、Raz (ACM 1999) によって始められ、最近では Gosset と Smolin (TQC 2019) によって研究され、量子学習理論においてよく知られた古典的シャドウ問題における純粋状態の完全な古典的なバージョンと考えることができる。 これら2つの明らかな問題の難しさがどのように結びついているかを示す。 まず、通信問題の相対誤差バージョンを検討し、一方のランダム化された古典的通信に対して$\Omega(\sqrt{2^{n}}\epsilon^{-2})$の下位境界を証明し、GossetとSmolinが示すように、加算誤差の下限を$\Omega(\sqrt{2^{n}})$で改善する。 特に、この下界がすべての可観測体の集合だけでなく、パウリ可観測体のクラスに制限されている場合にも成り立つことを示す。 この事実は、$Omega(\sqrt{2^{n}})$ vs $O(\text{poly}(n))$ 古典記憶を持つ非適応的なパウリの古典的影に対する相対的および加法的エラー設定の間の圧縮サイズを分離することを意味する。 この枠組みを拡張して、他の相対的誤りに対してランダム化された通信の下限を証明している: a $\Omega(2^{n}\epsilon^{-2})$ lowerbound when instead Alice is given an observable and Bob is given a quantum state and they are asked to estimates the expectation value, a $\Omega(\sqrt{n}\epsilon^{-2})$ lower bound when limited to Paulis, and a $\Omega(\sqrt{2^{n}}\epsilon^{-2})$ lower bound when Alice and Bob are both given quantum state and asked to estimate the inner product。

関連論文リスト

• On the sample complexity of purity and inner product estimation [8.94496959777308]
  本研究では,タスクの量子純度推定と内部積推定の複雑さについて検討する。 純度推定では、未知の量子状態$rho$の$tr(rho2)$を加算誤差$epsilon$に見積もる。 量子内積推定では、アリスとボブは$tr(rhosigma)$を加算誤差$epsilon$未知の量子状態$rho$と$sigma$のコピーとして推定する。
  論文  参考訳（メタデータ） (2024-10-16T16:17:21Z)
• Distributed inner product estimation with limited quantum communication [3.729242965449096]
  量子通信が制限された場合, 内部積の分散推定の課題を考察する。 我々は、$k=Theta(sqrt2n-q)$コピーが本質的に必要であり、このタスクに十分であることを示す。 また、任意のエルミート $M$ に対して $|langle psi|M|phirangle|2$ を推定することを考える。
  論文  参考訳（メタデータ） (2024-10-16T15:46:59Z)
• Quantum advantage in zero-error function computation with side information [10.0060346233449]
  本稿では,サイド情報を用いたゼロエラー関数計算の問題点について考察する。 Alice and Bob has correlation source $X,Y$ with joint p.m.f. $p_XY(cdot, cdot)$. Bob want to compute $f(X,Y)$ with zero error。
  論文  参考訳（メタデータ） (2024-02-02T16:41:36Z)
• Unbounded Quantum Advantage in Communication with Minimal Input Scaling [0.0]
  一般の硬貨を使わずに関係の再構築を行う場合, 量子的に非有界な利点を示す。 また、このタスクの半デバイス非依存なディメンションの目撃や、ミューチュアル・アンバイアスド・ベースの検出への応用についても強調する。
  論文  参考訳（メタデータ） (2023-05-17T16:58:05Z)
• Exponential Separation between Quantum and Classical Ordered Binary Decision Diagrams, Reordering Method and Hierarchies [68.93512627479197]
  量子順序付き二項決定図($OBDD$)モデルについて検討する。 入力変数の任意の順序で、OBDDの下位境界と上位境界を証明します。 read$k$-times Ordered Binary Decision Diagrams (k$-OBDD$)の幅の階層を拡張します。
  論文  参考訳（メタデータ） (2022-04-22T12:37:56Z)
• A lower bound on the space overhead of fault-tolerant quantum computation [51.723084600243716]
  しきい値定理は、フォールトトレラント量子計算の理論における基本的な結果である。 振幅雑音を伴う耐故障性量子計算の最大長に対する指数的上限を証明した。
  論文  参考訳（メタデータ） (2022-01-31T22:19:49Z)
• 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)
• Lower Bounds for XOR of Forrelations [7.510385608531827]
  我々は Forrelation 関数の独立コピー $k$ の XOR について検討する。 また、任意の準ポリノミカルサイズの定数深さ回路が、ランダムな推測に対して準ポリノミカルに小さな優位性を持つことを示す。
  論文  参考訳（メタデータ） (2020-07-07T17:05:09Z)
• Quantum Communication Complexity of Distribution Testing [114.31181206328276]
  2人のプレーヤーが1つのディストリビューションから$t$のサンプルを受け取ります。 目標は、2つの分布が等しいか、または$epsilon$-far であるかどうかを決定することである。 この問題の量子通信複雑性が$tildeO$(tepsilon2)$ qubitsであることを示す。
  論文  参考訳（メタデータ） (2020-06-26T09:05:58Z)
• Quantum Coupon Collector [62.58209964224025]
  我々は、$k$-要素集合$Ssubseteq[n]$が、その要素の一様重ね合わせ$|Srangleからいかに効率的に学習できるかを研究する。 我々は、$k$と$n$ごとに必要となる量子サンプルの数に厳密な制限を与え、効率的な量子学習アルゴリズムを与える。
  論文  参考訳（メタデータ） (2020-02-18T16:14:55Z)

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

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