論文の概要: Dequantization Barriers for Guided Stoquastic Hamiltonians
- arxiv url: http://arxiv.org/abs/2602.23183v1
- Date: Thu, 26 Feb 2026 16:40:32 GMT
- ステータス: 翻訳完了
- システム内更新日: 2026-02-27 18:41:22.781595
- Title: Dequantization Barriers for Guided Stoquastic Hamiltonians
- Title（参考訳）: ガイド付き確率ハミルトニアンのための分数化障壁
- Authors: Yassine Hamoudi, Yvan Le Borgne, Shrinidhi Teganahally Sridhara,
- Abstract要約: 量子的設定では、この問題は誘導状態が入力として与えられる確率的ハミルトンの基底状態の準備と見なすことができる。
以上の結果から,従来のアルゴリズムでは幅広い確率的基底状態の問題を解くことはできないことが示唆された。
- 参考スコア（独自算出の注目度）: 0.6308539010172308
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: We construct a probability distribution, induced by the Perron--Frobenius eigenvector of an exponentially large graph, which cannot be efficiently sampled by any classical algorithm, even when provided with the best-possible warm-start distribution. In the quantum setting, this problem can be viewed as preparing the ground state of a stoquastic Hamiltonian given a guiding state as input, and is known to be efficiently solvable on a quantum computer. Our result suggests that no efficient classical algorithm can solve a broad class of stoquastic ground-state problems. Our graph is constructed from a class of high-degree, high-girth spectral expanders to which self-similar trees are attached. This builds on and extends prior work of Gilyén, Hastings, and Vazirani [Quantum 2021, STOC 2021], which ruled out dequantization for a specific stoquastic adiabatic path algorithm. We strengthen their result by ruling out any classical algorithm for guided ground-state preparation.
- Abstract（参考訳）: 指数関数的に大きいグラフのペロン-フロベニウス固有ベクトルによって誘導される確率分布を構築し、最も可能性の高いウォームスタート分布が与えられた場合でも、任意の古典的アルゴリズムでは効率的にサンプリングできない。
量子環境では、この問題は導出状態が入力として与えられる確率的ハミルトンの基底状態の準備と見なすことができ、量子コンピュータ上で効率的に解けることが知られている。
以上の結果から,従来のアルゴリズムでは幅広い確率的基底状態の問題を解くことはできないことが示唆された。
我々のグラフは、自己相似木が取り付けられる高次高密度スペクトル展開器のクラスから構築されている。
これはGilyén, Hastings, Vazirani [Quantum 2021, STOC 2021] の以前の作業の上に構築され、拡張されている。
我々は、誘導基底状態の準備のための古典的アルゴリズムを除外することで、それらの結果を補強する。
関連論文リスト
- Learning Feasible Quantum States for Quadratic Constrained Binary Optimization Problems [41.23247424467223]
我々はQCBOの制約を満たす量子状態の同値重ね合わせを生成する変動的アプローチを開発する。
結果として生じる同値な重ね合わせは、QUBO/QCBOを解く量子アルゴリズムの初期状態として使用できる。
論文 参考訳（メタデータ） (2025-08-04T16:44:53Z) - Unstructured Adiabatic Quantum Optimization: Optimality with Limitations [0.06022769903412461]
本研究では,非構造探索手法を用いた断熱的量子最適化により,古典的局所スピンハミルトニアンのクラスに対する下界と一致するランニング時間が得られることを示す。
回避された交差の位置は、ハミルトニアン問題の退化と逆ギャップに依存し、低加算精度でも計算し難い量によってほぼ与えられることを示す。
論文 参考訳（メタデータ） (2024-11-08T17:51:18Z) - Optimizing random local Hamiltonians by dissipation [44.99833362998488]
簡単な量子ギブスサンプリングアルゴリズムが最適値の$Omega(frac1k)$-fraction近似を達成することを証明した。
この結果から, 局所スピンおよびフェルミオンモデルに対する低エネルギー状態の発見は量子的に容易であるが, 古典的には非自明であることが示唆された。
論文 参考訳（メタデータ） (2024-11-04T20:21:16Z) - Classical Algorithms for Hamiltonian Dynamics Mean Value and Guided Local Hamiltonian Problem [9.550310003133555]
本稿では,任意の局所量子系の短時間ダイナミクスをシミュレーションする,効率的な古典的アルゴリズムを提案する。
また,探索型局所ハミルトニアン(GLH)問題を定値加算誤差に効率よく解く量子アルゴリズムを提案する。
論文 参考訳（メタデータ） (2024-09-06T09:59:12Z) - Bregman-divergence-based Arimoto-Blahut algorithm [53.64687146666141]
本稿では,Arimoto-BlahutアルゴリズムをBregman-Diversergenceシステム上で定義された一般関数に一般化する。
このアルゴリズムは古典的および量子速度歪み理論に適用できる。
論文 参考訳（メタデータ） (2024-08-10T06:16:24Z) - Analyzing Prospects for Quantum Advantage in Topological Data Analysis [35.423446067065576]
我々は、トポロジカルデータ解析のための改良された量子アルゴリズムを解析し、最適化する。
超二次量子スピードアップは乗法誤差近似をターゲットとする場合にのみ可能であることを示す。
数百億のトフォリを持つ量子回路は、古典的に難解なインスタンスを解くことができると我々は主張する。
論文 参考訳（メタデータ） (2022-09-27T17:56:15Z) - A single $T$-gate makes distribution learning hard [56.045224655472865]
この研究は、局所量子回路の出力分布の学習可能性に関する広範な評価を提供する。
ハイブリッド量子古典アルゴリズムを含む多種多様な学習アルゴリズムにおいて、深度$d=omega(log(n))$ Clifford回路に関連する生成的モデリング問題さえも困難であることを示す。
論文 参考訳（メタデータ） (2022-07-07T08:04:15Z) - Quantum Assisted Eigensolver [0.0]
本研究では,ハミルトニアンの基底状態と基底状態エネルギーを近似するハイブリッド量子古典アルゴリズムを提案する。
アルゴリズムの量子部分からの出力を古典コンピュータの入力として利用する。
論文 参考訳（メタデータ） (2020-09-23T08:33:18Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。