論文の概要: Elfs, trees and quantum walks

• arxiv url: http://arxiv.org/abs/2211.16379v2
• Date: Tue, 18 Feb 2025 18:22:11 GMT
• ステータス: 翻訳完了
• システム内更新日: 2025-02-19 14:01:24.967070
• Title: Elfs, trees and quantum walks
• Title（参考訳）: エルフ、木、量子ウォーク
• Authors: Simon Apers, Stephen Piddock,
• Abstract要約: 電気的流れサンプリング(elfs)に基づくグラフ上のマルコフ過程の研究 木上の電気的打撃時間はグラフサイズと重みの対数的であることを示す。 これにより、ランダムなウォーク到着分布からサンプリングする量子ウォークアルゴリズムが得られる。
• 参考スコア（独自算出の注目度）: 1.104960878651584
• License:
• Abstract: We study an elementary Markov process on graphs based on electric flow sampling (elfs). The elfs process repeatedly samples from an electric flow on a graph. While the sinks of the flow are fixed, the source is updated using the electric flow sample, and the process ends when it hits a sink vertex. We argue that this process naturally connects to many key quantities of interest. E.g., we describe a random walk coupling which implies that the elfs process has the same arrival distribution as a random walk. We also analyze the electric hitting time, which is the expected time before the process hits a sink vertex. As our main technical contribution, we show that the electric hitting time on trees is logarithmic in the graph size and weights. The initial motivation behind the elfs process is that quantum walks can sample from electric flows, and they can hence implement this process very naturally. This yields a quantum walk algorithm for sampling from the random walk arrival distribution, which has widespread applications. It complements the existing line of quantum walk search algorithms which only return an element from the sink, but yield no insight in the distribution of the returned element. By our bound on the electric hitting time on trees, the quantum walk algorithm on trees requires quadratically fewer steps than the random walk hitting time, up to polylog factors.
• Abstract（参考訳）: 電子フローサンプリング(elfs)に基づくグラフ上でのマルコフ過程について検討する。 エルフプロセスは、グラフ上の電気の流れから繰り返しサンプリングされる。 フローのシンクは固定されているが、ソースは電気フローサンプルを使用して更新され、シンク頂点にぶつかるとプロセスは終了する。 このプロセスは自然に多くの重要な関心事に結びついていると我々は主張する。 例えば、エルフ過程がランダムウォークと同じ到着分布を持つことを示すランダムウォーク結合を記述する。 我々はまた、このプロセスがシンク頂点に達する前に予想される電気的打撃時間も分析する。 我々の主要な技術的貢献として、木上の電気的打撃時間はグラフのサイズと重みの対数であることを示す。 エルフ過程の背後にある最初の動機は、量子ウォークが電気の流れからサンプルを採取できるため、この過程を非常に自然に実装できるということである。 これにより、ランダムなウォーク到着分布からサンプリングする量子ウォークアルゴリズムが得られ、広く応用されている。 これは既存の量子ウォーク探索アルゴリズムのラインを補完し、シンクから要素だけを返すが、返される要素の分布についての洞察は得られない。 木上の電気的打撃時間に縛られることで、木上の量子ウォークアルゴリズムは、ランダムなウォーク時間よりも2次的に少ないステップをポリログ因子まで必要とします。

関連論文リスト

• Global Phase Helps in Quantum Search: Yet Another Look at the Welded Tree Problem [55.80819771134007]
  本稿では、離散時間量子ウォークによる溶接木問題に対する最適線形打撃時間の簡単な証明を行う。 同じ手法は他の1次元階層グラフにも適用できる。
  論文  参考訳（メタデータ） (2024-04-30T11:45:49Z)
• Quantum walks, the discrete wave equation and Chebyshev polynomials [1.0878040851638]
  量子ウォーク(quantum walk)は、ランダムウォークの量子アナログである。 量子ウォークは、グラフ上のランダムウォークの拡散または混合速度を高速化できることを示す。
  論文  参考訳（メタデータ） (2024-02-12T17:15:19Z)
