論文の概要: Efficient Learning Implies Quantum Glassiness

• arxiv url: http://arxiv.org/abs/2505.00087v1
• Date: Wed, 30 Apr 2025 18:00:29 GMT
• ステータス: 翻訳完了
• システム内更新日: 2025-05-02 19:15:55.140582
• Title: Efficient Learning Implies Quantum Glassiness
• Title（参考訳）: 効率的な学習は量子ガラス性に影響を及ぼす
• Authors: Eric R. Anschuetz,
• Abstract要約: 量子学習理論とアルゴリズムの硬さの驚くべき関係を示す。 量子アルゴリズムの「Lipschitz」では,スパース乱れの量子系の近傍状態の発見が平均的に困難であることを示す。
• 参考スコア（独自算出の注目度）: 0.0
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: We show a surprising relation between quantum learning theory and algorithmic hardness. We demonstrate that finding near-ground states of certain sparse disordered quantum systems is average-case hard for "Lipschitz" quantum algorithms if there exists an efficient, local learning algorithm -- such as the classical shadows algorithm -- for estimating the energy of a state of the system. A corollary of our result is that many standard quantum algorithms fail to find near-ground states of these systems, including short-time Lindbladian dynamics, short-time quantum annealing, phase estimation, and shallow-depth variational quantum algorithms. To achieve this, we introduce a topological property of quantum systems that we call the quantum overlap gap property (QOGP). This property is only satisfied by systems with an efficient local learning algorithm for the energy. We prove that systems which exhibit this topological property in their low-energy space are intractable for quantum algorithms whose outputs are stable under perturbations to their inputs. We then prove that the QOGP is satisfied for a sparsified variant of the quantum $p$-spin model, giving the first known algorithmic hardness-of-approximation result for quantum algorithms in finding the ground state of a non-stoquastic, noncommuting quantum system. Our resulting lower bound for quantum algorithms optimizing this model using Lindbladian evolution matches the best-known time lower bound for classical Langevin dynamics optimizing classical $p$-spin models. For this reason we suspect that finding ground states of typical quantum $p$-spin models using quantum algorithms is, in practice, as intractable as the classical $p$-spin model is for classical algorithms. Inversely, we show that the Sachdev--Ye--Kitaev (SYK) model does not exhibit the QOGP, consistent with previous evidence that the model is rapidly mixing at low temperatures.
• Abstract（参考訳）: 量子学習理論とアルゴリズムの硬さの驚くべき関係を示す。 従来のシャドウアルゴリズムのような効率的で局所的な学習アルゴリズムがシステムの状態のエネルギーを推定するために存在する場合、「Lipschitz」量子アルゴリズムでは、特定のスパース乱れ量子系の準基底状態を見つけることは、平均ケースが難しいことを実証する。 結果として、多くの標準的な量子アルゴリズムは、短時間のリンドブレディアン力学、短時間の量子アニール、位相推定、浅深さの変動量子アルゴリズムなど、これらのシステムのほぼ基底状態を見つけられなかった。 これを実現するために、量子オーバーラップギャップ特性(QOGP)と呼ばれる量子システムのトポロジ的特性を導入する。 この性質は、エネルギーの効率的な局所学習アルゴリズムを持つシステムによってのみ満たされる。 低エネルギー空間におけるこのトポロジ的特性を示すシステムは、入力に対する摂動の下で出力が安定な量子アルゴリズムにとって魅力的なものであることを証明した。 次に、QOGPが量子$p$-spinモデルのスパーシフィケーション変種に対して満足していることが証明され、非確率的、非可換な量子系の基底状態を見つけるための量子アルゴリズムのアルゴリズム的硬度-近似結果が最初に知られる。 我々の導出した量子アルゴリズムの下位境界は、古典的な$p$スピンモデルを最適化する古典的なランゲヴィン力学の最もよく知られた時間下限と一致する。 このため、量子アルゴリズムを用いて典型的な$p$-spinモデルの基底状態を見つけることは、古典的な$p$-spinモデルが古典的なアルゴリズムであるように、実際は難解である。 逆に、Sachdev--Ye-Kitaevモデル(SYK)がQOGPを示さないことを示す。

関連論文リスト

• Quantum phase classification via quantum hypothesis testing [0.39102514525861415]
  理論的には2つの量子状態の区別に最適である量子ネイマン・ピアソン検定に基づく分類アルゴリズムを提案する。 その結果,提案手法は低い分類誤差確率を実現し,トレーニングコストを大幅に削減できることがわかった。 これらの知見は、量子位相分類の強力なツールとしての量子仮説テストの可能性を強調している。
  論文  参考訳（メタデータ） (2025-04-05T08:23:45Z)
• Accelerating Quantum Reinforcement Learning with a Quantum Natural Policy Gradient Based Approach [36.05085942729295]
  本稿では、古典的なNPG推定器で使用されるランダムサンプリングを決定論的勾配推定手法で置き換える量子自然ポリシー勾配(QNPG)アルゴリズムを提案する。 提案したQNPGアルゴリズムは、量子オラクルへのクエリに対する$tildemathcalO(epsilon-1.5)$のサンプル複雑性を達成し、マルコフ決定プロセス(MDP)へのクエリに対する$tildemathcalO(epsilon-2)$の古典的な下界を大幅に改善する。
  論文  参考訳（メタデータ） (2025-01-27T17:38:30Z)
