論文の概要: 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 によって予想される最適長さと一致する。
量子アルゴリズムはまた、最適な古典的アルゴリズムによって引き出されたランダムなサンプル数に比べて必要な量子サンプル数において二次的な利点を達成し、その計算複雑性は量子サンプルを生成するのに使用されるマルコフ連鎖のスペクトルギャップに依存する。
関連論文リスト
- Sum-of-Squares inspired Quantum Metaheuristic for Polynomial Optimization with the Hadamard Test and Approximate Amplitude Constraints [76.53316706600717]
最近提案された量子アルゴリズムarXiv:2206.14999は半定値プログラミング(SDP)に基づいている
SDPにインスパイアされた量子アルゴリズムを2乗和に一般化する。
この結果から,本アルゴリズムは大きな問題に適応し,最もよく知られた古典学に近似することが示唆された。
論文 参考訳（メタデータ） (2024-08-14T19:04:13Z) - Quantum Subroutine for Variance Estimation: Algorithmic Design and Applications [80.04533958880862]
量子コンピューティングは、アルゴリズムを設計する新しい方法の基礎となる。
どの場の量子スピードアップが達成できるかという新たな課題が生じる。
量子サブルーチンの設計は、従来のサブルーチンよりも効率的で、新しい強力な量子アルゴリズムに固い柱を向ける。
論文 参考訳（メタデータ） (2024-02-26T09:32:07Z) - Variational Quantum Algorithms for the Allocation of Resources in a Cloud/Edge Architecture [1.072460284847973]
変分量子アルゴリズムは, 近い将来, 古典的アルゴリズムの代替となる可能性が示唆された。
特に、2つのアルゴリズム、すなわち量子近似最適化アルゴリズム(QAOA)と変分量子固有解器(VQE)の性能を比較した。
シミュレーション実験は、クラウドと2つのエッジノードを含む %CM230124 の単純な問題に対して実施され、VQE アルゴリズムは、検索空間を制限できる適切な回路テクスタイタンサッチを備えている場合に、より良い性能を保証することを示す。
論文 参考訳（メタデータ） (2024-01-25T17:37:40Z) - Fast Computation of Optimal Transport via Entropy-Regularized Extragradient Methods [75.34939761152587]
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) - Quantum jet clustering with LHC simulated data [0.0]
2つの新しい量子アルゴリズムは、古典的なジェットクラスタリングアルゴリズムを高速化する。
最初の2つのアルゴリズムでは、次元とデータ長の指数的なスピードアップを達成することができる。
k_T$アルゴリズムでは、FastJetと同じ順序の量子バージョンが達成される。
論文 参考訳（メタデータ） (2022-09-19T10:51:13Z) - 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) - Quantum vs. classical algorithms for solving the heat equation [0.04297070083645048]
量子コンピュータは、おそらく指数関数的に偏微分方程式を解くために古典的よりも優れていると予測されている。
ここでは、矩形領域における熱方程式である原始型PDEを考察し、それを解くための10の古典的および量子的アルゴリズムの複雑さを詳細に比較する。
論文 参考訳（メタデータ） (2020-04-14T13:57:47Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。