論文の概要: A rapidly mixing Markov chain from any gapped quantum many-body system
- arxiv url: http://arxiv.org/abs/2207.07044v2
- Date: Mon, 30 Oct 2023 20:36:59 GMT
- ステータス: 処理完了
- システム内更新日: 2023-11-02 04:42:47.675386
- Title: A rapidly mixing Markov chain from any gapped quantum many-body system
- Title（参考訳）: ギャップ量子多体系からの急速に混合されたマルコフ鎖
- Authors: Sergey Bravyi, Giuseppe Carleo, David Gosset, Yinchen Liu
- Abstract要約: 我々は、$pi(x)=|langle x|psirangle|2$ からビット文字列 $x$ を考える。
我々の主な結果は、逆スペクトルギャップ$H$と関連する連続時間Markov Chainと定常状態$pi$の混合時間との直接リンクを記述する。
- 参考スコア（独自算出の注目度）: 2.321323878201932
- License: http://creativecommons.org/licenses/by/4.0/
- Abstract: We consider the computational task of sampling a bit string $x$ from a
distribution $\pi(x)=|\langle x|\psi\rangle|^2$, where $\psi$ is the unique
ground state of a local Hamiltonian $H$. Our main result describes a direct
link between the inverse spectral gap of $H$ and the mixing time of an
associated continuous-time Markov Chain with steady state $\pi$. The Markov
Chain can be implemented efficiently whenever ratios of ground state amplitudes
$\langle y|\psi\rangle/\langle x|\psi\rangle$ are efficiently computable, the
spectral gap of $H$ is at least inverse polynomial in the system size, and the
starting state of the chain satisfies a mild technical condition that can be
efficiently checked. This extends a previously known relationship between
sign-problem free Hamiltonians and Markov chains. The tool which enables this
generalization is the so-called fixed-node Hamiltonian construction, previously
used in Quantum Monte Carlo simulations to address the fermionic sign problem.
We implement the proposed sampling algorithm numerically and use it to sample
from the ground state of Haldane-Shastry Hamiltonian with up to 56 qubits. We
observe empirically that our Markov chain based on the fixed-node Hamiltonian
mixes more rapidly than the standard Metropolis-Hastings Markov chain.
- Abstract（参考訳）: 分布 $\pi(x)=|\langle x|\psi\rangle|^2$ からビット文字列 $x$ をサンプリングする計算タスクを考える。
我々の主な結果は、逆スペクトルギャップの$H$と、関連する連続時間マルコフ連鎖と定常状態の$\pi$との混合時間との直接リンクを記述する。
マルコフ連鎖は、基底状態振幅の比$\langle y|\psi\rangle/\langle x|\psi\rangle$が効率良く計算可能であり、$H$のスペクトルギャップはシステムサイズにおける少なくとも逆多項式であり、連鎖の開始状態は、効率よくチェックできる穏やかな技術的条件を満たす。
これは、サインプロブレム自由ハミルトニアンとマルコフ連鎖の間の既知の関係を拡張する。
この一般化を可能にするツールは、フェルミオン符号問題に対処するために以前は量子モンテカルロシミュレーションで使われていたいわゆる固定ノードハミルトン構成である。
提案したサンプリングアルゴリズムを数値的に実装し,56量子ビットのHaldane-Shastry Hamiltonian基底状態からサンプリングする。
我々は、固定ノードハミルトニアンに基づくマルコフ連鎖が標準のメトロポリス・ハスティングス・マルコフ連鎖よりも高速に混合されることを経験的に観察する。
関連論文リスト
- Slow Mixing of Quantum Gibbs Samplers [47.373245682678515]
一般化されたボトルネック補題を用いて、これらのツールの量子一般化を示す。
この補題は、古典的なハミング距離に類似する距離の量子測度に焦点を当てるが、一意に量子原理に根ざしている。
サブ線形障壁でさえも、ファインマン・カック法を用いて古典的から量子的なものを持ち上げて、厳密な下界の$T_mathrmmix = 2Omega(nalpha)$を確立する。
論文 参考訳（メタデータ） (2024-11-06T22:51:27Z) - Provable Benefit of Annealed Langevin Monte Carlo for Non-log-concave Sampling [28.931489333515618]
簡単なアニール型Langevin Monte Carloアルゴリズムに対して$widetildeOleft(fracdbeta2cal A2varepsilon6right)のオラクル複雑性を確立する。
例えば、$cal A$ は対象分布 $pi$ と容易にサンプリング可能な分布を補間する確率測度の曲線の作用を表す。
論文 参考訳（メタデータ） (2024-07-24T02:15:48Z) - Ito Diffusion Approximation of Universal Ito Chains for Sampling, Optimization and Boosting [64.0722630873758]
我々は、ある微分方程式のオイラー・マルヤマ離散化のように見える、より一般で幅広いマルコフ連鎖、伊藤鎖を考える。
伊藤鎖の法則と微分方程式の間の$W_2$-距離の有界性を証明する。
論文 参考訳（メタデータ） (2023-10-09T18:38:56Z) - Enabling Quantum Speedup of Markov Chains using a Multi-level Approach [0.0]
マルコフ連鎖を混合する量子スピードアップは、ゆっくりと変化する$r$マルコフ鎖の構成に基づいて達成できる。
低分解能マルコフ鎖の密度関数を用いてマルコフ鎖を高分解能で温めることができることを示す。
論文 参考訳（メタデータ） (2022-10-25T15:17:52Z) - Space-efficient Quantization Method for Reversible Markov Chains [1.558664512158522]
Szegedy氏は、任意の可逆マルコフ連鎖に対する量子ウォーク$W(P)$の構築方法を示した。
ある種のマルコフ連鎖に対する状態空間の二重化を回避できることが示される。
論文 参考訳（メタデータ） (2022-06-14T14:41:56Z) - How to simulate quantum measurement without computing marginals [3.222802562733787]
量子状態$psi$を標準で計算するためのアルゴリズムを,古典的に記述し,解析する。
我々のアルゴリズムはサンプリングタスクを$n$-qubit状態のポリ(n)$振幅の計算に還元する。
論文 参考訳（メタデータ） (2021-12-15T21:44:05Z) - Random quantum circuits transform local noise into global white noise [118.18170052022323]
低忠実度状態におけるノイズランダム量子回路の測定結果の分布について検討する。
十分に弱くユニタリな局所雑音に対して、一般的なノイズ回路インスタンスの出力分布$p_textnoisy$間の相関(線形クロスエントロピーベンチマークで測定)は指数関数的に減少する。
ノイズが不整合であれば、出力分布は、正確に同じ速度で均一分布の$p_textunif$に近づく。
論文 参考訳（メタデータ） (2021-11-29T19:26:28Z) - Optimal policy evaluation using kernel-based temporal difference methods [78.83926562536791]
カーネルヒルベルト空間を用いて、無限水平割引マルコフ報酬過程の値関数を推定する。
我々は、関連するカーネル演算子の固有値に明示的に依存した誤差の非漸近上界を導出する。
MRP のサブクラスに対する minimax の下位境界を証明する。
論文 参考訳（メタデータ） (2021-09-24T14:48:20Z) - Stoquasticity in circuit QED [78.980148137396]
スケーラブルな符号-確率自由経路積分モンテカルロシミュレーションは一般にそのようなシステムに対して可能であることを示す。
我々は、実効的、非確率的クビットハミルトニアンが容量結合された束量子ビットの系に現れるという最近の発見を裏付ける。
論文 参考訳（メタデータ） (2020-11-02T16:41:28Z) - A Matrix Chernoff Bound for Markov Chains and Its Application to
Co-occurrence Matrices [30.49132891333353]
正則な(周期的かつ既約な)有限マルコフ連鎖を介してサンプリングされた行列値確率変数の和に対するチェルノフ型有界性を証明する。
我々の証明は、[Garg et al. STOC '18] とマルコフ連鎖に対するスカラーチャーノフ-ホーフディング境界の行列展開(正規無向グラフ)に基づいている。
マルコフ連鎖に対する我々の行列チェルノフバウンドは、逐次データに対する共起統計量の挙動を解析するために応用できる。
論文 参考訳（メタデータ） (2020-08-06T05:44:54Z) - Sample Complexity of Asynchronous Q-Learning: Sharper Analysis and
Variance Reduction [63.41789556777387]
非同期Q-ラーニングはマルコフ決定過程(MDP)の最適行動値関数(またはQ-関数)を学習することを目的としている。
Q-関数の入出力$varepsilon$-正確な推定に必要なサンプルの数は、少なくとも$frac1mu_min (1-gamma)5varepsilon2+ fract_mixmu_min (1-gamma)$の順である。
論文 参考訳（メタデータ） (2020-06-04T17:51:00Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。