論文の概要: Quantum advantage from random geometrically-two-local Hamiltonian dynamics

• arxiv url: http://arxiv.org/abs/2510.06321v1
• Date: Tue, 07 Oct 2025 18:00:02 GMT
• ステータス: 翻訳完了
• システム内更新日: 2025-10-09 16:41:20.121792
• Title: Quantum advantage from random geometrically-two-local Hamiltonian dynamics
• Title（参考訳）: ランダムな幾何学的二局所ハミルトン力学による量子優位性
• Authors: Yihui Quek,
• Abstract要約: 幾何学的に2-局所ハミルトニアン進化の出力確率を近似する最初の最悪の平均ケース削減法を開発した。 また,誤り評価に対処するため,Berlekamp-Welchのアルゴリズム版も提案する。
• 参考スコア（独自算出の注目度）: 1.3537117504260623
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: Classical hardness-of-sampling results are largely established for random quantum circuits, whereas analog simulators natively realize time evolutions under geometrically local Hamiltonians. Does a typical such Hamiltonian already yield classically-intractable dynamics? We answer this question in the affirmative for the ensemble of geometrically-2-local Hamiltonians with Gaussian coefficients, evolved for constant time. This naturally leads to a quantum advantage scheme with clear prospects for experimental realization, necessitating only course-grained control. We give strong evidence of hardness for this physically-relevant ensemble. We develop the first worst-to-average-case reduction for approximating output probabilities of (time-independent) geometrically-2-local Hamiltonian evolutions. Our reduction proceeds by nonstandard means: while we also leverage polynomial interpolation, unlike previous works, we reduce directly to an evaluator for the exact distribution over Hamiltonians, from which we are trying to prove that sampling is hard. Previous works instead sampled from various perturbations of the true distribution, introducing additional constraints meant to keep the perturbation, measured in total variation distance, under control. We dispense with this step. Our reduction consists in a robust multivariate polynomial interpolation, reduced to sequential robust univariate interpolations via the symmetries of the Gaussian. We circumvent the fact that random Hamiltonians lack a hiding symmetry, a key property in previous proofs. We also contribute an algorithmic version of Berlekamp-Welch to deal with errored evaluations, solving an open problem from the RCS literature. We expect the machinery we develop to find use in average-case Hamiltonian complexity, filling in a gap in this literature which has thus far focussed on worst-case hardness results.
• Abstract（参考訳）: 古典的なハードネス・オブ・サンプリングの結果は、主にランダム量子回路に対して確立されているが、アナログシミュレーターは幾何学的に局所的なハミルトニアンの下での時間進化を自然に実現している。 そのような典型的なハミルトニアンはすでに古典的に難解な力学を得られるか。 ガウス係数を持つ幾何学的に2-局所ハミルトニアンのアンサンブルに対する肯定的証明において、この疑問に答える。 これは自然に、実験的な実現のための明確な可能性を持つ量子優位スキームにつながり、コースのきめ細かい制御しか必要としない。 我々はこの物理的に関係のあるアンサンブルの硬さの強い証拠を与える。 我々は、幾何学的に(2-局所ハミルトン進化の(時間に依存しない)出力確率を近似するための、最初の最悪の平均ケース削減法を開発した。 我々の還元は非標準的手段によって進行する: 多項式補間も活用するが、以前の研究とは異なり、標本サンプリングが困難であることを証明しようとするハミルトン多様体上の正確な分布に対する評価器に直接還元する。 以前の研究は真の分布の様々な摂動からサンプリングされ、全変動距離で測定された摂動を維持するための追加の制約が導入された。 私たちはこのステップを省きます。 我々の還元は頑健な多変量多項式補間から成り、ガウスの対称性を介して連続的に頑健な単変量補間へと還元される。 ランダムハミルトニアンには隠れ対称性がないという事実を回避し、これは以前の証明の鍵となる性質である。 我々はまた、誤り評価に対処し、RCS文献から解き放たれた問題を解くために、Berlekamp-Welchのアルゴリズム版にも貢献する。 私たちが開発している機械は、平均ケースハミルトンの複雑さで使われ、この文献のギャップを埋めることを期待しています。

関連論文リスト

• Lower Bounds for Learning Hamiltonians from Time Evolution [5.118083299467833]
  我々はハミルトニアンを時間進化から学ぶことの問題を考察する。 逆時間分解能を持つ任意の学習アルゴリズムは、超ポリノミカルな全進化時間を必要とすることを示す。
  論文  参考訳（メタデータ） (2025-09-25T01:50:55Z)
• Shot-noise reduction for lattice Hamiltonians [0.7852714805965528]
  格子ハミルトンのエネルギー期待値を量子コンピュータ上で効率的に推定することは深刻な課題である。 拡張性のある代替手段として幾何学的分割を導入する。 サンプリング数の改善が不完全な固有状態の改善にどのように寄与するかを示す。
  論文  参考訳（メタデータ） (2024-10-28T17:50:28Z)
• Bayesian Circular Regression with von Mises Quasi-Processes [57.88921637944379]
  本研究では、円値ランダム関数上の表現的および解釈可能な分布の族を探索する。 後部推論のために,高速ギブズサンプリングに寄与するストラトノビッチ様拡張法を導入する。 本研究では,このモデルを用いて風向予測と走行歩行周期のパーセンテージを関節角度の関数として適用する実験を行った。
  論文  参考訳（メタデータ） (2024-06-19T01:57:21Z)
• Spectral form factor in a minimal bosonic model of many-body quantum chaos [1.3793594968500609]
  周期的結合ボソニック鎖のスペクトル形成因子について検討した。 我々は、Thouless 時間における非自明な体系的システムサイズ依存を数値的に見出す。
  論文  参考訳（メタデータ） (2022-03-10T15:56:24Z)
• 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)
• Algebraic Compression of Quantum Circuits for Hamiltonian Evolution [52.77024349608834]
  時間依存ハミルトニアンの下でのユニタリ進化は、量子ハードウェアにおけるシミュレーションの重要な構成要素である。 本稿では、トロッターステップを1ブロックの量子ゲートに圧縮するアルゴリズムを提案する。 この結果、ハミルトニアンのある種のクラスに対する固定深度時間進化がもたらされる。
  論文  参考訳（メタデータ） (2021-08-06T19:38:01Z)

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

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