論文の概要: Dequantization and Hardness of Spectral Sum Estimation

• arxiv url: http://arxiv.org/abs/2509.20183v1
• Date: Wed, 24 Sep 2025 14:44:53 GMT
• ステータス: 翻訳完了
• システム内更新日: 2025-09-25 20:53:19.855368
• Title: Dequantization and Hardness of Spectral Sum Estimation
• Title（参考訳）: スペクトルサム推定の定式化と硬度化
• Authors: Roman Edenhofer, Atsuya Hasegawa, François Le Gall,
• Abstract要約: 対数行列式などの行列のスペクトル和を推定するための新しい定式化と硬度結果を与える。 古典的な上界を$mathsfDQC1$-completenessで補い、特定のスペクトル和を推定する。
• 参考スコア（独自算出の注目度）: 1.0323063834827415
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: We give new dequantization and hardness results for estimating spectral sums of matrices, such as the log-determinant. Recent quantum algorithms have demonstrated that the logarithm of the determinant of sparse, well-conditioned, positive matrices can be approximated to $\varepsilon$-relative accuracy in time polylogarithmic in the dimension $N$, specifically in time $\mathrm{poly}(\mathrm{log}(N), s, \kappa, 1/\varepsilon)$, where $s$ is the sparsity and $\kappa$ the condition number of the input matrix. We provide a simple dequantization of these techniques that preserves the polylogarithmic dependence on the dimension. Our classical algorithm runs in time $\mathrm{polylog}(N)\cdot s^{O(\sqrt{\kappa}\log \kappa/\varepsilon)}$ which constitutes an exponential improvement over previous classical algorithms in certain parameter regimes. We complement our classical upper bound with $\mathsf{DQC1}$-completeness results for estimating specific spectral sums such as the trace of the inverse and the trace of matrix powers for log-local Hamiltonians, with parameter scalings analogous to those of known quantum algorithms. Assuming $\mathsf{BPP}\subsetneq\mathsf{DQC1}$, this rules out classical algorithms with the same scalings. It also resolves a main open problem of Cade and Montanaro (TQC 2018) concerning the complexity of Schatten-$p$ norm estimation. We further analyze a block-encoding input model, where instead of a classical description of a sparse matrix, we are given a block-encoding of it. We show $\mathsf{DQC}1$-completeness in a very general way in this model for estimating $\mathrm{tr}[f(A)]$ whenever $f$ and $f^{-1}$ are sufficiently smooth. We conclude our work with $\mathsf{BQP}$-hardness and $\mathsf{PP}$-completeness results for high-accuracy log-determinant estimation.
• Abstract（参考訳）: 対数行列式などの行列のスペクトル和を推定するための新しい定式化と硬度化結果を与える。 最近の量子アルゴリズムでは、スパース行列式の対数は、よく条件付きで正の行列の対数として$\varepsilon$-relative accuracy in time polylogarithmic in the dimension $N$, especially in time $\mathrm{poly}(\mathrm{log}(N), s, \kappa, 1/\varepsilon)$, where $s$ is the sparsity and $\kappa$ the condition number of the input matrix。 我々はこれらの手法の簡易な定式化を行い、次元に対する多対数依存を保存する。 我々の古典的アルゴリズムは時間$\mathrm{polylog}(N)\cdot s^{O(\sqrt{\kappa}\log \kappa/\varepsilon)}$で実行されます。 古典的な上界を$\mathsf{DQC1}$-completenessの結果で補完し、逆のトレースや対数局所ハミルトニアンの行列パワーのトレースといった特定のスペクトル和を推定し、パラメータスケーリングは既知の量子アルゴリズムと類似する。 $\mathsf{BPP}\subsetneq\mathsf{DQC1}$と仮定すると、これは同じスケーリングで古典的なアルゴリズムを除外する。 また、Schatten-$p$ノルム推定の複雑さに関して、Cade and Montanaro (TQC 2018) の主要な開問題を解決している。 さらに、スパース行列の古典的な記述の代わりにブロックエンコードを行うブロックエンコード入力モデルを解析する。 このモデルでは、$\mathsf{DQC}1$-完全性を非常に一般的な方法で示し、$\mathrm{tr}[f(A)]$ every $f$ および $f^{-1}$ が十分に滑らかであることを推定する。 我々は、高精度な対数決定式推定のための $\mathsf{BQP}$-hardness と $\mathsf{PP}$-completeness の結果を結論付けている。

