論文の概要: Faster quantum mixing of Markov chains in non-regular graph with fewer qubits

• arxiv url: http://arxiv.org/abs/2205.06099v1
• Date: Thu, 12 May 2022 14:08:08 GMT
• ステータス: 処理完了
• システム内更新日: 2023-02-13 09:39:08.059321
• Title: Faster quantum mixing of Markov chains in non-regular graph with fewer qubits
• Title（参考訳）: 量子ビットの少ない非正則グラフにおけるマルコフ鎖の高速量子混合
• Authors: Xinyin Li, Yun Shang
• Abstract要約: 量子の場合、マルコフ連鎖からのqsamplingは、定常分布の平方根に任意に近い振幅を持つ量子状態の準備として構成することができる。 本稿では,すべての可逆マルコフ連鎖に対する新しいqsamplingアルゴリズムを離散時間量子ウォークを用いて構築する。 非正規グラフでは、量子高速フォワードアルゴリズムの起動は、離散時間と連続時間の両方で既存の最先端のqsamplingアルゴリズムを加速させる。
• 参考スコア（独自算出の注目度）: 0.0
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: Sampling from the stationary distribution is one of the fundamental tasks of Markov chain-based algorithms and has important applications in machine learning, combinatorial optimization and network science. For the quantum case, qsampling from Markov chains can be constructed as preparing quantum states with amplitudes arbitrarily close to the square root of a stationary distribution instead of classical sampling from a stationary distribution. In this paper, a new qsampling algorithm for all reversible Markov chains is constructed by discrete-time quantum walks and works without any limit compared with existing results. In detail, we build a qsampling algorithm that not only accelerates non-regular graphs but also keeps the speed-up of existing quantum algorithms for regular graphs. In non-regular graphs, the invocation of the quantum fast-forward algorithm accelerates existing state-of-the-art qsampling algorithms for both discrete-time and continuous-time cases, especially on sparse graphs. Compared to existing algorithms we reduce log n, where n is the number of graph vertices. In regular graphs, our result matches other quantum algorithms, and our reliance on the gap of Markov chains achieves quadratic speedup compared with classical cases. For both cases, we reduce the number of ancilla qubits required compared to the existing results. In some widely used graphs and a series of sparse graphs where stationary distributions are difficult to reach quickly, our algorithm is the first algorithm to achieve complete quadratic acceleration (without log factor) over the classical case without any limit. To enlarge success probability amplitude amplification is introduced. We construct a new reflection on stationary state with fewer ancilla qubits and think it may have independent application.
• Abstract（参考訳）: 定常分布からのサンプリングはマルコフ連鎖に基づくアルゴリズムの基本課題の1つであり、機械学習、組合せ最適化、ネットワーク科学において重要な応用がある。 量子の場合、マルコフ連鎖からのqサンプリングは、定常分布からの古典的なサンプリングではなく、定常分布の平方根に任意に近い振幅を持つ量子状態を作成するために構成できる。 本稿では,すべての可逆マルコフ連鎖に対する新しいqsamplingアルゴリズムを離散時間量子ウォークによって構築し,既存の結果と比較して制限なく動作させる。 具体的には、非正則グラフを高速化するだけでなく、既存の正則グラフの量子アルゴリズムを高速化するqsamplingアルゴリズムを構築する。 非正規グラフでは、量子高速フォワードアルゴリズムの起動は、特にスパースグラフ上の離散時間と連続時間の両方で既存の最先端のqsamplingアルゴリズムを加速させる。 既存のアルゴリズムと比較して、n はグラフ頂点の数である log n を減らす。 正規グラフでは、我々の結果は他の量子アルゴリズムと一致し、マルコフ連鎖のギャップへの依存は古典的な場合と比較して二次的なスピードアップを達成する。 どちらのケースでも、既存の結果と比較して必要となるアンシラキュービットの数を減らす。 いくつかの広く使われているグラフや、定常分布の到達が困難であるスパースグラフにおいて、我々のアルゴリズムは、制限なく古典的なケースに対して(ログ係数なしで)完全な二次加速度を達成する最初のアルゴリズムである。 成功確率振幅増幅を増大させる。 静止状態に新たな反射を生じさせるため,アンシラ量子ビットが少なく,独立した応用が考えられる。

関連論文リスト