• Quantum Subroutines in Branch-Price-and-Cut for Vehicle Routing [0.0]
  この研究で、限られた資源を持つ量子がNPハード問題に対する大規模な正確な最適化アルゴリズムにどのように統合できるかを実証する。 我々のアルゴリズムの重要な特徴は、量子によって返される最良の解からではなく、あるコスト閾値以下の全ての解から得られることである。
  論文  参考訳（メタデータ） (2024-12-20T08:27:23Z)
• Efficient Quantum Pseudorandomness from Hamiltonian Phase States [41.94295877935867]
  我々は、ハミルトニアン相状態(HPS)問題と呼ばれる量子硬度仮定を導入する。 我々は、我々の仮定が少なくとも完全に量子的であることを示し、すなわち片方向関数を構成するのに使用できない。 仮定とその変形により、多くの擬似ランダム量子プリミティブを効率的に構築できることを示す。
  論文  参考訳（メタデータ） (2024-10-10T16:10:10Z)
• An Efficient Classical Algorithm for Simulating Short Time 2D Quantum Dynamics [2.891413712995642]
  本稿では,2次元量子システムにおける短時間のダイナミクスをシミュレーションする,効率的な古典的アルゴリズムを提案する。 この結果から, 短時間2次元量子力学の複雑さに固有の単純さが明らかとなった。 この研究は、古典計算と量子計算の境界についての理解を深める。
  論文  参考訳（メタデータ） (2024-09-06T09:59:12Z)
• Quantum quench dynamics as a shortcut to adiabaticity [31.114245664719455]
  本研究では,クエンチステップを組み込んだ量子アルゴリズムを,変分するアディバティック・タイムスケールに対する対策として開発・テストする。 実験の結果,本手法は断熱アルゴリズムよりも有意に優れていることがわかった。
  論文  参考訳（メタデータ） (2024-05-31T17:07:43Z)
• Rapidly Achieving Chemical Accuracy with Quantum Computing Enforced Language Model [22.163742052849432]
  QiankunNet-VQEは量子コンピューティングを用いて量子状態の学習と生成を行うトランスフォーマーベースの言語モデルである。 最大12キュービットで実装され、最先端の古典的手法と競合する精度のレベルに達した。
  論文  参考訳（メタデータ） (2024-05-15T07:50:57Z)
• Quantum Annealing for Single Image Super-Resolution [86.69338893753886]
  単一画像超解像(SISR)問題を解くために,量子コンピューティングに基づくアルゴリズムを提案する。 提案したAQCアルゴリズムは、SISRの精度を維持しつつ、古典的なアナログよりも向上したスピードアップを実現する。
  論文  参考訳（メタデータ） (2023-04-18T11:57:15Z)
• Quantum Thermal State Preparation [39.91303506884272]
  量子マスター方程式をシミュレートするための簡単な連続時間量子ギブスサンプリングを導入する。 我々は、特定の純ギブス状態を作成するための証明可能かつ効率的なアルゴリズムを構築した。 アルゴリズムのコストは温度、精度、混合時間に依存している。
  論文  参考訳（メタデータ） (2023-03-31T17:29:56Z)
• QuanGCN: Noise-Adaptive Training for Robust Quantum Graph Convolutional Networks [124.7972093110732]
  本稿では,ノード間の局所的なメッセージパッシングをクロスゲート量子演算のシーケンスで学習する量子グラフ畳み込みネットワーク(QuanGCN)を提案する。 現代の量子デバイスから固有のノイズを緩和するために、ノードの接続をスパーズするためにスパース制約を適用します。 我々のQuanGCNは、いくつかのベンチマークグラフデータセットの古典的なアルゴリズムよりも機能的に同等か、さらに優れている。
  論文  参考訳（メタデータ） (2022-11-09T21:43:16Z)
• Classical simulation of short-time quantum dynamics [0.0]
  局所観測可能量と非局所量のダイナミクスを近似する古典的アルゴリズムを提案する。 我々は、新しい量子速度限界、動的相転移の束縛、および製品状態の束縛された濃度を短期間に発展させた。
  論文  参考訳（メタデータ） (2022-10-20T18:00:04Z)
• Surviving The Barren Plateau in Variational Quantum Circuits with Bayesian Learning Initialization [0.0]
  変分量子古典ハイブリッドアルゴリズムは、近い将来に量子コンピュータの実用的な問題を解くための有望な戦略と見なされている。 本稿では,ベイズ空間における有望な領域を特定するために勾配を用いた高速・スローアルゴリズムを提案する。 本研究は, 量子化学, 最適化, 量子シミュレーション問題における変分量子アルゴリズムの応用に近づいたものである。
  論文  参考訳（メタデータ） (2022-03-04T17:48:57Z)
• Quantum algorithms for quantum dynamics: A performance study on the spin-boson model [68.8204255655161]
  量子力学シミュレーションのための量子アルゴリズムは、伝統的に時間進化作用素のトロッター近似の実装に基づいている。 変分量子アルゴリズムは欠かせない代替手段となり、現在のハードウェア上での小規模なシミュレーションを可能にしている。 量子ゲートコストが明らかに削減されているにもかかわらず、現在の実装における変分法は量子的優位性をもたらすことはありそうにない。
  論文  参考訳（メタデータ） (2021-08-09T18:00:05Z)

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

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