論文の概要: Improved Sample Upper and Lower Bounds for Trace Estimation of Quantum State Powers

• arxiv url: http://arxiv.org/abs/2505.09563v1
• Date: Wed, 14 May 2025 17:06:33 GMT
• ステータス: 翻訳完了
• システム内更新日: 2025-05-15 21:44:09.540413
• Title: Improved Sample Upper and Lower Bounds for Trace Estimation of Quantum State Powers
• Title（参考訳）: 量子状態電力のトレース推定のための上・下境界の改善
• Authors: Kean Chen, Qisheng Wang,
• Abstract要約: 上界と下界の両方で$operatornametr(rhoq)$を推定することで、サンプルの複雑さを大幅に改善する。 我々の上界は、弱いシュアサンプリングに基づく(プラグインでない)量子推定器によって得られる。
• 参考スコア（独自算出の注目度）: 9.136389487369117
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: As often emerges in various basic quantum properties such as entropy, the trace of quantum state powers $\operatorname{tr}(\rho^q)$ has attracted a lot of attention. The recent work of Liu and Wang (SODA 2025) showed that $\operatorname{tr}(\rho^q)$ can be estimated to within additive error $\varepsilon$ with a dimension-independent sample complexity of $\widetilde O(1/\varepsilon^{3+\frac{2}{q-1}})$ for any constant $q > 1$, where only an $\Omega(1/\varepsilon)$ lower bound was given. In this paper, we significantly improve the sample complexity of estimating $\operatorname{tr}(\rho^q)$ in both the upper and lower bounds. In particular: - For $q > 2$, we settle the sample complexity with matching upper and lower bounds $\widetilde \Theta(1/\varepsilon^2)$. - For $1 < q < 2$, we provide an upper bound $\widetilde O(1/\varepsilon^{\frac{2}{q-1}})$, with a lower bound $\Omega(1/\varepsilon^{\max\{\frac{1}{q-1}, 2\}})$ for dimension-independent estimators, implying there is only room for a quadratic improvement. Our upper bounds are obtained by (non-plug-in) quantum estimators based on weak Schur sampling, in sharp contrast to the prior approach based on quantum singular value transformation and samplizer.
• Abstract（参考訳）: エントロピーのような様々な基本的な量子特性にしばしば現れるように、量子状態のパワーの痕跡$\operatorname{tr}(\rho^q)$は多くの注目を集めている。 Liu and Wang (SODA 2025) の最近の研究によると、$\operatorname{tr}(\rho^q)$は、任意の定数$q > 1$に対して$\widetilde O(1/\varepsilon^{3+\frac{2}{q-1}})$の次元非依存なサンプル複雑性を持つ加法誤差$\varepsilon$と推定できる。 本稿では,上界と下界の両方で$\operatorname{tr}(\rho^q)$を推定する際のサンプルの複雑さを著しく改善する。 特に、$q > 2$ の場合、上界と下界が一致するサンプル複雑性を $\widetilde \Theta(1/\varepsilon^2)$ で解決する。 - 1 < q < 2$ に対して、上界$\widetilde O(1/\varepsilon^{\frac{2}{q-1}})$ を、下界$\Omega(1/\varepsilon^{\max\{\frac{1}{q-1}, 2\}})$ を、次元に依存しない推定器に対して与える。 我々の上界は、弱いシュールサンプリングに基づく(非プラグイン)量子推定器によって得られ、量子特異値変換とサンプリング器に基づく以前のアプローチとは対照的である。

関連論文リスト

• On estimating the quantum $\ell_α$ distance [2.637436382971936]
  時間複雑性を持つ$mathrmT_alpha(rho_0,rho_1)$に対する効率的なランク独立量子推定器を開発した。 我々のアルゴリズムは、量子状態微分可能性問題の計算複雑性の2分法をSchatten $alpha$-norm (QSD$_alpha$)で明らかにしている。 この硬さは、1leq α leq infty$ の量子 $ell_alpha$ 距離に対する新しい階数依存の不等式に基づく還元の結果に続く。
  論文  参考訳（メタデータ） (2025-05-01T11:15:20Z)
• On estimating the trace of quantum state powers [2.637436382971936]
  量子状態のトレースを推定する計算複雑性を、$n$-qubit混合量子状態$rho$に対して$texttr(rhoq)$で調べる。 我々の高速化は、正のパワー関数の計算可能な一様近似を量子特異値変換に効率よく導入することで達成される。
  論文  参考訳（メタデータ） (2024-10-17T13:57:13Z)
• Coresets for Multiple $\ell_p$ Regression [47.790126028106734]
  サイズ $tilde O(varepsilon-2d)$ for $p2$ と $tilde O(varepsilon-pdp/2)$ for $p>2$ のコアセットを構築します。 1p2$の場合、すべての行列は$tilde O(varepsilon-1k)$行のサブセットを持ち、$(varepsilon-1k)$-a optimal $k$-dimensional subspace for $ell_p$ subspace approximationである。
  論文  参考訳（メタデータ） (2024-06-04T15:50:42Z)
• Time-Efficient Quantum Entropy Estimator via Samplizer [7.319050391449301]
  量子状態のエントロピーを推定することは、量子情報の基本的な問題である。 我々は、フォン・ノイマンエントロピー $S(rho)$ と R'enyi entropy $S_alpha(rho)$ を$N$次元量子状態 $rho として推定するための時間効率のよい量子アプローチを導入する。
  論文  参考訳（メタデータ） (2024-01-18T12:50:20Z)
• Optimal Query Complexities for Dynamic Trace Estimation [59.032228008383484]
  我々は,行列がゆっくりと変化している動的環境において,正確なトレース推定に必要な行列ベクトルクエリ数を最小化する問題を考える。 我々は、$delta$失敗確率で$epsilon$エラーまで、すべての$m$トレースを同時に推定する新しいバイナリツリー要約手順を提供する。 我々の下界(1)は、静的な設定においてもフロベニウスノルム誤差を持つ行列ベクトル積モデルにおけるハッチンソン推定子の第一の厳密な境界を与え、(2)動的トレース推定のための最初の無条件下界を与える。
  論文  参考訳（メタデータ） (2022-09-30T04:15:44Z)
• Enlarging the notion of additivity of resource quantifiers [62.997667081978825]
  量子状態 $varrho$ と量子化器 $cal E(varrho) が与えられたとき、$cal E(varrhootimes N)$ を決定するのは難しい。 本研究では, ある球対称状態の1発の蒸留可能な絡み合いを, このような拡張付加性によって定量的に近似できることを示す。
  論文  参考訳（メタデータ） (2022-07-31T00:23:10Z)
• 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)
• Improved quantum data analysis [1.8416014644193066]
  我々は、$O(log2 m)/epsilon2)$$$d$次元状態のサンプルのみを必要とする量子"Threshold Search"アルゴリズムを提供する。 また, $tildeO((log3 m)/epsilon2)$サンプルを用いた仮説選択法も提案する。
  論文  参考訳（メタデータ） (2020-11-22T01:22:37Z)
• 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)
• Model-Free Reinforcement Learning: from Clipped Pseudo-Regret to Sample Complexity [59.34067736545355]
  S$状態、$A$アクション、割引係数$gamma in (0,1)$、近似しきい値$epsilon > 0$の MDP が与えられた場合、$epsilon$-Optimal Policy を学ぶためのモデルなしアルゴリズムを提供する。 十分小さな$epsilon$の場合、サンプルの複雑さで改良されたアルゴリズムを示す。
  論文  参考訳（メタデータ） (2020-06-06T13:34:41Z)

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

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