論文の概要: Average-case quantum complexity from glassiness
- arxiv url: http://arxiv.org/abs/2510.08497v1
- Date: Thu, 09 Oct 2025 17:37:33 GMT
- ステータス: 翻訳完了
- システム内更新日: 2025-10-10 17:54:15.253533
- Title: Average-case quantum complexity from glassiness
- Title（参考訳）: ガラス性からの平均ケース量子複雑性
- Authors: Alexander Zlokapa, Bobak T. Kiani, Eric R. Anschuetz,
- Abstract要約: グラスネス(Glassiness)は、物理学において、不安定な自由エネルギーの風景を特徴とする現象であり、安定な古典的アルゴリズムの難しさを意味する。
レプリカ対称性の破れに基づく標準的な量子ガラス性の概念は、ギブスサンプリングのための安定な量子アルゴリズムを妨げていることを証明している。
- 参考スコア（独自算出の注目度）: 45.57609001239456
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: Glassiness -- a phenomenon in physics characterized by a rough free-energy landscape -- implies hardness for stable classical algorithms. For example, it can obstruct constant-time Langevin dynamics and message-passing in random $k$-SAT and max-cut instances. We provide an analogous framework for average-case quantum complexity showing that a natural family of quantum algorithms (e.g., Lindbladian evolution) fails for natural Hamiltonian ensembles (e.g., random 3-local Hamiltonians). Specifically, we prove that the standard notion of quantum glassiness based on replica symmetry breaking obstructs stable quantum algorithms for Gibbs sampling, which we define by a Lipschitz temperature dependence in quantum Wasserstein complexity. Our proof relies on showing that such algorithms fail to capture a structural phase transition in the Gibbs state, where glassiness causes the Gibbs state to decompose into clusters extensively separated in quantum Wasserstein distance. This yields average-case lower bounds for constant-time local Lindbladian evolution and shallow variational circuits. Unlike mixing time lower bounds, our results hold even when dynamics are initialized from the maximally mixed state. We apply these lower bounds to non-commuting, non-stoquastic Hamiltonians by showing a glass transition via the replica trick. We find that the ensemble of all 3-local Pauli strings with independent Gaussian coefficients is average-case hard, while providing analytical evidence that the general $p$-local Pauli ensemble is non-glassy for sufficiently large constant $p$, in contrast to its classical (Ising $p$-spin, always glassy) and fermionic (SYK, never glassy) counterparts.
- Abstract（参考訳）: グラスネス(Glassiness)は、物理学において、不安定な自由エネルギーの風景を特徴とする現象であり、安定な古典的アルゴリズムの難しさを意味する。
例えば、ランダムな$k$-SATおよびmax-cutインスタンスで、定数時間ランゲヴィンダイナミクスとメッセージパスを妨害することができる。
我々は、量子アルゴリズムの自然な族(例えばリンドブラディアンの進化)が自然ハミルトンのアンサンブル(例えば、ランダムな3つの局所ハミルトン多様体)に失敗することを示す平均ケース量子複雑性のための類似のフレームワークを提供する。
具体的には、レプリカ対称性の破れに基づく標準的な量子ガラス性の概念は、量子ワッサーシュタイン複雑性におけるリプシッツ温度依存性によって定義されるギブスサンプリングの安定な量子アルゴリズムを妨げていることを証明している。
我々の証明は、そのようなアルゴリズムがギブス状態の構造的相転移を捉えないことを示すことに依存しており、そこではガラス性によりギブス状態は量子ワッサーシュタイン距離で広く分離されたクラスターに分解される。
これにより、定時間局所リンドブラディアンの進化と浅い変動回路に対する平均ケース下界が得られる。
混合時間下界とは異なり、最大混合状態から力学が初期化されても結果は保たれる。
これらの下界を非可換な非確率的ハミルトン多様体に適用し、レプリカのトリックを通してガラス転移を示す。
独立ガウス係数を持つ3つの局所パウリ弦のアンサンブルは平均ケースハードであり、一般の$p$-局所パウリアンサンブルが、古典的(Ising $p$-spin, always glassy)やフェルミオン(SYK, never glassy)のアンサンブルとは対照的に、十分に大きい定数の$p$に対してガラスではないという解析的な証拠を提供する。
関連論文リスト
- Polynomial Time Quantum Gibbs Sampling for Fermi-Hubbard Model at any Temperature [9.62464358196899]
我々は、相互作用するフェルミオンに対応する摂動型リンドブレディアンの一定のギャップを最大結合強度まで証明する。
これは格子フェルミオンのギャップの安定性に関する定理を用いて達成される。
アプリケーションとして,検討されたシステムに対する分割関数の計算方法を説明する。
論文 参考訳（メタデータ） (2025-01-02T18:56:02Z) - Slow Mixing of Quantum Gibbs Samplers [47.373245682678515]
一般化されたボトルネック補題を用いて、これらのツールの量子一般化を示す。
この補題は、古典的なハミング距離に類似する距離の量子測度に焦点を当てるが、一意に量子原理に根ざしている。
ポアソン・ファインマン・カック法を用いて古典的な緩やかな混合結果を持ち上げる方法を示す。
論文 参考訳（メタデータ） (2024-11-06T22:51:27Z) - Optimizing random local Hamiltonians by dissipation [44.99833362998488]
簡単な量子ギブスサンプリングアルゴリズムが最適値の$Omega(frac1k)$-fraction近似を達成することを証明した。
この結果から, 局所スピンおよびフェルミオンモデルに対する低エネルギー状態の発見は量子的に容易であるが, 古典的には非自明であることが示唆された。
論文 参考訳（メタデータ） (2024-11-04T20:21:16Z) - Efficient Quantum Pseudorandomness from Hamiltonian Phase States [41.94295877935867]
我々は、ハミルトニアン相状態(HPS)問題と呼ばれる量子硬度仮定を導入する。
我々は、我々の仮定が少なくとも完全に量子的であることを示し、すなわち片方向関数を構成するのに使用できない。
仮定とその変形により、多くの擬似ランダム量子プリミティブを効率的に構築できることを示す。
論文 参考訳（メタデータ） (2024-10-10T16:10:10Z) - An efficient and exact noncommutative quantum Gibbs sampler [0.0]
任意の非可換ハミルトニアンのギブス状態に対して、効率よく実装可能で正確に詳細バランスの取れたリンドブラディアンを初めて構築する。
我々の構成は、メトロポリス・ハスティングスアルゴリズムの連続時間量子アナログと見なすこともできる。
論文 参考訳（メタデータ） (2023-11-15T18:51:24Z) - Guidable Local Hamiltonian Problems with Implications to Heuristic Ansätze State Preparation and the Quantum PCP Conjecture [0.0]
我々は最近定義されたガイドド局所ハミルトン問題における「マーリン化」バージョンについて検討する。
これらの問題には、入力の一部として提供される指針状態はなく、単に存在するという約束が伴うだけである。
誘導状態の両クラスに対する誘導可能な局所ハミルトン問題は、逆多項式の精度設定において$mathsfQCMA$-completeであることを示す。
論文 参考訳（メタデータ） (2023-02-22T19:00:00Z) - The principle of majorization: application to random quantum circuits [68.8204255655161]
i) 普遍的、ii) 古典的シミュラブル、iii) 普遍的、古典的シミュラブルの3つのクラスが考慮された。
回路のすべての族が平均的に正規化の原理を満たすことを検証した。
明らかな違いは、状態に関連したローレンツ曲線のゆらぎに現れる。
論文 参考訳（メタデータ） (2021-02-19T16:07:09Z) - Einselection from incompatible decoherence channels [62.997667081978825]
我々は、CQED実験にインスパイアされたオープン量子力学を、2つの非可換リンドブラッド作用素を用いて解析する。
Fock状態は、決定的な結合をデコヒーレンスにデコヒーレンスする最も堅牢な状態のままであることを示す。
論文 参考訳（メタデータ） (2020-01-29T14:15:19Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。