論文の概要: Simpler (classical) and faster (quantum) algorithms for Gibbs partition
functions
- arxiv url: http://arxiv.org/abs/2009.11270v5
- Date: Wed, 31 Aug 2022 00:38:44 GMT
- ステータス: 処理完了
- システム内更新日: 2023-05-01 04:46:22.335656
- Title: Simpler (classical) and faster (quantum) algorithms for Gibbs partition
functions
- Title(参考訳): gibbs分割関数のための単純(古典的)および高速(量子)アルゴリズム
- Authors: Srinivasan Arunachalam, Vojtech Havlicek, Giacomo Nannicini, Kristan
Temme, Pawel Wocjan
- Abstract要約: 古典ハミルトニアンの分配関数を所定の温度で近似するための古典的および量子的アルゴリズムを提案する。
我々は,vStefankovivc,Vempala,Vigodaの古典的アルゴリズムを改良し,サンプルの複雑さを改善する。
我々はこの新しいアルゴリズムを量子化し、HarrowとWeiにより、この問題に対してこれまで最速の量子アルゴリズムを改善した。
- 参考スコア(独自算出の注目度): 4.2698418800007865
- License: http://creativecommons.org/licenses/by-nc-sa/4.0/
- Abstract: We present classical and quantum algorithms for approximating partition
functions of classical Hamiltonians at a given temperature. Our work has two
main contributions: first, we modify the classical algorithm of
\v{S}tefankovi\v{c}, Vempala and Vigoda (\emph{J.~ACM}, 56(3), 2009) to improve
its sample complexity; second, we quantize this new algorithm, improving upon
the previously fastest quantum algorithm for this problem, due to Harrow and
Wei (SODA 2020). The conventional approach to estimating partition functions
requires approximating the means of Gibbs distributions at a set of inverse
temperatures that form the so-called cooling schedule. The length of the
cooling schedule directly affects the complexity of the algorithm. Combining
our improved version of the algorithm of \v{S}tefankovi\v{c}, Vempala and
Vigoda with the paired-product estimator of Huber (\emph{Ann.\ Appl.\ Probab.},
25(2),~2015), our new quantum algorithm uses a shorter cooling schedule than
previously known. This length matches the optimal length conjectured by
\v{S}tefankovi\v{c}, Vempala and Vigoda. The quantum algorithm also achieves a
quadratic advantage in the number of required quantum samples compared to the
number of random samples drawn by the best classical algorithm, and its
computational complexity has quadratically better dependence on the spectral
gap of the Markov chains used to produce the quantum samples.
- Abstract(参考訳): 与えられた温度で古典ハミルトニアンの分割関数を近似する古典アルゴリズムと量子アルゴリズムを提案する。
まず、古典的アルゴリズムである \v{S}tefankovi\v{c}, Vempala と Vigoda (\emph{J} の修正を行う。
~acm}, 56(3), 2009) 標本の複雑さを改善するため, この新しいアルゴリズムを量子化し, harrow と wei (soda 2020) によるこの問題に対する従来最速の量子アルゴリズムを改良した。
分割関数を推定する従来のアプローチでは、いわゆる冷却スケジュールを形成する逆温度のセットでギブス分布の手段を近似する必要がある。
冷却スケジュールの長さはアルゴリズムの複雑さに直接影響する。
改良されたアルゴリズムである \v{S}tefankovi\v{c}, Vempala, Vigoda と Huber (\emph{Ann) のペア積推定器を組み合わせた。
に登場。
プロバブ。
量子アルゴリズムは、これまで知られていたよりも短い冷却スケジュールを使用する。
この長さは \v{S}tefankovi\v{c}, Vempala と Vigoda によって予想される最適長さと一致する。
量子アルゴリズムはまた、最適な古典的アルゴリズムによって引き出されたランダムなサンプル数に比べて必要な量子サンプル数において二次的な利点を達成し、その計算複雑性は量子サンプルを生成するのに使用されるマルコフ連鎖のスペクトルギャップに依存する。
関連論文リスト
- Quantum Variational Algorithms for the Allocation of Resources in a
Cloud/Edge Architecture [1.1715858161748576]
クラウド/エッジアーキテクチャは、異種コンピューティングノードの複数のレイヤを編成する必要がある。
異なるノード上での計算の最適割り当てとスケジューリングは非常に難しい問題であり、NP困難である。
近い将来,変分量子アルゴリズムが古典的アルゴリズムの代替となる可能性が示唆された。
論文 参考訳(メタデータ) (2024-01-25T17:37:40Z) - Quantum Algorithms for the Pathwise Lasso [1.9374282535132377]
古典的LARS(Least Angle Regression)パスワイズアルゴリズムに基づく新しい量子高次元線形回帰アルゴリズムを提案する。
我々の量子アルゴリズムは、ペナルティ項が変化するにつれて、完全な正規化パスを提供するが、特定の条件下では、イテレーション毎に2次的に高速である。
論文 参考訳(メタデータ) (2023-12-21T18:57:54Z) - Fast Computation of Optimal Transport via Entropy-Regularized
Extragradient Methods [98.85583323658366]
2つの分布間の最適な輸送距離の効率的な計算は、様々な応用を促進するアルゴリズムとして機能する。
本稿では,$varepsilon$加法精度で最適な輸送を計算できるスケーラブルな一階最適化法を提案する。
論文 参考訳(メタデータ) (2023-01-30T15:46:39Z) - Quantum Clustering with k-Means: a Hybrid Approach [117.4705494502186]
我々は3つのハイブリッド量子k-Meansアルゴリズムを設計、実装、評価する。
我々は距離の計算を高速化するために量子現象を利用する。
我々は、我々のハイブリッド量子k-平均アルゴリズムが古典的バージョンよりも効率的であることを示す。
論文 参考訳(メタデータ) (2022-12-13T16:04:16Z) - A Sublinear-Time Quantum Algorithm for Approximating Partition Functions [0.0]
本稿では,ギブス分割関数を線形時間で推定する新しい量子アルゴリズムを提案する。
これは、vStefankovivc, Vempala, Vigodaの半周期的なほぼ直線時間で得られる最初のスピードアップである。
論文 参考訳(メタデータ) (2022-07-18T14:41:48Z) - Adaptive Algorithm for Quantum Amplitude Estimation [13.82667502131475]
振幅の間隔推定のための適応アルゴリズムを提案する。
提案アルゴリズムは、同じレベルの精度を達成するために、同じ数の量子クエリを使用する。
我々は,古典モンテカルロサンプリングに対する2次高速化として,オラクルクエリの数が$O(1/epsilon)$に達することを厳密に証明する。
論文 参考訳(メタデータ) (2022-06-16T21:11:15Z) - Entanglement and coherence in Bernstein-Vazirani algorithm [58.720142291102135]
Bernstein-Vaziraniアルゴリズムは、オラクルに符号化されたビット文字列を決定できる。
我々はベルンシュタイン・ヴァジラニアルゴリズムの量子資源を詳細に分析する。
絡み合いがない場合、初期状態における量子コヒーレンス量とアルゴリズムの性能が直接関係していることが示される。
論文 参考訳(メタデータ) (2022-05-26T20:32:36Z) - Twisted hybrid algorithms for combinatorial optimization [68.8204255655161]
提案されたハイブリッドアルゴリズムは、コスト関数をハミルトニアン問題にエンコードし、回路の複雑さの低い一連の状態によってエネルギーを最適化する。
レベル$p=2,ldots, 6$の場合、予想される近似比をほぼ維持しながら、レベル$p$を1に減らすことができる。
論文 参考訳(メタデータ) (2022-03-01T19:47:16Z) - Efficient Computation of Expectations under Spanning Tree Distributions [67.71280539312536]
本稿では,エッジファクター,非プロジェクティブ・スパンニングツリーモデルにおいて,一階期待と二階期待の重要なケースに対する統一アルゴリズムを提案する。
我々のアルゴリズムは勾配と期待の基本的な関係を利用しており、効率的なアルゴリズムを導出することができる。
論文 参考訳(メタデータ) (2020-08-29T14:58:26Z) - Learning to Accelerate Heuristic Searching for Large-Scale Maximum
Weighted b-Matching Problems in Online Advertising [51.97494906131859]
バイパルタイトbマッチングはアルゴリズム設計の基本であり、経済市場や労働市場などに広く適用されている。
既存の正確で近似的なアルゴリズムは、通常そのような設定で失敗する。
我々は、以前の事例から学んだ知識を活用して、新しい問題インスタンスを解決するtextttNeuSearcherを提案する。
論文 参考訳(メタデータ) (2020-05-09T02:48:23Z) - Quantum vs. classical algorithms for solving the heat equation [0.04297070083645048]
量子コンピュータは、おそらく指数関数的に偏微分方程式を解くために古典的よりも優れていると予測されている。
ここでは、矩形領域における熱方程式である原始型PDEを考察し、それを解くための10の古典的および量子的アルゴリズムの複雑さを詳細に比較する。
論文 参考訳(メタデータ) (2020-04-14T13:57:47Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト(すべての情報・翻訳含む)の品質を保証せず、本サイト(すべての情報・翻訳含む)を使用して発生したあらゆる結果について一切の責任を負いません。