論文の概要: Slow Mixing of Quantum Gibbs Samplers

• arxiv url: http://arxiv.org/abs/2411.04300v1
• Date: Wed, 06 Nov 2024 22:51:27 GMT
• ステータス: 翻訳完了
• システム内更新日: 2024-11-08 19:35:45.329865
• Title: Slow Mixing of Quantum Gibbs Samplers
• Title（参考訳）: 量子ギブスサンプリング器のスローミキシング
• Authors: David Gamarnik, Bobak T. Kiani, Alexander Zlokapa,
• Abstract要約: 一般化されたボトルネック補題を用いて、これらのツールの量子一般化を示す。 この補題は、古典的なハミング距離に類似する距離の量子測度に焦点を当てるが、一意に量子原理に根ざしている。 サブ線形障壁でさえも、ファインマン・カック法を用いて古典的から量子的なものを持ち上げて、厳密な下界の$T_mathrmmix = 2Omega(nalpha)$を確立する。
• 参考スコア（独自算出の注目度）: 47.373245682678515
• License:
• Abstract: Preparing thermal (Gibbs) states is a common task in physics and computer science. Recent algorithms mimic cooling via system-bath coupling, where the cost is determined by mixing time, akin to classical Metropolis-like algorithms. However, few methods exist to demonstrate slow mixing in quantum systems, unlike the well-established classical tools for systems like the Ising model and constraint satisfaction problems. We present a quantum generalization of these tools through a generic bottleneck lemma that implies slow mixing in quantum systems. This lemma focuses on quantum measures of distance, analogous to the classical Hamming distance but rooted in uniquely quantum principles and quantified either through Bohr spectrum jumps or operator locality. Using our bottleneck lemma, we establish unconditional lower bounds on the mixing times of Gibbs samplers for several families of Hamiltonians at low temperatures. For classical Hamiltonians with mixing time lower bounds $T_\mathrm{mix} = 2^{\Omega(n^\alpha)}$, we prove that quantum Gibbs samplers also have $T_\mathrm{mix} = 2^{\Omega(n^\alpha)}$. This applies to models like random $K$-SAT instances and spin glasses. For stabilizer Hamiltonians, we provide a concise proof of exponential lower bounds $T_\mathrm{mix} = 2^{\Omega(n)}$ on mixing times of good $n$-qubit stabilizer codes at low constant temperature, improving upon previous bounds of $T_\mathrm{mix} = 2^{\Omega(\sqrt n)}$. Finally, for $H = H_0 + h\sum_i X_i$ with $H_0$ diagonal in $Z$ basis, we show that a linear free energy barrier in $H_0$ leads to $T_\mathrm{mix} = 2^{\Omega(n)}$ for local Gibbs samplers at low temperature and small $h$. Even with sublinear barriers, we use Poisson Feynman-Kac techniques to lift classical bottlenecks to quantum ones establishing an asymptotically tight lower bound $T_\mathrm{mix} = 2^{n^{1/2-o(1)}}$ for the 2D transverse field Ising model.
• Abstract（参考訳）: 熱状態(ギブズ)を準備することは物理学や計算機科学において一般的な課題である。 最近のアルゴリズムは、古典的なメトロポリスのようなアルゴリズムと同様に、時間混合によってコストが決定されるシステムバスカップリングによる冷却を模倣している。 しかし、イジングモデルや制約満足度問題のようなシステムのための確立された古典的なツールとは異なり、量子系における遅い混合を示す方法はほとんど存在しない。 我々はこれらのツールの量子一般化を、量子系における遅い混合を暗示する一般的なボトルネック補題を通して提示する。 この補題は、古典的なハミング距離に類似する距離の量子測度に焦点を当てるが、一意に量子原理に根ざし、ボーアスペクトルジャンプまたは作用素局所性を通じて定量化される。 ボトルネック補題を用いて、低温でハミルトニアンのいくつかの家系に対してギブス試料の混合時間に関する無条件下限を定めている。 T_\mathrm{mix} = 2^{\Omega(n^\alpha)}$ を混合する古典的ハミルトニアンに対しては、量子ギブスサンプリング器も$T_\mathrm{mix} = 2^{\Omega(n^\alpha)}$ を持つことを証明する。 これはランダムな$K$-SATインスタンスやスピングラスのようなモデルに適用できる。 安定化器ハミルトニアンに対しては、指数的下界の簡潔な証明として$T_\mathrm{mix} = 2^{\Omega(n)}$を低い定温度で混合した場合に$T_\mathrm{mix} = 2^{\Omega(\sqrt n)}$とする。 最後に、$H = H_0 + h\sum_i X_i$ with $H_0$ diagonal in $Z$ に対して、$H_0$ の線型自由エネルギー障壁は、低温で小さな$h$ のギブスサンプルに対して$T_\mathrm{mix} = 2^{\Omega(n)}$ となることを示す。 サブ線形障壁でさえも、ポアソン・ファインマン・カック(Poisson Feynman-Kac)法を用いて古典的ボトルネックを量子的に持ち上げ、漸近的に厳密な下界を持つ$T_\mathrm{mix} = 2^{n^{1/2-o(1)}} を2次元逆場イジングモデルに対して成立させる。