• Comparison among Classical, Probabilistic and Quantum Algorithms for Hamiltonian Cycle problem [0.0]
  ハミルトニアンサイクル問題(HCP)は、n 個のノードと m 個のエッジを持つグラフ G を持ち、各ノードを正確に1度に接続する経路を見つけることである。 本稿では、計算の異なるモデル、特に確率的および量子的モデルを用いて、aHCPを解くアルゴリズムを比較する。
  論文  参考訳（メタデータ） (2023-11-18T02:36:10Z)
• 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)
• Quantum Clustering with k-Means: a Hybrid Approach [117.4705494502186]
  我々は3つのハイブリッド量子k-Meansアルゴリズムを設計、実装、評価する。 我々は距離の計算を高速化するために量子現象を利用する。 我々は、我々のハイブリッド量子k-平均アルゴリズムが古典的バージョンよりも効率的であることを示す。
  論文  参考訳（メタデータ） (2022-12-13T16:04:16Z)
• Quantum Worst-Case to Average-Case Reductions for All Linear Problems [66.65497337069792]
  量子アルゴリズムにおける最悪のケースと平均ケースの削減を設計する問題について検討する。 量子アルゴリズムの明示的で効率的な変換は、入力のごく一部でのみ正し、全ての入力で正しくなる。
  論文  参考訳（メタデータ） (2022-12-06T22:01:49Z)
• Entanglement and coherence in Bernstein-Vazirani algorithm [58.720142291102135]
  Bernstein-Vaziraniアルゴリズムは、オラクルに符号化されたビット文字列を決定できる。 我々はベルンシュタイン・ヴァジラニアルゴリズムの量子資源を詳細に分析する。 絡み合いがない場合、初期状態における量子コヒーレンス量とアルゴリズムの性能が直接関係していることが示される。
  論文  参考訳（メタデータ） (2022-05-26T20:32:36Z)
• Quadratic speedup for spatial search by continuous-time quantum walk [0.0]
  連続時間量子ウォークは、空間探索として知られるグラフ内のマークされたノードの集合の中のノードを見つけるという根本的な問題に取り組むためのフレームワークを提供する。 連続時間量子ウォーク探索アルゴリズムでは,任意のノード数を持つグラフにおいて,従来のランダムウォークよりも2次的に高速なマークノードを見つけることができる。
  論文  参考訳（メタデータ） (2021-12-23T17:57:49Z)
• Correlation Clustering in Constant Many Parallel Rounds [42.10280805559555]
  相関クラスタリングは教師なし学習において中心的なトピックであり、MLやデータマイニングに多くの応用がある。 本研究では,従来よりもかなり高速な超並列計算(MPC)アルゴリズムを提案する。 我々のアルゴリズムは,ノード数にメモリサブリニアを持つマシンを使用し,一定回数のラウンドでのみ実行しながら,一定の近似を返す。
  論文  参考訳（メタデータ） (2021-06-15T21:45:45Z)
• Quantum algorithm for Feynman loop integrals [0.0]
  量子アルゴリズムのFeynmanループ積分への新しいベンチマーク適用を提案する。 ファインマンプロパゲーターの2つのオンシェル状態は、キュービットの2つの状態と同一視される。 量子アルゴリズムは、マルチループファインマン図形の因果特異構成を展開するために用いられる。
  論文  参考訳（メタデータ） (2021-05-18T17:41:56Z)
• Quantum algorithms for learning a hidden graph and beyond [0.05076419064097732]
  本稿では、量子アルゴリズムを用いて、託宣によって提供された未知のグラフを学習する問題について研究する。 ORおよびパリティクエリモデルにおいて、最も優れた古典的アルゴリズムの高速化を実現する量子アルゴリズムを提供する。 さらに、グループテスト問題の"ガッペ"バージョンに対して、Ambainisらのアルゴリズムに基づいて、この問題に対する時間効率の量子アルゴリズムを与える。
  論文  参考訳（メタデータ） (2020-11-17T13:12:43Z)
• Single-Timescale Stochastic Nonconvex-Concave Optimization for Smooth Nonlinear TD Learning [145.54544979467872]
  本稿では,各ステップごとに1つのデータポイントしか必要としない2つの単一スケールシングルループアルゴリズムを提案する。 本研究の結果は, 同時一次および二重側収束の形で表される。
  論文  参考訳（メタデータ） (2020-08-23T20:36:49Z)
• 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)

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

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