論文の概要: A framework for optimal quantum spatial search using alternating phase-walks

• arxiv url: http://arxiv.org/abs/2109.14351v1
• Date: Wed, 29 Sep 2021 11:16:52 GMT
• ステータス: 処理完了
• システム内更新日: 2023-03-13 05:08:40.259195
• Title: A framework for optimal quantum spatial search using alternating phase-walks
• Title（参考訳）: 交互位相歩行を用いた最適量子空間探索の枠組み
• Authors: S. Marsh, J. B. Wang
• Abstract要約: 我々は、マーク頂点位相シフトと連続時間量子ウォークの交互適用により、Childs & Goldstone(mathcalCG$)アルゴリズムを一般化する。 様々なグラフ上の$mathcalO(sqrtN)$検索にアルゴリズムを適用することで,アルゴリズムの有効性を実証する。
• 参考スコア（独自算出の注目度）: 0.0
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: We present a novel methodological framework for quantum spatial search, generalising the Childs & Goldstone ($\mathcal{CG}$) algorithm via alternating applications of marked-vertex phase shifts and continuous-time quantum walks. We determine closed form expressions for the optimal walk time and phase shift parameters for periodic graphs. These parameters are chosen to rotate the system about subsets of the graph Laplacian eigenstates, amplifying the probability of measuring the marked vertex. The state evolution is asymptotically optimal for any class of periodic graphs having a fixed number of unique eigenvalues. We demonstrate the effectiveness of the algorithm by applying it to obtain $\mathcal{O}(\sqrt{N})$ search on a variety of graphs. One important class is the $n \times n^3$ rook graph, which has $N=n^4$ vertices. On this class of graphs the $\mathcal{CG}$ algorithm performs suboptimally, achieving only $\mathcal{O}(N^{-1/8})$ overlap after time $\mathcal{O}(N^{5/8})$. Using the new alternating phase-walk framework, we show that $\mathcal{O}(1)$ overlap is obtained in $\mathcal{O}(\sqrt{N})$ phase-walk iterations.
• Abstract（参考訳）: 本稿では,マーク頂点位相シフトと連続時間量子ウォークの交互適用によるChilds & Goldstone(\mathcal{CG}$)アルゴリズムを一般化した新しい量子空間探索手法を提案する。 閉形式式を最適歩行時間と周期グラフの位相シフトパラメータで決定する。 これらのパラメータはグラフラプラシアン固有状態の部分集合に関する系を回転させ、マークされた頂点を測定する確率を増幅する。 状態進化は一定数の固有値を持つ任意の周期グラフのクラスに対して漸近的に最適である。 本稿では,種々のグラフに対して$\mathcal{o}(\sqrt{n})$ 探索を行うことで,アルゴリズムの有効性を示す。 1つの重要なクラスは$n \times n^3$ rook graphであり、これは$N=n^4$ verticesを持つ。 このグラフのクラスでは、$\mathcal{CG}$アルゴリズムが亜最適に実行し、$\mathcal{O}(N^{-1/8})$オーバーラップの後に$\mathcal{O}(N^{5/8})$のみを達成する。 新しい交互位相歩行フレームワークを用いて、$\mathcal{o}(1)$ overlap が$\mathcal{o}(\sqrt{n})$ phase-walk 反復で得られることを示す。

関連論文リスト

• Implementation of Continuous-Time Quantum Walk on Sparse Graph [0.0]
  連続時間量子ウォーク(CTQW)は、量子コンピューティングにおいて重要な役割を果たす。 CTQWを効率的に実装する方法は難しい問題である。 本稿では,スパースグラフ上でのCTQWの実装について検討する。
  論文  参考訳（メタデータ） (2024-08-20T05:20:55Z)
• Graph Unfolding and Sampling for Transitory Video Summarization via Gershgorin Disc Alignment [48.137527345353625]
  携帯電話からYouTubeやTikTokなどのソーシャルメディアサイトにアップロードされたユーザー生成ビデオ(UGV)は、短くて繰り返しではない。 我々は、ガーシュゴリンディスクアライメント(GDA)に基づく高速グラフサンプリングにより、遷移UGVを複数のディスクに線形時間で要約する。 提案アルゴリズムは,最先端の手法と比較して,映像の要約性能が向上し,複雑さが大幅に低減されていることを示す。
  論文  参考訳（メタデータ） (2024-08-03T20:08:02Z)