関連論文リスト

• A polynomial-time dissipation-based quantum algorithm for solving the ground states of a class of classically hard Hamiltonians [4.500918096201963]
  我々は、ハミルトン群の基底状態を解決するための量子アルゴリズムを与える。 我々のアルゴリズムに現れた指数的スピードアップのメカニズムは、オープン量子系における散逸に由来する。
  論文  参考訳（メタデータ） (2024-01-25T05:01:02Z)
• Time-Efficient Quantum Entropy Estimator via Samplizer [7.319050391449301]
  量子状態のエントロピーを推定することは、量子情報の基本的な問題である。 我々は、フォン・ノイマンエントロピー $S(rho)$ と R'enyi entropy $S_alpha(rho)$ を$N$次元量子状態 $rho として推定するための時間効率のよい量子アプローチを導入する。
  論文  参考訳（メタデータ） (2024-01-18T12:50:20Z)
• Towards large-scale quantum optimization solvers with few qubits [59.63282173947468]
  我々は、$m=mathcalO(nk)$バイナリ変数を$n$ qubitsだけを使って最適化するために、$k>1$で可変量子ソルバを導入する。 我々は,特定の量子ビット効率の符号化が,バレン高原の超ポリノミウム緩和を内蔵特徴としてもたらすことを解析的に証明した。
  論文  参考訳（メタデータ） (2024-01-17T18:59:38Z)
• A Unified Framework for Uniform Signal Recovery in Nonlinear Generative Compressed Sensing [68.80803866919123]
  非線形測定では、ほとんどの先行結果は一様ではない、すなわち、すべての$mathbfx*$に対してではなく、固定された$mathbfx*$に対して高い確率で保持される。 本フレームワークはGCSに1ビット/一様量子化観測と単一インデックスモデルを標準例として適用する。 また、指標集合が計量エントロピーが低い製品プロセスに対して、より厳密な境界を生み出す濃度不等式も開発する。
  論文  参考訳（メタデータ） (2023-09-25T17:54:19Z)
• A lower bound on the space overhead of fault-tolerant quantum computation [51.723084600243716]
  しきい値定理は、フォールトトレラント量子計算の理論における基本的な結果である。 振幅雑音を伴う耐故障性量子計算の最大長に対する指数的上限を証明した。
  論文  参考訳（メタデータ） (2022-01-31T22:19:49Z)
• On quantum algorithms for the Schr\"odinger equation in the semi-classical regime [27.175719898694073]
  半古典的状態におけるシュル・オーディンガーの方程式を考える。 このようなシュル・オーディンガー方程式はボルン=オッペンハイマーの分子動力学やエレンフェストの動力学など多くの応用を見出す。
  論文  参考訳（メタデータ） (2021-12-25T20:01:54Z)
• Improved spectral gaps for random quantum circuits: large local dimensions and all-to-all interactions [0.0]
  我々は、$D$のランダム量子回路がスペクトルギャップスケーリングを$Omega(n-1)$とすることを示し、$t$が局所次元と比較して小さいことを仮定する:$t2leq O(q)$。 2つ目の結果は、全ての相互作用を持つランダム量子回路に対して、以下に$Omega(n-1log-1(n) t-alpha(q))$で有界な非条件スペクトルギャップである。
  論文  参考訳（メタデータ） (2020-12-09T19:00:50Z)
• Quantum Algorithms for Simulating the Lattice Schwinger Model [63.18141027763459]
  NISQとフォールトトレラントの両方の設定で格子シュウィンガーモデルをシミュレートするために、スケーラブルで明示的なデジタル量子アルゴリズムを提供する。 格子単位において、結合定数$x-1/2$と電場カットオフ$x-1/2Lambda$を持つ$N/2$物理サイト上のシュウィンガーモデルを求める。 NISQと耐故障性の両方でコストがかかるオブザーバブルを、単純なオブザーバブルとして推定し、平均ペア密度を推定する。
  論文  参考訳（メタデータ） (2020-02-25T19:18:36Z)
• Quantum Coupon Collector [62.58209964224025]
  我々は、$k$-要素集合$Ssubseteq[n]$が、その要素の一様重ね合わせ$|Srangleからいかに効率的に学習できるかを研究する。 我々は、$k$と$n$ごとに必要となる量子サンプルの数に厳密な制限を与え、効率的な量子学習アルゴリズムを与える。
  論文  参考訳（メタデータ） (2020-02-18T16:14:55Z)

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

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