論文の概要: Effective gaps are not effective: quasipolynomial classical simulation
of obstructed stoquastic Hamiltonians
- arxiv url: http://arxiv.org/abs/2004.08681v3
- Date: Wed, 21 Oct 2020 20:11:24 GMT
- ステータス: 処理完了
- システム内更新日: 2023-05-23 02:37:22.955130
- Title: Effective gaps are not effective: quasipolynomial classical simulation
of obstructed stoquastic Hamiltonians
- Title（参考訳）: 実効的ギャップは有効ではない:ブロックされた確率的ハミルトンの準多項古典シミュレーション
- Authors: Jacob Bringewatt and Michael Jarret
- Abstract要約: 古典的アルゴリズムは、$k$-局所確率的ハミルトニアン$H$の有効部分空間から効率的にサンプリングする。
我々の結果は、k$-ローカルハミルトニアンの隠れ対称性から生じる古典計算と確率的AQCの指数関数的分離を除外する。
- 参考スコア（独自算出の注目度）: 0.0
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: All known examples confirming the possibility of an exponential separation
between classical simulation algorithms and stoquastic adiabatic quantum
computing (AQC) exploit symmetries that constrain adiabatic dynamics to
effective, symmetric subspaces. The symmetries produce large effective
eigenvalue gaps, which in turn make adiabatic computation efficient. We present
a classical algorithm to efficiently sample from the effective subspace of a
$k$-local stoquastic Hamiltonian $H$, without a priori knowledge of its
symmetries (or near-symmetries). Our algorithm maps any $k$-local Hamiltonian
to a graph $G=(V,E)$ with $\lvert V \rvert = O\left(\mathrm{poly}(n)\right)$
where $n$ is the number of qubits. Given the well-known result of Babai, we
exploit graph isomorphism to study the automorphisms of $G$ and arrive at an
algorithm quasi-polynomial in $\lvert V\rvert$ for producing samples from the
effective subspace eigenstates of $H$. Our results rule out exponential
separations between stoquastic AQC and classical computation that arise from
hidden symmetries in $k$-local Hamiltonians. Furthermore, our graph
representation of $H$ is not limited to stoquastic Hamiltonians and may rule
out corresponding obstructions in non-stoquastic cases, or be useful in
studying additional properties of $k$-local Hamiltonians.
- Abstract（参考訳）: 古典的シミュレーションアルゴリズムと確率的断熱量子コンピューティング(aqc)の間の指数的分離の可能性を確認するすべての既知の例は、断熱力学を効果的で対称な部分空間に制限する対称性を利用する。
対称性は大きな有効固有値ギャップを生成し、それによって断熱計算を効率的にする。
古典的アルゴリズムは、その対称性(あるいは近対称性)の事前知識を伴わずに、$k$-局所確率的ハミルトニアン$H$の有効部分空間から効率的にサンプリングする。
我々のアルゴリズムは任意の$k$-局所ハミルトニアンを、$\lvert V \rvert = O\left(\mathrm{poly}(n)\right)$でグラフ $G=(V,E)$ にマッピングする。
ババイのよく知られた結果から、グラフ同型を利用して$G$の自己同型を研究し、$\lvert V\rvert$のアルゴリズム準多項式に到達して、有効部分空間固有状態からサンプルを生成する。
我々の結果は、k$-ローカルハミルトニアンの隠れ対称性から生じる古典計算と確率的AQCの指数関数的分離を除外する。
さらに、h$ のグラフ表現は確率的ハミルトニアンに限らず、非確率的場合における対応する障害を排除したり、k$ 局所ハミルトニアンの追加的性質を研究するのに有用である。
関連論文リスト
- Automorphism-Assisted Quantum Approximate Optimization Algorithm for efficient graph optimization [0.0]
我々は、グラフ自己同型を識別するために、Nautyパッケージを使用し、エッジ同値クラスを決定することに重点を置いている。
これらの対称性を利用することで、ハミルトニアンの複雑性を著しく低減することができる。
この結果から, 自己同型に基づく対称性を用いて, 得られた解の質を損なうことなく, 計算オーバーヘッドを著しく低減できることが示唆された。
論文 参考訳（メタデータ） (2024-10-29T17:10:25Z) - Predicting Ground State Properties: Constant Sample Complexity and Deep Learning Algorithms [48.869199703062606]
量子多体物理学における基本的な問題は、局所ハミルトニアンの基底状態を見つけることである。
基底状態特性を学習するためのシステムサイズ$n$とは無関係に,一定のサンプル複雑性を実現する2つのアプローチを導入する。
論文 参考訳（メタデータ） (2024-05-28T18:00:32Z) - Composite QDrift-Product Formulas for Quantum and Classical Simulations
in Real and Imaginary Time [0.18374319565577155]
最近の研究は、与えられたシミュレーション問題に対してハミルトニアン$H$をサブセットに分割する合成チャネルを実装するのが有利であることを示した。
このアプローチは想像上の時間で成り立ち、量子モンテカルロ計算の古典的アルゴリズムの候補となる。
一定の誤差耐性を満たすために,$e-iH_j t$および$e-H_j beta$のゲート数を数えることにより,アルゴリズムコストの正確な数値シミュレーションを行う。
論文 参考訳（メタデータ） (2023-06-28T21:31:26Z) - Learning quantum symmetries with interactive quantum-classical
variational algorithms [0.0]
状態 $vert psi rangle$ の対称性は単位作用素であり、$vert psi rangle$ は固有ベクトルである。
対称性は量子システムに 重要な物理的な洞察を与えます
我々は,$vert psi rangle$の対称性を体系的に探索する変分型量子古典学習法を開発した。
論文 参考訳（メタデータ） (2022-06-23T20:41:26Z) - Learning a Single Neuron with Adversarial Label Noise via Gradient
Descent [50.659479930171585]
モノトン活性化に対する $mathbfxmapstosigma(mathbfwcdotmathbfx)$ の関数について検討する。
学習者の目標は仮説ベクトル $mathbfw$ that $F(mathbbw)=C, epsilon$ を高い確率で出力することである。
論文 参考訳（メタデータ） (2022-06-17T17:55:43Z) - Hamiltonian simulation with random inputs [74.82351543483588]
ランダム初期状態を持つハミルトンシミュレーションの平均ケース性能の理論
数値的な証拠は、この理論がコンクリート模型の平均誤差を正確に特徴づけていることを示唆している。
論文 参考訳（メタデータ） (2021-11-08T19:08:42Z) - Hybridized Methods for Quantum Simulation in the Interaction Picture [69.02115180674885]
本研究では,異なるシミュレーション手法をハイブリダイズし,インタラクション・ピクチャー・シミュレーションの性能を向上させるフレームワークを提案する。
これらのハイブリッド化手法の物理的応用は、電気遮断において$log2 Lambda$としてゲート複雑性のスケーリングをもたらす。
力学的な制約を受けるハミルトニアンシミュレーションの一般的な問題に対して、これらの手法は、エネルギーコストを課すために使われるペナルティパラメータ$lambda$とは無関係に、クエリの複雑さをもたらす。
論文 参考訳（メタデータ） (2021-09-07T20:01:22Z) - Quantum algorithm for time-dependent Hamiltonian simulation by
permutation expansion [6.338178373376447]
時間依存ハミルトニアンの力学シミュレーションのための量子アルゴリズムを提案する。
アルゴリズムのコストはハミルトニアン周波数に依存しないことを示す。
論文 参考訳（メタデータ） (2021-03-29T05:02:02Z) - Enhancing the Quantum Linear Systems Algorithm using Richardson
Extrapolation [0.8057006406834467]
Amathbfx=mathbfb$という形の線形方程式の系を解く量子アルゴリズムを提案する。
このアルゴリズムは古典的手法に対して$N$に対して指数関数的に改善する。
論文 参考訳（メタデータ） (2020-09-09T18:00:09Z) - Learning Halfspaces with Tsybakov Noise [50.659479930171585]
テュバコフ雑音の存在下でのハーフスペースの学習可能性について検討する。
真半空間に関して誤分類誤差$epsilon$を達成するアルゴリズムを与える。
論文 参考訳（メタデータ） (2020-06-11T14:25:02Z) - Complexity of Finding Stationary Points of Nonsmooth Nonconvex Functions [84.49087114959872]
非滑らかで非滑らかな関数の定常点を見つけるための最初の非漸近解析を提供する。
特に、アダマール半微分可能函数(おそらく非滑らか関数の最大のクラス)について研究する。
論文 参考訳（メタデータ） (2020-02-10T23:23:04Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。