関連論文リスト

• Spectral Gaps with Quantum Counting Queries and Oblivious State Preparation [47.600794349481966]
  本研究では、量子ビットの対数数を用いて、加算誤差$epsilonDelta_k$まで値を近似する量子アルゴリズムを提案する。 この分析における重要な技術的ステップは、適切なランダム初期状態の準備であり、最終的には閾値よりも小さい固有値の数を効率的に数えることができる。
  論文  参考訳（メタデータ） (2025-08-28T17:04:18Z)
• Quantum algorithm for the gradient of a logarithm-determinant [0.0]
  スパースランク入力演算子の逆を効率的に決定することができる。 このアルゴリズムは、完全に誤り訂正された量子コンピュータのために想定されている。 このアルゴリズムがカーネルベースの量子機械学習にどのように使えるかについて議論する。
  論文  参考訳（メタデータ） (2025-01-16T09:39:31Z)
• Fast and Practical Quantum-Inspired Classical Algorithms for Solving Linear Systems [11.929584800629673]
  線形系を解くための高速で実用的な量子インスパイアされた古典的アルゴリズムを提案する。 我々の主な貢献は、線形系を解くために量子に着想を得た古典的アルゴリズムへの重球運動量法の適用である。
  論文  参考訳（メタデータ） (2023-07-13T08:46:19Z)
• Near-optimal fitting of ellipsoids to random points [68.12685213894112]
  楕円体をランダムな点に合わせるという基本的な問題は、低ランク行列分解、独立成分分析、主成分分析に関係している。 我々はこの予想を、ある$n = Omega(, d2/mathrmpolylog(d))$ に対する適合楕円体を構成することで対数的因子まで解決する。 我々の証明は、ある非標準確率行列の便利な分解を用いて、サンダーソン等最小二乗構成の実現可能性を示す。
  論文  参考訳（メタデータ） (2022-08-19T18:00:34Z)
• Quantum Resources Required to Block-Encode a Matrix of Classical Data [56.508135743727934]
  回路レベルの実装とリソース推定を行い、古典データの高密度な$Ntimes N$行列をブロックエンコードして$epsilon$を精度良くすることができる。 異なるアプローチ間のリソーストレードオフを調査し、量子ランダムアクセスメモリ(QRAM)の2つの異なるモデルの実装を検討する。 我々の結果は、単純なクエリの複雑さを超えて、大量の古典的データが量子アルゴリズムにアクセスできると仮定された場合のリソースコストの明確な図を提供する。
  論文  参考訳（メタデータ） (2022-06-07T18:00:01Z)
• 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)
• Quantum algorithms for spectral sums [50.045011844765185]
  正半定値行列(PSD)のスペクトル和を推定するための新しい量子アルゴリズムを提案する。 本稿では, スペクトルグラフ理論における3つの問題に対して, アルゴリズムと手法が適用可能であることを示す。
  論文  参考訳（メタデータ） (2020-11-12T16:29:45Z)
• Enhancing the Quantum Linear Systems Algorithm using Richardson Extrapolation [0.8057006406834467]
  Amathbfx=mathbfb$という形の線形方程式の系を解く量子アルゴリズムを提案する。 このアルゴリズムは古典的手法に対して$N$に対して指数関数的に改善する。
  論文  参考訳（メタデータ） (2020-09-09T18:00:09Z)

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

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