論文の概要: Computational hardness of estimating quantum entropies via binary entropy bounds

• arxiv url: http://arxiv.org/abs/2601.03734v1
• Date: Wed, 07 Jan 2026 09:25:07 GMT
• ステータス: 翻訳完了
• システム内更新日: 2026-01-09 02:15:23.391813
• Title: Computational hardness of estimating quantum entropies via binary entropy bounds
• Title（参考訳）: 二元エントロピー境界による推定量子エントロピーの計算硬度
• Authors: Yupan Liu,
• Abstract要約: 量子$-Rényi entropy $rm Stt T_q()$を推定する際の計算困難さについて検討する。 すべての正の位数に対して、ランク-$2$の変種が Rank2RényiQEA$_$ と Rank2TsallisQEA$_q$ は $sf BQP$-hard であることを示す。 我々の結果は、異なる順序の$-Rényiあるいは$q$-Tsallis二項エントロピーに関する新しい不等式に基づく還元に由来する。
• 参考スコア（独自算出の注目度）: 0.2538209532048867
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: We investigate the computational hardness of estimating the quantum $α$-Rényi entropy ${\rm S}^{\tt R}_α(ρ) = \frac{\ln {\rm Tr}(ρ^α)}{1-α}$ and the quantum $q$-Tsallis entropy ${\rm S}^{\tt T}_q(ρ) = \frac{1-{\rm Tr}(ρ^q)}{q-1}$, both converging to the von Neumann entropy as the order approaches $1$. The promise problems Quantum $α$-Rényi Entropy Approximation (RényiQEA$_α$) and Quantum $q$-Tsallis Entropy Approximation (TsallisQEA$_q$) ask whether $ {\rm S}^ {\tt R}_α(ρ)$ or ${\rm S}^{\tt T}_q(ρ)$, respectively, is at least $τ_{\tt Y}$ or at most $τ_{\tt N}$, where $τ_{\tt Y} - τ_{\tt N}$ is typically a positive constant. Previous hardness results cover only the von Neumann entropy (order $1$) and some cases of the quantum $q$-Tsallis entropy, while existing approaches do not readily extend to other orders. We establish that for all positive real orders, the rank-$2$ variants Rank2RényiQEA$_α$ and Rank2TsallisQEA$_q$ are ${\sf BQP}$-hard. Combined with prior (rank-dependent) quantum query algorithms in Wang, Guan, Liu, Zhang, and Ying (TIT 2024), Wang, Zhang, and Li (TIT 2024), and Liu and Wang (SODA 2025), our results imply: - For all real orders $α> 0$ and $0 < q \leq 1$, LowRankRényiQEA$_α$ and LowRankTsallisQEA$_q$ are ${\sf BQP}$-complete, where both are restricted versions of RényiQEA$_α$ and TsallisQEA$_q$ with $ρ$ of polynomial rank. - For all real order $q>1$, TsallisQEA$_q$ is ${\sf BQP}$-complete. Our hardness results stem from reductions based on new inequalities relating the $α$-Rényi or $q$-Tsallis binary entropies of different orders, where the reductions differ substantially from previous approaches, and the inequalities are also of independent interest.
• Abstract（参考訳）: 量子 $α$-Rényi entropy ${\rm S}^{\tt R}_α(ρ) = \frac{\ln {\rm Tr}(ρ^α)}{1-α}$ と量子 $q$-Tsallis entropy ${\rm S}^{\tt T}_q(ρ) = \frac{1-{\rm Tr}(ρ^q)}{q-1}$ を推定する計算困難さについて検討する。 約束問題Quantum $α$-Rényi Entropy Approximation (RényiQEA$_α$)とQuantum $q$-Tsallis Entropy Approximation (TsallisQEA$_q$)は、$ {\rm S}^ {\tt R}_α(ρ)$か${\rm S}^{\tt T}_q(ρ)$が少なくとも$τ_{\t Y}$か、少なくとも$τ_{\t N}$であり、$τ_{\t Y} - τ_{\t N}$は通常正の定数であるかどうかを問う。 それまでの硬さの結果はフォン・ノイマンエントロピー(位数1ドル)と量子$q$-ツァリスエントロピー(英語版)のみをカバーするが、既存のアプローチは容易に他の順序に拡張できない。 すべての正の位数に対して、ランク-$2$の変種が Rank2RényiQEA$_α$ と Rank2TsallisQEA$_q$ は ${\sf BQP}$-hard であることを示す。 Wang, Guan, Liu, Zhang, and Ying (TIT 2024), Wang, Zhang, and Li (TIT 2024), and Liu and Wang (SODA 2025) の以前の(ランク依存の)量子クエリアルゴリズムと組み合わせることで、以下の結果が得られる: - すべての実位数$α> 0$と$0 < q \leq 1$, LowRankRényiQEA$_α$とLowRankTsallisQEA$_q$は${\sf BQP}$-完全で、RényiQEA$_α$とTsallisQEA$_q$は$ρ$である。 -すべての実順序$q>1$に対して、TsallisQEA$_q$は${\sf BQP}$-completeである。 我々の硬さの結果は、異なる順序の$α$-Rényiまたは$q$-Tsallis二項エントロピーに関する新しい不等式に基づく還元に起因している。

関連論文リスト

• Spectral Gaps with Quantum Counting Queries and Oblivious State Preparation [47.600794349481966]
  本研究では、量子ビットの対数数を用いて、加算誤差$epsilonDelta_k$まで値を近似する量子アルゴリズムを提案する。 この分析における重要な技術的ステップは、適切なランダム初期状態の準備であり、最終的には閾値よりも小さい固有値の数を効率的に数えることができる。
  論文  参考訳（メタデータ） (2025-08-28T17:04:18Z)
• 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 [11.63482880743131]
  量子状態のトレースを推定する計算複雑性を、$n$-qubit混合量子状態$rho$に対して$texttr(rhoq)$で調べる。 我々の高速化は、正のパワー関数の計算可能な一様近似を量子特異値変換に効率よく導入することで達成される。
  論文  参考訳（メタデータ） (2024-10-17T13:57:13Z)
• Optimal Query Complexities for Dynamic Trace Estimation [59.032228008383484]
  我々は,行列がゆっくりと変化している動的環境において,正確なトレース推定に必要な行列ベクトルクエリ数を最小化する問題を考える。 我々は、$delta$失敗確率で$epsilon$エラーまで、すべての$m$トレースを同時に推定する新しいバイナリツリー要約手順を提供する。 我々の下界(1)は、静的な設定においてもフロベニウスノルム誤差を持つ行列ベクトル積モデルにおけるハッチンソン推定子の第一の厳密な境界を与え、(2)動的トレース推定のための最初の無条件下界を与える。
  論文  参考訳（メタデータ） (2022-09-30T04:15:44Z)
• 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)
• Private Stochastic Convex Optimization: Optimal Rates in $\ell_1$ Geometry [69.24618367447101]
  対数要因まで $(varepsilon,delta)$-differently private の最適過剰人口損失は $sqrtlog(d)/n + sqrtd/varepsilon n.$ です。 損失関数がさらなる滑らかさの仮定を満たすとき、余剰損失は$sqrtlog(d)/n + (log(d)/varepsilon n)2/3で上界(対数因子まで)であることが示される。
  論文  参考訳（メタデータ） (2021-03-02T06:53:44Z)
• 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)

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

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