論文の概要: 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-28 17:07:45.16382
• Title: Slow Mixing of Quantum Gibbs Samplers
• Title（参考訳）: 量子ギブスサンプリング器のスローミキシング
• Authors: David Gamarnik, Bobak T. Kiani, Alexander Zlokapa,
• Abstract要約: 一般化されたボトルネック補題を用いて、これらのツールの量子一般化を示す。 この補題は、古典的なハミング距離に類似する距離の量子測度に焦点を当てるが、一意に量子原理に根ざしている。 サブ線形障壁でさえも、ファインマン・カック法を用いて古典的から量子的なものを持ち上げて、厳密な下界の$T_mathrmmix = 2Omega(nalpha)$を確立する。
• 参考スコア（独自算出の注目度）: 47.373245682678515
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• 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次元逆場イジングモデルに対して成立させる。

関連論文リスト

• Learning quantum Gibbs states locally and efficiently [7.728643029778198]
  熱平衡における量子多体系の基礎となるハミルトニアンの学習は、量子学習理論と実験科学の基本的な課題である。 我々は, 局所項である$n$-qubit $D$-dimensional Hamiltonian を, サンプル複雑性を伴う加法誤差$epsilon$ に学習する学習アルゴリズムを提案する。
  論文  参考訳（メタデータ） (2025-04-03T15:42:23Z)
• Testing classical properties from quantum data [0.0]
  古典的テスタをサンプルに制限する場合のスピードアップは,量子データを使用するテスタによって回復可能であることを示す。 単調性テストでは、古典的に必要とされる2Omega(sqrtn)$サンプルと比較して、$tildemathcalO(n2)$関数状態コピーを使用する量子アルゴリズムを提供する。 Omega(n1/4)$ および $Omega(n)$ の古典的下限と比較し,対称性と三角形自由度に関する $mathcalO(1)$-copy テスタも提示する。
  論文  参考訳（メタデータ） (2024-11-19T18:52:55Z)
• Optimizing random local Hamiltonians by dissipation [44.99833362998488]
  簡単な量子ギブスサンプリングアルゴリズムが最適値の$Omega(frac1k)$-fraction近似を達成することを証明した。 この結果から, 局所スピンおよびフェルミオンモデルに対する低エネルギー状態の発見は量子的に容易であるが, 古典的には非自明であることが示唆された。
  論文  参考訳（メタデータ） (2024-11-04T20:21:16Z)
• Hamiltonian simulation for low-energy states with optimal time dependence [45.02537589779136]
  低エネルギー部分空間内のハミルトン$H$の下で時間発展をシミュレートする作業を考える。 我々は,$O(tsqrtlambdaGamma + sqrtlambda/Gammalog (1/epsilon))$クエリを,任意の$Gamma$に対するブロックエンコーディングに使用する量子アルゴリズムを提案する。
  論文  参考訳（メタデータ） (2024-04-04T17:58:01Z)
• 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)
• Quantum walks advantage on the dihedral group for uniform sampling problem [0.0]
  本稿では、ケイリーグラフ上での量子ウォーク混合の一般的な理解を前進させる。 これは、D_2n$で連続時間量子ウォークによって達成された改良された混合時間を強調する。 この研究は、非アーベル群に基づくサンプリング問題のクラスに対するアルゴリズムに潜在的な応用をもたらす。
  論文  参考訳（メタデータ） (2023-12-25T11:21:55Z)
• An efficient and exact noncommutative quantum Gibbs sampler [0.0]
  任意の非可換ハミルトニアンのギブス状態に対して、効率よく実装可能で正確に詳細バランスの取れたリンドブラディアンを初めて構築する。 我々の構成は、メトロポリス・ハスティングスアルゴリズムの連続時間量子アナログと見なすこともできる。
  論文  参考訳（メタデータ） (2023-11-15T18:51:24Z)
• A Unified Framework for Uniform Signal Recovery in Nonlinear Generative Compressed Sensing [68.80803866919123]
  非線形測定では、ほとんどの先行結果は一様ではない、すなわち、すべての$mathbfx*$に対してではなく、固定された$mathbfx*$に対して高い確率で保持される。 本フレームワークはGCSに1ビット/一様量子化観測と単一インデックスモデルを標準例として適用する。 また、指標集合が計量エントロピーが低い製品プロセスに対して、より厳密な境界を生み出す濃度不等式も開発する。
  論文  参考訳（メタデータ） (2023-09-25T17:54:19Z)
• Uniform observable error bounds of Trotter formulae for the semiclassical Schrödinger equation [0.0]
  観測可能なクラスの計算コストは、最先端の限界よりもはるかに低いことを示します。 We improve the additive observable error bounds to uniform-in-$h$ observable error bounds。 これは、我々の知る限りでは、半古典的シュル「オーディンガー方程式」に対する最初の一様可観測誤差である。
  論文  参考訳（メタデータ） (2022-08-16T21:34:49Z)
• 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)
• Average-case Speedup for Product Formulas [69.68937033275746]
  製品公式(英: Product formulas)またはトロッター化(英: Trotterization)は、量子系をシミュレートする最も古い方法であり、いまだに魅力的な方法である。 我々は、ほとんどの入力状態に対して、トロッター誤差が定性的に優れたスケーリングを示すことを証明した。 我々の結果は、平均的なケースにおける量子アルゴリズムの研究の扉を開く。
  論文  参考訳（メタデータ） (2021-11-09T18:49:48Z)
• Hamiltonian simulation with random inputs [74.82351543483588]
  ランダム初期状態を持つハミルトンシミュレーションの平均ケース性能の理論 数値的な証拠は、この理論がコンクリート模型の平均誤差を正確に特徴づけていることを示唆している。
  論文  参考訳（メタデータ） (2021-11-08T19:08:42Z)
• 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)

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

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