• An Oblivious Stochastic Composite Optimization Algorithm for Eigenvalue Optimization Problems [76.2042837251496]
  相補的な合成条件に基づく2つの難解なミラー降下アルゴリズムを導入する。 注目すべきは、どちらのアルゴリズムも、目的関数のリプシッツ定数や滑らかさに関する事前の知識なしで機能する。 本稿では,大規模半確定プログラム上での手法の効率性とロバスト性を示す。
  論文  参考訳（メタデータ） (2023-06-30T08:34:29Z)
• Fast Online Node Labeling for Very Large Graphs [11.700626862639131]
  現在のメソッドは、$mathcalO(n3)$または$mathcalO(n2)$スペースの複雑さでグラフカーネルランタイムマトリックスを反転させるか、ランダムなスパンニングツリーを大量にサンプリングする。 本稿では,一連の研究によって導入されたテクスチトリン緩和技術に基づく改善を提案する。
  論文  参考訳（メタデータ） (2023-05-25T17:13:08Z)
• Convergence of a Normal Map-based Prox-SGD Method under the KL Inequality [0.0]
  我々は、$symbol$k$収束問題に対して、新しいマップベースのアルゴリズム(mathsfnorMtext-mathsfSGD$)を提案する。
  論文  参考訳（メタデータ） (2023-05-10T01:12:11Z)
• Efficient Signed Graph Sampling via Balancing & Gershgorin Disc Perfect Alignment [51.74913666829224]
  強い反相関を持つデータセットに対して、適切なグラフは正および負のエッジ重みの両方を含むことを示す。 本稿では,平衡符号グラフの概念に着目した線形時間符号グラフサンプリング手法を提案する。 実験結果から, 署名付きグラフサンプリング手法は, 各種データセットにおいて, 既存の高速サンプリング方式よりも優れた性能を示した。
  論文  参考訳（メタデータ） (2022-08-18T09:19:01Z)
• Learning a Single Neuron with Adversarial Label Noise via Gradient Descent [50.659479930171585]
  モノトン活性化に対する $mathbfxmapstosigma(mathbfwcdotmathbfx)$ の関数について検討する。 学習者の目標は仮説ベクトル $mathbfw$ that $F(mathbbw)=C, epsilon$ を高い確率で出力することである。
  論文  参考訳（メタデータ） (2022-06-17T17:55:43Z)
• Multimarked Spatial Search by Continuous-Time Quantum Walk [0.0]
  任意のグラフ上の連続時間量子ウォークによる空間探索の計算複雑性を決定するためのフレームワークについて述べる。 量子ウォークは、マークされた頂点の存在によって修正されたグラフの隣接行列に由来するハミルトン行列によって駆動される。
  論文  参考訳（メタデータ） (2022-03-27T20:22:17Z)
• Fast Graph Sampling for Short Video Summarization using Gershgorin Disc Alignment [52.577757919003844]
  高速グラフサンプリングの最近の進歩を利用して,短い動画を複数の段落に効率よく要約する問題について検討する。 実験結果から,本アルゴリズムは最先端の手法と同等の映像要約を実現し,複雑さを大幅に低減した。
  論文  参考訳（メタデータ） (2021-10-21T18:43:00Z)
• Random Graph Matching with Improved Noise Robustness [2.294014185517203]
  本稿では確率モデルに基づくグラフマッチングの新しいアルゴリズムを提案する。 我々のアルゴリズムは、$alpha le 1 / (log log n)C$ のとき、その基礎となるマッチングを高い確率で復元する。 これにより、以前の作業で達成された条件 $alpha le 1 / (log n)C$ が改善される。
  論文  参考訳（メタデータ） (2021-01-28T02:39:27Z)
• Complexity of Finding Stationary Points of Nonsmooth Nonconvex Functions [84.49087114959872]
  非滑らかで非滑らかな関数の定常点を見つけるための最初の非漸近解析を提供する。 特に、アダマール半微分可能函数(おそらく非滑らか関数の最大のクラス)について研究する。
  論文  参考訳（メタデータ） (2020-02-10T23:23:04Z)

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

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