論文の概要: Quasi-optimal quantum Markov chain spectral gap estimation

• arxiv url: http://arxiv.org/abs/2601.07601v1
• Date: Mon, 12 Jan 2026 14:50:46 GMT
• ステータス: 翻訳完了
• システム内更新日: 2026-01-13 19:08:01.466456
• Title: Quasi-optimal quantum Markov chain spectral gap estimation
• Title（参考訳）: 準最適量子マルコフ連鎖スペクトルギャップ推定
• Authors: Adam Connolly, Steven Herbert, Julien Sorci,
• Abstract要約: 本稿では,マルコフ連鎖スペクトルギャップ推定のための量子アルゴリズムを提案する。 マルコフ連鎖のスペクトルギャップを知ることはマルコフ連鎖モンテカルロにおけるスピードアップサンプリングを可能にする。
• 参考スコア（独自算出の注目度）: 0.0
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: This paper proposes a quantum algorithm for Markov chain spectral gap estimation that is quasi-optimal (i.e., optimal up to a polylogarithmic factor) in the number of vertices for all parameters, and additionally quasi-optimal in the reciprocal of the spectral gap itself, if the permitted relative error is above some critical value. In particular, these results constitute an almost quadratic advantage over the best-possible classical algorithm. Our algorithm also improves on the quantum state of the art, and we contend that this is not just theoretically interesting but also potentially practically impactful in real-world applications: knowing a Markov chain's spectral gap can speed-up sampling in Markov chain Monte Carlo. Our approach uses the quantum singular value transformation, and as a result we also develop some theory around block-encoding Markov chain transition matrices, which is potentially of independent interest. In particular, we introduce explicit block-encoding methods for the transition matrices of two algebraically-defined classes of Markov chains.
• Abstract（参考訳）: 本稿では,マルコフ連鎖のスペクトルギャップ推定のための量子アルゴリズムを提案する。これは全てのパラメータの頂点数において準最適(すなわち,ポリ対数係数まで最適)であり,また,許容相対誤差がいくつかの臨界値を超える場合,スペクトルギャップ自体の相互に準最適である。 特に、これらの結果は、最も有望な古典的アルゴリズムに対するほぼ2次的な優位性を構成する。 我々のアルゴリズムは、量子技術の状態を改善し、これは理論上は興味深いだけでなく、現実の応用に潜在的に影響を及ぼす可能性がある、と我々は主張する。 我々のアプローチは量子特異値変換を用いており、その結果、ブロック符号化マルコフ連鎖遷移行列に関するいくつかの理論も発展し、これは独立な関心を持つ可能性がある。 特に、マルコフ連鎖の代数的に定義された2つのクラスの遷移行列に対する明示的なブロックエンコーディング手法を導入する。

関連論文リスト

• Quantum Approximate Optimization Algorithm for MIMO with Quantized b-bit Beamforming [47.98440449939344]
  多重入力多重出力(MIMO)は6G通信において重要であり、スペクトル効率と信頼性の向上を提供する。 本稿では、送信機と受信機の両方でbビット量子化位相シフト器の問題に対処するために、量子近似最適化アルゴリズム(QAOA)と交互最適化を適用することを検討する。 この量子化ビームフォーミング問題の構造はQAOAのようなハイブリッド古典的手法と自然に一致し、ビームフォーミングで使われる位相シフトは量子回路の回転ゲートに直接マッピングできる。
  論文  参考訳（メタデータ） (2025-10-07T17:53:02Z)
• Quantum Markov chain Monte Carlo with programmable quantum simulators [0.0]
  many-Body Localized phase を用いて量子状態の分布からエルゴード性やサンプリングの条件に対処する方法を示す。 このアルゴリズムは近傍の相互作用を持つ1次元イジング鎖のフロケダイナミクスをシミュレートできる任意の量子ハードウェア上で実装することができる。
  論文  参考訳（メタデータ） (2025-05-27T14:37:35Z)
• QAMA: Scalable Quantum Annealing Multi-Head Attention Operator for Deep Learning [48.12231190677108]
  QAMA(Quantum Annealing Multi-Head Attention)は、エネルギーベースのハミルトン最適化問題として注目を集める新しいドロップイン演算子である。 この枠組みでは、トークン相互作用を二項二項項に符号化し、低エネルギー構成の探索に量子アニールを用いる。 経験的に、自然言語と視覚のベンチマークによる評価は、タスク全体にわたって、標準的なマルチヘッドの注意から少なくとも2.7ポイントの精度が低下していることを示している。
  論文  参考訳（メタデータ） (2025-04-15T11:29:09Z)
• Quantum Speedup for Nonreversible Markov Chains [0.0]
  マルコフ連鎖の問題は量子コンピューティングによってかなり高速に解けることが議論されている。 本研究では,非可逆過程を高速化する量子アルゴリズム技術を開発した。 このような先進的な量子スピードアップは、多くのアプリケーションに決定的な影響を与える可能性がある。
  論文  参考訳（メタデータ） (2025-01-10T11:09:40Z)
• Quantum enhanced Markov chains require fine-tuned quenches [0.0]
  不完全な量子デバイス上でのロバストな量子スピードアップの方法として、量子強化型マルコフ連鎖モンテカルロが提案されている。 アルゴリズムの性能を制限する競合要因を同定する。 具体的には、長期の極限において、マルコフ連鎖のギャップは、固有状態基底における古典状態の逆参加比によって制限されることを示す。
  論文  参考訳（メタデータ） (2024-08-15T01:40:07Z)
• Quantum Speedups in Regret Analysis of Infinite Horizon Average-Reward Markov Decision Processes [32.07657827173262]
  我々は,未知のMDPとエージェントのエンゲージメントのための革新的な量子フレームワークを提案する。 平均推定における量子的優位性は、無限の地平線強化学習に対する後悔の保証において指数的な進歩をもたらすことを示す。
  論文  参考訳（メタデータ） (2023-10-18T03:17:51Z)
• A quantum advantage over classical for local max cut [48.02822142773719]
  量子最適化近似アルゴリズム(QAOA)は、次数3グラフ上の古典的手法に匹敵する計算上の優位性を持つ。 結果として、最先端の量子ハードウェアに関係している小規模量子計算でさえ、比較可能な単純な古典よりも大きな優位性を持つ可能性が示唆された。
  論文  参考訳（メタデータ） (2023-04-17T16:42:05Z)
• Quantum vs classical Markov chains; Exactly solvable examples [0.0]
  グラフ上の一般可逆マルコフ連鎖のコインレス量子化手順を示す。 量子ハミルトン H は、基本遷移確率行列 K の類似性変換によって得られる。
  論文  参考訳（メタデータ） (2022-12-21T01:24:23Z)

関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。

指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。