論文の概要: A Sublinear-Time Quantum Algorithm for Approximating Partition Functions
- arxiv url: http://arxiv.org/abs/2207.08643v1
- Date: Mon, 18 Jul 2022 14:41:48 GMT
- ステータス: 処理完了
- システム内更新日: 2022-07-19 19:15:36.809895
- Title: A Sublinear-Time Quantum Algorithm for Approximating Partition Functions
- Title（参考訳）: 分割関数近似のためのサブ線形時間量子アルゴリズム
- Authors: Arjan Cornelissen and Yassine Hamoudi
- Abstract要約: 本稿では,ギブス分割関数を線形時間で推定する新しい量子アルゴリズムを提案する。
これは、vStefankovivc, Vempala, Vigodaの半周期的なほぼ直線時間で得られる最初のスピードアップである。
- 参考スコア（独自算出の注目度）: 0.0
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: We present a novel quantum algorithm for estimating Gibbs partition functions
in sublinear time with respect to the logarithm of the size of the state space.
This is the first speed-up of this type to be obtained over the seminal
nearly-linear time algorithm of \v{S}tefankovi\v{c}, Vempala and Vigoda [JACM,
2009]. Our result also preserves the quadratic speed-up in precision and
spectral gap achieved in previous work by exploiting the properties of quantum
Markov chains. As an application, we obtain new polynomial improvements over
the best-known algorithms for computing the partition function of the Ising
model, and counting the number of $k$-colorings, matchings or independent sets
of a graph.
Our approach relies on developing new variants of the quantum phase and
amplitude estimation algorithms that return nearly unbiased estimates with low
variance and without destroying their initial quantum state. We extend these
subroutines into a nearly unbiased quantum mean estimator that reduces the
variance quadratically faster than the classical empirical mean. No such
estimator was known to exist prior to our work. These properties, which are of
general interest, lead to better convergence guarantees within the paradigm of
simulated annealing for computing partition functions.
- Abstract（参考訳）: 本稿では, 状態空間の大きさの対数に関して, gibbs分割関数をサブリニア時間で推定する新しい量子アルゴリズムを提案する。
これは、v{S}tefankovi\v{c}, Vempala and Vigoda [JACM, 2009] の半正準線形時間アルゴリズム上で得られるこのタイプの最初のスピードアップである。
また, 量子マルコフ鎖の性質を生かして, 先行研究で達成された精度とスペクトルギャップの2次速度を保った。
応用として、Isingモデルの分割関数を計算し、グラフの$k$-colorings, matchings, independent setの数をカウントする最もよく知られたアルゴリズムに対して、新しい多項式改善が得られる。
我々のアプローチは、量子位相および振幅推定アルゴリズムの新しい変種を開発し、低分散で初期量子状態を破壊することなくほぼ偏りのない推定値を返す。
これらのサブルーチンをほぼ偏りのない量子平均推定器に拡張し、古典的経験平均よりも二乗的に分散を減少させる。
そのような推定者は我々の仕事の前には存在しなかった。
これらの性質は一般に興味を持ち、計算分割関数のシミュレーションアニールのパラダイム内での収束性を保証する。
関連論文リスト
- Kernel Descent -- a Novel Optimizer for Variational Quantum Algorithms [0.0]
変動量子アルゴリズムの基礎となる関数を最小化するための新しいアルゴリズムであるカーネル降下を導入する。
特に、カーネル降下が勾配降下と量子解析降下より優れるシナリオを示す。
カーネル降下は、局所近似の構築において、再生されたカーネルヒルベルト空間技術(英語版)を使わずに、自身を分離する。
論文 参考訳（メタデータ） (2024-09-16T13:10:26Z) - Application of Langevin Dynamics to Advance the Quantum Natural Gradient Optimization Algorithm [47.47843839099175]
近年,変分量子回路の最適化のためのQNGアルゴリズムが提案されている。
本研究では、この離散時間解が一般化形式を与えることを示すために、QNG力を持つランゲヴィン方程式を用いる。
論文 参考訳（メタデータ） (2024-09-03T15:21:16Z) - Evaluation of phase shifts for non-relativistic elastic scattering using quantum computers [39.58317527488534]
本研究は, 量子コンピュータ上での一般相対論的非弾性散乱過程の位相シフトを求めるアルゴリズムの開発を報告する。
論文 参考訳（メタデータ） (2024-07-04T21:11:05Z) - A quantum advantage over classical for local max cut [48.02822142773719]
量子最適化近似アルゴリズム(QAOA)は、次数3グラフ上の古典的手法に匹敵する計算上の優位性を持つ。
結果として、最先端の量子ハードウェアに関係している小規模量子計算でさえ、比較可能な単純な古典よりも大きな優位性を持つ可能性が示唆された。
論文 参考訳（メタデータ） (2023-04-17T16:42:05Z) - Faster variational quantum algorithms with quantum kernel-based
surrogate models [0.0]
本稿では,雑音量子プロセッサ上での小型から中規模の変分アルゴリズムを提案する。
提案手法は,計算負荷をこれらのハイブリッドアルゴリズムの古典的成分にシフトさせ,量子プロセッサへのクエリ数を劇的に削減する。
論文 参考訳（メタデータ） (2022-11-02T14:11:25Z) - Analyzing Prospects for Quantum Advantage in Topological Data Analysis [35.423446067065576]
我々は、トポロジカルデータ解析のための改良された量子アルゴリズムを解析し、最適化する。
超二次量子スピードアップは乗法誤差近似をターゲットとする場合にのみ可能であることを示す。
数百億のトフォリを持つ量子回路は、古典的に難解なインスタンスを解くことができると我々は主張する。
論文 参考訳（メタデータ） (2022-09-27T17:56:15Z) - Mitigating algorithmic errors in quantum optimization through energy
extrapolation [4.426846282723645]
基底状態エネルギーの推定において、非無視誤差を緩和するスケーラブルな外挿法を提案する。
我々は,IBM量子コンピュータ上での数値シミュレーションと実験により,これらの手法の有効性を検証した。
論文 参考訳（メタデータ） (2021-09-16T17:39:11Z) - Quantum algorithms for quantum dynamics: A performance study on the
spin-boson model [68.8204255655161]
量子力学シミュレーションのための量子アルゴリズムは、伝統的に時間進化作用素のトロッター近似の実装に基づいている。
変分量子アルゴリズムは欠かせない代替手段となり、現在のハードウェア上での小規模なシミュレーションを可能にしている。
量子ゲートコストが明らかに削減されているにもかかわらず、現在の実装における変分法は量子的優位性をもたらすことはありそうにない。
論文 参考訳（メタデータ） (2021-08-09T18:00:05Z) - Simpler (classical) and faster (quantum) algorithms for Gibbs partition
functions [4.2698418800007865]
古典ハミルトニアンの分配関数を所定の温度で近似するための古典的および量子的アルゴリズムを提案する。
我々は,vStefankovivc,Vempala,Vigodaの古典的アルゴリズムを改良し,サンプルの複雑さを改善する。
我々はこの新しいアルゴリズムを量子化し、HarrowとWeiにより、この問題に対してこれまで最速の量子アルゴリズムを改善した。
論文 参考訳（メタデータ） (2020-09-23T17:27:28Z) - Momentum Q-learning with Finite-Sample Convergence Guarantee [49.38471009162477]
本稿では,有限サンプル保証を用いたモーメントに基づくQ-ラーニングアルゴリズムのクラスを解析する。
線形関数近似とマルコフサンプリングによるMomentumQの収束保証を確立する。
提案したMomentumQが他のモーメントベースのQ-ラーニングアルゴリズムより優れていることを示す。
論文 参考訳（メタデータ） (2020-07-30T12:27:03Z) - Efficient Algorithms for Approximating Quantum Partition Functions [0.0]
我々は,高温における量子スピンモデルの分配関数の時間近似アルゴリズムを確立する。
我々の主な貢献は、有界グラフ上の対相互作用の場合の単純でわずかにシャープな分析である。
論文 参考訳（メタデータ） (2020-04-24T07:21:43Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。