論文の概要: DQC1-completeness of normalized trace estimation for functions of log-local Hamiltonians
- arxiv url: http://arxiv.org/abs/2604.01519v1
- Date: Thu, 02 Apr 2026 01:15:12 GMT
- ステータス: 翻訳完了
- システム内更新日: 2026-04-03 14:21:10.183763
- Title: DQC1-completeness of normalized trace estimation for functions of log-local Hamiltonians
- Title（参考訳）: 対数局所ハミルトニアン関数に対する正規化トレース推定のDQC1完全性
- Authors: Zhengfeng Ji, Tongyang Li, Changpeng Shao, Xinzhao Wang, Yuxin Zhang,
- Abstract要約: 正規化トレース 2-nTr[f(A)]$ を対数局所ハミルトニアン$A$ で$n$ qubits に作用させることの計算複雑性について検討する。
この問題は自然に DQC1 モデルで生じるが、その複雑性は限定された函数のクラス$f(x)$に対してのみ理解される。
f(x)$ が近似次数 $(rm poly(n))$ の連続関数であれば、2-nTr[f(A)]$ を定数加法誤差まで見積もる。
- 参考スコア（独自算出の注目度）: 20.990700912031773
- License: http://creativecommons.org/licenses/by/4.0/
- Abstract: We study the computational complexity of estimating the normalized trace $2^{-n}Tr[f(A)]$ for a log-local Hamiltonian $A$ acting on $n$ qubits. This problem arises naturally in the DQC1 model, yet its complexity is only understood for a limited class of functions $f(x)$. We show that if $f(x)$ is a continuous function with approximate degree $Ω({\rm poly}(n))$, then estimating $2^{-n}Tr[f(A)]$ up to constant additive error is DQC1-complete, under a technical condition on the polynomial approximation error of $f(x)$. This condition holds for a broad class of functions, including exponentials, trigonometric functions, logarithms, and inverse-type functions. We further prove that when $A$ is sparse, the classical query complexity of this problem is exponential in the approximate degree, assuming a conjectured lower bound for a trace variant of the $k$-Forrelation problem in the DQC1 query model. Together, these results identify the approximate degree as the key parameter governing the complexity of normalized trace estimation: it characterizes both the quantum complexity (via efficient DQC1 algorithms) and, conditionally, the classical hardness, yielding an exponential quantum-classical separation. Our proof develops a unified framework that cleanly combines circuit-to-Hamiltonian constructions, periodic Jacobi operators, and tools from polynomial approximation theory, including the Chebyshev equioscillation theorem.
- Abstract（参考訳）: 正規化トレース 2^{-n}Tr[f(A)]$ を対数局所ハミルトニアン$A$ で$n$ qubits に作用させることの計算複雑性について検討する。
この問題は自然に DQC1 モデルで生じるが、その複雑性は限定された函数のクラス$f(x)$に対してのみ理解される。
f(x)$ が近似次数 $Ω({\rm poly}(n))$ の連続函数であれば、多項式近似誤差 $f(x)$ の技術的条件の下で、定数加法誤差に対して 2^{-n}Tr[f(A)]$ が DQC1-完全であることが示される。
この条件は指数関数、三角関数、対数、逆型関数を含む幅広い種類の関数に当てはまる。
さらに、$A$がスパースであるとき、DQC1クエリモデルの$k$-Forrelation問題のトレース変項に対する予想下界を仮定して、この問題の古典的なクエリ複雑性が近似度で指数関数的であることを証明した。
これらの結果は、近似度を、(効率的なDQC1アルゴリズムを介して)量子複雑性と、条件的に古典的硬さの両方を特徴づけ、指数的量子-古典的分離をもたらす、正規化トレース推定の複雑さを規定する鍵パラメータとして特定する。
我々の証明は、回路-ハミルトニアン構成、周期的ヤコビ作用素、およびチェビシェフ等化定理を含む多項式近似理論からのツールをきれいに組み合わせた統一的な枠組みを開発する。
関連論文リスト
- Hardness of High-Dimensional Linear Classification [58.29089693778071]
我々は、最大半空間離散性問題に対する次元下界の新たな指数関数を確立する。
どちらも計算幾何学と機械学習の基本的問題であり、その正確で近似的な形式である。
論文 参考訳（メタデータ） (2026-03-19T15:53:41Z) - Quantum computational complexity of matrix functions [2.7488316163114823]
2つの原始問題の計算複雑性について検討する。
単項関数、チェビシェフ関数、時間発展関数、逆関数の4つの関数を考える。
各関数に対する両問題のBQP完全形式を同定する。
論文 参考訳（メタデータ） (2024-10-17T18:00:03Z) - Calculating response functions of coupled oscillators using quantum phase estimation [40.31060267062305]
量子コンピュータを用いた結合型古典的高調波発振器系の周波数応答関数の推定問題について検討する。
提案する量子アルゴリズムは,標準的な$sスパース,オーラクルベースのクエリアクセスモデルで動作する。
そこで,本アルゴリズムの簡単な適応により,時間内に無作為な結束木問題を解くことを示す。
論文 参考訳（メタデータ） (2024-05-14T15:28:37Z) - Provably Efficient Reinforcement Learning via Surprise Bound [66.15308700413814]
本稿では,一般値関数近似を用いた効率の良い強化学習アルゴリズムを提案する。
本アルゴリズムは, 線形設定と疎高次元線形設定の両方に適用した場合に, 合理的な後悔境界を達成できる。
論文 参考訳（メタデータ） (2023-02-22T20:21:25Z) - Detection-Recovery Gap for Planted Dense Cycles [72.4451045270967]
期待帯域幅$n tau$とエッジ密度$p$をエルドホス=R'enyiグラフ$G(n,q)$に植え込むモデルを考える。
低次アルゴリズムのクラスにおいて、関連する検出および回復問題に対する計算しきい値を特徴付ける。
論文 参考訳（メタデータ） (2023-02-13T22:51:07Z) - On Function Approximation in Reinforcement Learning: Optimism in the
Face of Large State Spaces [208.67848059021915]
強化学習のコアにおける探索・探索トレードオフについて検討する。
特に、関数クラス $mathcalF$ の複雑さが関数の複雑さを特徴づけていることを証明する。
私たちの後悔の限界はエピソードの数とは無関係です。
論文 参考訳（メタデータ） (2020-11-09T18:32:22Z) - Reinforcement Learning with General Value Function Approximation:
Provably Efficient Approach via Bounded Eluder Dimension [124.7752517531109]
一般値関数近似を用いた効率の良い強化学習アルゴリズムを確立する。
我々のアルゴリズムは、$d$が複雑性測度である場合、$widetildeO(mathrmpoly(dH)sqrtT)$の後悔の限界を達成することを示す。
我々の理論は線形値関数近似によるRLの最近の進歩を一般化し、環境モデルに対する明示的な仮定をしない。
論文 参考訳（メタデータ） (2020-05-21T17:36:09Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。