論文の概要: Optimal learning of quantum Hamiltonians from high-temperature Gibbs
states
- arxiv url: http://arxiv.org/abs/2108.04842v1
- Date: Tue, 10 Aug 2021 18:00:49 GMT
- ステータス: 処理完了
- システム内更新日: 2021-08-12 13:16:12.562634
- Title: Optimal learning of quantum Hamiltonians from high-temperature Gibbs
states
- Title(参考訳): 高温ギブス状態からの量子ハミルトンの最適学習
- Authors: Jeongwan Haah, Robin Kothari, Ewin Tang
- Abstract要約: 我々は、サンプル複雑性$S = O(log N/(betavarepsilon)2)$とサンプルサイズにおける時間線型である$O(S N)$で、ハミルトンの係数を誤差$varepsilon$で学習する方法を示す。
付録では、ほぼ同じアルゴリズムを用いて、類似のサンプルと時間複雑性を持つ小さな$tレジームにおいて、リアルタイム進化単位の$e-it Hilonから$H$を学習できることが示されている。
- 参考スコア(独自算出の注目度): 0.9453554184019105
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: We study the problem of learning a Hamiltonian $H$ to precision
$\varepsilon$, supposing we are given copies of its Gibbs state
$\rho=\exp(-\beta H)/\operatorname{Tr}(\exp(-\beta H))$ at a known inverse
temperature $\beta$. Anshu, Arunachalam, Kuwahara, and Soleimanifar (Nature
Physics, 2021) recently studied the sample complexity (number of copies of
$\rho$ needed) of this problem for geometrically local $N$-qubit Hamiltonians.
In the high-temperature (low $\beta$) regime, their algorithm has sample
complexity poly$(N, 1/\beta,1/\varepsilon)$ and can be implemented with
polynomial, but suboptimal, time complexity.
In this paper, we study the same question for a more general class of
Hamiltonians. We show how to learn the coefficients of a Hamiltonian to error
$\varepsilon$ with sample complexity $S = O(\log N/(\beta\varepsilon)^{2})$ and
time complexity linear in the sample size, $O(S N)$. Furthermore, we prove a
matching lower bound showing that our algorithm's sample complexity is optimal,
and hence our time complexity is also optimal.
In the appendix, we show that virtually the same algorithm can be used to
learn $H$ from a real-time evolution unitary $e^{-it H}$ in a small $t$ regime
with similar sample and time complexity.
- Abstract(参考訳): 我々は、ハミルトニアン$H$を精度良く学習する問題を研究し、そのギブス状態 $\rho=\exp(-\beta H)/\operatorname{Tr}(\exp(-\beta H))$ のコピーを既知の逆温度 $\beta$ で与えられる。
Anshu, Arunachalam, Kuwahara, and Soleimanifar (Nature Physics, 2021) は、幾何学的に局所的な$N$-qubit Hamiltonianに対してこの問題のサンプル複雑性($$\rho$のコピーの数)を研究した。
高温(低い$\beta$)では、それらのアルゴリズムはポリ(N, 1/\beta,1/\varepsilon)$のサンプル複雑性を持ち、多項式で実装できるが、最適でない時間複雑性を持つ。
本稿では、より一般的なハミルトンのクラスについて、同様の質問を考察する。
我々は、サンプル複雑性$S = O(\log N/(\beta\varepsilon)^{2})$と時間複雑性をサンプルサイズで線形に、$O(S N)$で誤りを犯すハミルトニアンの係数を学習する方法を示す。
さらに,アルゴリズムのサンプル複雑性が最適であることを示し,時間複雑性も最適であることを示す。
付録では、ほぼ同じアルゴリズムを用いて、実時間進化単位の$e^{-it H}$から、類似のサンプルと時間複雑性を持つ小さな$t$レジームで$H$を学習できることが示されている。
関連論文リスト
- Efficiently Learning One-Hidden-Layer ReLU Networks via Schur
Polynomials [50.90125395570797]
正方形損失に関して、標準的なガウス分布の下での$k$ReLU活性化の線形結合をPAC学習する問題をmathbbRd$で検討する。
本研究の主な成果は,この学習課題に対して,サンプルおよび計算複雑性が$(dk/epsilon)O(k)$で,epsilon>0$が目標精度である。
論文 参考訳(メタデータ) (2023-07-24T14:37:22Z) - Near-Optimal Bounds for Learning Gaussian Halfspaces with Random
Classification Noise [50.64137465792738]
この問題に対する効率的なSQアルゴリズムは、少なくとも$Omega(d1/2/(maxp, epsilon)2)$. のサンプル複雑性を必要とする。
我々の下限は、この1/epsilon$に対する二次的依存は、効率的なアルゴリズムに固有のものであることを示唆している。
論文 参考訳(メタデータ) (2023-07-13T18:59:28Z) - Information-Computation Tradeoffs for Learning Margin Halfspaces with
Random Classification Noise [50.64137465792738]
ランダム分類ノイズを用いたPAC$gamma$-marginハーフスペースの問題について検討する。
我々は、問題のサンプル複雑性と計算効率の良いアルゴリズムのサンプル複雑性との間に固有のギャップを示唆する情報計算トレードオフを確立する。
論文 参考訳(メタデータ) (2023-06-28T16:33:39Z) - Learning many-body Hamiltonians with Heisenberg-limited scaling [3.460138063155115]
N$-qubit 局所ハミルトニアンの相互作用を学習するためのハイゼンベルク限界を達成するアルゴリズムを提案する。
総進化時間$mathcalO(epsilon-1)$の後に、提案アルゴリズムは高い確率で$N$-qubit Hamiltonianのパラメータを$epsilon$-errorに効率的に推定することができる。
論文 参考訳(メタデータ) (2022-10-06T16:30:51Z) - Optimal algorithms for learning quantum phase states [8.736370689844682]
未知の次数$d$相状態を学ぶ際のサンプルの複雑さは、分離可能な測定を許せば$Theta(nd)$であることを示す。
また、f$がsparsity-$s$, degree-$d$を持つ場合の学習フェーズ状態も検討する。
論文 参考訳(メタデータ) (2022-08-16T17:15:06Z) - Quantum algorithms from fluctuation theorems: Thermal-state preparation [0.09786690381850353]
逆温度でのH_$の熱状態の浄化を行うための量子アルゴリズムを提案する。
エプシロン$の複雑性の依存性は、量子系の構造によって異なる。
我々は、異なる非平衡ユニタリプロセスを用いて、逆場イジングモデルの熱状態を作成する複雑さを解析する。
論文 参考訳(メタデータ) (2022-03-16T18:55:12Z) - Private and polynomial time algorithms for learning Gaussians and beyond [13.947461378608525]
本稿では,$(varepsilon, delta)$differentially private (DP) 統計的推定を非私的推定に還元する枠組みを提案する。
我々は、(制限のない)ガウスの堅牢な学習のための$(varepsilon, delta)$-DPアルゴリズムを初めて提供する。
論文 参考訳(メタデータ) (2021-11-22T16:25:51Z) - Threshold Phenomena in Learning Halfspaces with Massart Noise [56.01192577666607]
ガウス境界の下でのマスアートノイズ付きmathbbRd$におけるPAC学習ハーフスペースの問題について検討する。
この結果は,Massartモデルにおける学習ハーフスペースの複雑さを定性的に特徴づけるものである。
論文 参考訳(メタデータ) (2021-08-19T16:16:48Z) - Enhancing the Quantum Linear Systems Algorithm using Richardson
Extrapolation [0.8057006406834467]
Amathbfx=mathbfb$という形の線形方程式の系を解く量子アルゴリズムを提案する。
このアルゴリズムは古典的手法に対して$N$に対して指数関数的に改善する。
論文 参考訳(メタデータ) (2020-09-09T18:00:09Z) - 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)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト(すべての情報・翻訳含む)の品質を保証せず、本サイト(すべての情報・翻訳含む)を使用して発生したあらゆる結果について一切の責任を負いません。