論文の概要: Quantum Speedup for Nonreversible Markov Chains
- arxiv url: http://arxiv.org/abs/2501.05868v1
- Date: Fri, 10 Jan 2025 11:09:40 GMT
- ステータス: 翻訳完了
- システム内更新日: 2025-01-13 15:26:17.199682
- Title: Quantum Speedup for Nonreversible Markov Chains
- Title（参考訳）: 非可逆マルコフ鎖の量子スピードアップ
- Authors: Baptiste Claudon, Jean-Philip Piquemal, Pierre Monmarché,
- Abstract要約: マルコフ連鎖の問題は量子コンピューティングによってかなり高速に解けることが議論されている。
本研究では、現代の量子アルゴリズムとマルコフ連鎖理論を用いて、非可逆マルコフ鎖の定常分布をサンプリングする。
- 参考スコア（独自算出の注目度）: 0.0
- License:
- Abstract: Quantum algorithms can potentially solve a handful of problems more efficiently than their classical counterparts. In that context, it has been discussed that Markov chains problems could be solved significantly faster using quantum computing. Indeed, previous work suggests that quantum computers could accelerate sampling from the stationary distribution of reversible Markov chains. However, in practice, certain physical processes of interest are nonreversible in the probabilistic sense and reversible Markov chains can sometimes be replaced by more efficient nonreversible chains targeting the same stationary distribution. This study uses modern quantum algorithmic techniques and Markov chain theory to sample from the stationary distribution of nonreversible Markov chains with faster worst-case runtime and without requiring the stationary distribution to be computed up to a multiplicative constant. Such an up-to-exponential quantum speedup goes beyond the predicted quadratic quantum acceleration for reversible chains and is likely to have a decisive impact on many applications ranging from statistics and machine learning to computational modeling in physics, chemistry, biology and finance.
- Abstract（参考訳）: 量子アルゴリズムは、古典的なアルゴリズムよりも効率的にいくつかの問題を解くことができる。
この文脈では、マルコフ連鎖の問題は量子コンピューティングを用いてかなり高速に解けることが議論されている。
実際、以前の研究は、量子コンピュータが可逆マルコフ鎖の定常分布からのサンプリングを加速することを示唆している。
しかし、実際には、ある物理的過程は確率論的意味では可逆であり、可逆マルコフ鎖は時として同じ定常分布を対象とするより効率的な非可逆鎖に置き換えられる。
本研究は, 量子アルゴリズムとマルコフ連鎖理論を用いて, より高速で, 定常分布を乗法定数まで計算することなく, 非可逆マルコフ鎖の定常分布をサンプリングする。
このような上述の量子スピードアップは、可逆鎖の予測された二次量子加速を超えており、統計学や機械学習から物理学、化学、生物学、ファイナンスにおける計算モデリングまで、多くのアプリケーションに決定的な影響を与える可能性がある。
関連論文リスト
- Bounding speedup of quantum-enhanced Markov chain Monte Carlo [0.0]
最悪ケースの非構造サンプリング問題に対して,古典的なサンプリングよりも高速であることを示す。
我々は、任意のユニタリ量子提案のスピードアップを規定するマルコフギャップに上限を与える。
論文 参考訳（メタデータ） (2024-03-05T16:20:01Z) - Stochastic Quantum Sampling for Non-Logconcave Distributions and
Estimating Partition Functions [13.16814860487575]
非対数確率分布からサンプリングする量子アルゴリズムを提案する。
f$ は有限和 $f(x):= frac1Nsum_k=1N f_k(x)$ と書くことができる。
論文 参考訳（メタデータ） (2023-10-17T17:55:32Z) - A hybrid quantum-classical algorithm for multichannel quantum scattering
of atoms and molecules [62.997667081978825]
原子と分子の衝突に対するシュリンガー方程式を解くためのハイブリッド量子古典アルゴリズムを提案する。
このアルゴリズムはコーン変分原理の$S$-matrixバージョンに基づいており、基本散乱$S$-matrixを計算する。
大規模多原子分子の衝突をシミュレートするために,アルゴリズムをどのようにスケールアップするかを示す。
論文 参考訳（メタデータ） (2023-04-12T18:10:47Z) - Quantum Clustering with k-Means: a Hybrid Approach [117.4705494502186]
我々は3つのハイブリッド量子k-Meansアルゴリズムを設計、実装、評価する。
我々は距離の計算を高速化するために量子現象を利用する。
我々は、我々のハイブリッド量子k-平均アルゴリズムが古典的バージョンよりも効率的であることを示す。
論文 参考訳（メタデータ） (2022-12-13T16:04:16Z) - A single $T$-gate makes distribution learning hard [56.045224655472865]
この研究は、局所量子回路の出力分布の学習可能性に関する広範な評価を提供する。
ハイブリッド量子古典アルゴリズムを含む多種多様な学習アルゴリズムにおいて、深度$d=omega(log(n))$ Clifford回路に関連する生成的モデリング問題さえも困難であることを示す。
論文 参考訳（メタデータ） (2022-07-07T08:04:15Z) - Faster quantum mixing of Markov chains in non-regular graph with fewer
qubits [0.0]
量子の場合、マルコフ連鎖からのqsamplingは、定常分布の平方根に任意に近い振幅を持つ量子状態の準備として構成することができる。
本稿では,すべての可逆マルコフ連鎖に対する新しいqsamplingアルゴリズムを離散時間量子ウォークを用いて構築する。
非正規グラフでは、量子高速フォワードアルゴリズムの起動は、離散時間と連続時間の両方で既存の最先端のqsamplingアルゴリズムを加速させる。
論文 参考訳（メタデータ） (2022-05-12T14:08:08Z) - Quantum-enhanced Markov chain Monte Carlo [0.22166578153935784]
いくつかのアプリケーションにおいてボトルネックとなる分布のサンプリングに量子アルゴリズムを導入する。
それぞれのステップで、量子プロセッサは重ね合わせのモデルを探索し、ランダムな動きを提案し、古典的なコンピュータで受け入れられるか拒否される。
この量子アルゴリズムは、関連する問題インスタンス上の典型的なMCMC代替よりも少ないイテレーションで収束する。
論文 参考訳（メタデータ） (2022-03-23T15:50:12Z) - Quantum algorithms for quantum dynamics: A performance study on the
spin-boson model [68.8204255655161]
量子力学シミュレーションのための量子アルゴリズムは、伝統的に時間進化作用素のトロッター近似の実装に基づいている。
変分量子アルゴリズムは欠かせない代替手段となり、現在のハードウェア上での小規模なシミュレーションを可能にしている。
量子ゲートコストが明らかに削減されているにもかかわらず、現在の実装における変分法は量子的優位性をもたらすことはありそうにない。
論文 参考訳（メタデータ） (2021-08-09T18:00:05Z) - An Algebraic Quantum Circuit Compression Algorithm for Hamiltonian
Simulation [55.41644538483948]
現在の世代のノイズの多い中間スケール量子コンピュータ(NISQ)は、チップサイズとエラー率に大きく制限されている。
我々は、自由フェルミオンとして知られる特定のスピンハミルトニアンをシミュレーションするために、量子回路を効率よく圧縮するために局所化回路変換を導出する。
提案した数値回路圧縮アルゴリズムは、後方安定に動作し、$mathcalO(103)$スピンを超える回路合成を可能にするスピンの数で3次スケールする。
論文 参考訳（メタデータ） (2021-08-06T19:38:03Z) - Quantum computing for classical problems: Variational Quantum
Eigensolver for activated processes [0.0]
本稿では,Fokker-Planck-Smoluchowski固有値問題を解くための変分量子固有解法の開発と実装について報告する。
量子化学問題に対処するために一般的に採用されるそのようなアルゴリズムは、量子コンピュータの新しい応用への道を開く古典的なシステムに効果的に適用可能であることを示す。
論文 参考訳（メタデータ） (2021-07-27T18:16:16Z) - Preserving quantum correlations and coherence with non-Markovianity [50.591267188664666]
量子系における相関とコヒーレンスを保存するための非マルコビアン性の有用性を示す。
共変量子ビットの進化に対して、非マルコビアン性は、常に量子コヒーレンスを保存するために使用できることを示す。
論文 参考訳（メタデータ） (2021-06-25T11:52:51Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。