• Quantum walks advantage on the dihedral group for uniform sampling problem [0.0]
  本稿では、ケイリーグラフ上での量子ウォーク混合の一般的な理解を前進させる。 これは、D_2n$で連続時間量子ウォークによって達成された改良された混合時間を強調する。 この研究は、非アーベル群に基づくサンプリング問題のクラスに対するアルゴリズムに潜在的な応用をもたらす。
  論文  参考訳（メタデータ） (2023-12-25T11:21:55Z)
• On sampling determinantal and Pfaffian point processes on a quantum computer [49.1574468325115]
  DPPは1970年代の量子光学のモデルとしてマッキによって導入された。 ほとんどのアプリケーションはDPPからのサンプリングを必要としており、その量子起源を考えると、古典的なコンピュータでDPPをサンプリングするのは古典的なものよりも簡単かどうか疑問に思うのが自然である。 バニラサンプリングは、各コスト$mathcalO(N3)$と$mathcalO(Nr2)$の2つのステップから構成される。
  論文  参考訳（メタデータ） (2023-05-25T08:43:11Z)
• How to Sample From The Limiting Distribution of a Continuous-Time Quantum Walk [1.8021287677546958]
  我々は、連続時間量子ウォークの制限分布からサンプリングできる$varepsilon$-projectorsを紹介した。 グラフの隣接行列へのクエリアクセスしかできないブラックボックス設定では、サンプリングアルゴリズムはDelta-1$に比例して実行されます。 非ブラックボックス設定では,アルゴリズムが標準サンプリングアルゴリズムよりも指数関数的に高速に動作するグラフの例を示す。
  論文  参考訳（メタデータ） (2022-09-26T21:04:49Z)
• Quadratic speedup for spatial search by continuous-time quantum walk [0.0]
  連続時間量子ウォークは、空間探索として知られるグラフ内のマークされたノードの集合の中のノードを見つけるという根本的な問題に取り組むためのフレームワークを提供する。 連続時間量子ウォーク探索アルゴリズムでは,任意のノード数を持つグラフにおいて,従来のランダムウォークよりも2次的に高速なマークノードを見つけることができる。
  論文  参考訳（メタデータ） (2021-12-23T17:57:49Z)
• Algebraic Compression of Quantum Circuits for Hamiltonian Evolution [52.77024349608834]
  時間依存ハミルトニアンの下でのユニタリ進化は、量子ハードウェアにおけるシミュレーションの重要な構成要素である。 本稿では、トロッターステップを1ブロックの量子ゲートに圧縮するアルゴリズムを提案する。 この結果、ハミルトニアンのある種のクラスに対する固定深度時間進化がもたらされる。
  論文  参考訳（メタデータ） (2021-08-06T19:38:01Z)
• On the realistic worst case analysis of quantum arithmetic circuits [69.43216268165402]
  量子回路の設計における直観は誤解を招く可能性があることを示す。 また,T数を減らすことで,全深度を増大させることができることを示した。 リップルキャリーを用いた加算回路と乗算回路について述べる。
  論文  参考訳（メタデータ） (2021-01-12T21:36:16Z)
• Quantum walk processes in quantum devices [55.41644538483948]
  グラフ上の量子ウォークを量子回路として表現する方法を研究する。 提案手法は,量子ウォークアルゴリズムを量子コンピュータ上で効率的に実装する方法である。
  論文  参考訳（メタデータ） (2020-12-28T18:04:16Z)
• Random Walks: A Review of Algorithms and Applications [37.226218097358284]
  コンピュータ科学において、古典的なランダムウォークと量子ウォークはノード間の近接を計算し、ネットワーク内のトポロジーを抽出するために用いられる。 様々なランダムウォーク関連モデルは、リンク予測、レコメンデーション、コンピュータビジョン、半教師付き学習、ネットワーク埋め込みといった下流タスクに非常に重要である。
  論文  参考訳（メタデータ） (2020-08-09T03:41:56Z)
• Continuous-time quantum walks in the presence of a quadratic perturbation [55.41644538483948]
  連続時間量子ウォークの特性を、$mathcalH=L + lambda L2$という形のハミルトン群で解決する。 低/高接続性および/または対称性を持つパラダイムモデルであるため、サイクル、完全、およびスターグラフを考える。
  論文  参考訳（メタデータ） (2020-05-13T14:53:36Z)

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

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