論文の概要: A quantum searching model finding one of the edges of a subgraph in a complete graph

• arxiv url: http://arxiv.org/abs/2202.01464v2
• Date: Sun, 5 Jun 2022 03:35:41 GMT
• ステータス: 処理完了
• システム内更新日: 2023-02-26 23:05:35.796926
• Title: A quantum searching model finding one of the edges of a subgraph in a complete graph
• Title（参考訳）: 完全グラフにおける部分グラフのエッジの1つを見つける量子探索モデル
• Authors: Yusuke Yoshie and Kiyoto Yoshino
• Abstract要約: 我々は,与えられた部分グラフのエッジの1つを完全グラフで探索する量子探索モデルを構築した。 モデルが任意の部分グラフ、すなわち完備グラフに対して有効であることを示す。
• 参考スコア（独自算出の注目度）: 0.0
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: Some of the quantum searching models have been given by perturbed quantum walks. Driving some perturbed quantum walks, we may quickly find one of the targets with high probability. In this paper, we construct a quantum searching model finding one of the edges of a given subgraph in a complete graph. How to construct our model is that we label the arcs by $+1$ or $-1$, and define a perturbed quantum walk by the sign function on the set of arcs. After that, we detect one of the edges labeled $-1$ by the induced sign function as fast as possible. This idea was firstly proposed by Segawa et al. in 2021. They only addressed the case where the subgraph forms a matching, and obtained by a combinatorial argument that the time of finding one of the edges of the subgraph is quadratically faster than a classical searching model. In this paper, we show that the model is valid for any subgraph, i.e., we obtain by spectral analysis a quadratic speed-up for finding one of the edges of the subgraph in a complete graph.
• Abstract（参考訳）: 量子探索モデルのいくつかは摂動量子ウォークによって与えられる。 摂動量子ウォークを運転すると、高い確率でターゲットの1つがすぐに見つかるかもしれない。 本稿では,与えられた部分グラフのエッジの1つを完全グラフで探索する量子探索モデルを構築する。 私たちのモデルを構築するには、弧を+1$または1$でラベル付けし、弧の集合上の符号関数による摂動量子ウォークを定義する必要があります。 その後、誘導符号関数によって1$のラベルが付けられたエッジの1つをできるだけ早く検出する。 この考えは2021年に瀬川らによって初めて提案された。 それらは部分グラフがマッチングを形成する場合のみに対処し、部分グラフの辺の1つを見つける時間は古典的な探索モデルよりも2倍速いという組合せ論によって得られる。 本稿では,このモデルが任意の部分グラフに対して有効であることを示す。つまり,スペクトル解析により,部分グラフのエッジの1つを完全グラフで検索する2次高速化を求める。

関連論文リスト

• Quantum Walk Search on Complete Multipartite Graph with Multiple Marked Vertices [7.922488341886121]
  本稿では,完全多部グラフ上での量子ウォーク探索アルゴリズムについて検討する。 我々は、量子ウォークモデルを用いて、二次的なスピードアップを実現する。 また、量子アルゴリズムの数値シミュレーションと回路実装も提供する。
  論文  参考訳（メタデータ） (2024-10-07T11:13:41Z)
• Unifying quantum spatial search, state transfer and uniform sampling on graphs: simple and exact [2.871419116565751]
  本稿では,量子ウォークの交互化による新しい,簡潔なアルゴリズムフレームワークを提案する。 量子空間探索、状態移動、および大規模なグラフの均一サンプリングを統一する。 このアプローチは、グラフのラプラシア固有値集合の深さにのみ依存する簡潔な形式性を持っているため、簡単に利用できる。
  論文  参考訳（メタデータ） (2024-07-01T06:09:19Z)
• Global Phase Helps in Quantum Search: Yet Another Look at the Welded Tree Problem [55.80819771134007]
  本稿では、離散時間量子ウォークによる溶接木問題に対する最適線形打撃時間の簡単な証明を行う。 同じ手法は他の1次元階層グラフにも適用できる。
  論文  参考訳（メタデータ） (2024-04-30T11:45:49Z)
• Universal approach to deterministic spatial search via alternating quantum walks [2.940962519388297]
  本稿では,量子ウォークを交互に組み合わせることで,様々なグラフ上で決定論的量子探索アルゴリズムを設計するための新しいアプローチを提案する。 我々のアプローチは、異なるグラフに対してインスタンス固有の分析を必要としないため、普遍的である。
  論文  参考訳（メタデータ） (2023-07-30T05:14:19Z)
• Quantitative approach to Grover's quantum walk on graphs [62.997667081978825]
  グラフ上の連続時間量子ウォークに着目したGroverの探索アルゴリズムについて検討する。 関連する量子ウォークに便利なグラフトポロジーを見つける代わりに、グラフトポロジーを修正し、ラプラシアンを基礎とするグラフを変化させる。
  論文  参考訳（メタデータ） (2022-07-04T19:33:06Z)
• On Applying the Lackadaisical Quantum Walk Algorithm to Search for Multiple Solutions on Grids [63.75363908696257]
  不足量子ウォーク(英: lackadaisical quantum walk)は、頂点が重量$l$の自己ループを持つグラフ構造を探索するために開発されたアルゴリズムである。 本稿では,グリッド上の複数解の探索に不連続な量子ウォークを適用した際の問題に対処する。
  論文  参考訳（メタデータ） (2021-06-11T09:43:09Z)
• Fast and Accurate Anomaly Detection in Dynamic Graphs with a Two-Pronged Approach [49.25767340466445]
  動的グラフにおける異常検出のためのオンラインアルゴリズムAnomRankを提案する。 AnomRank氏は、異常を示す2つの新しいメトリクスを定義する2段階のアプローチを使用している。 理論的,実験的に,この2つのアプローチが共通の2種類の異常の検出に成功していることを示す。
  論文  参考訳（メタデータ） (2020-11-26T01:38:27Z)
• Quantum search of matching on signed graphs [0.0]
  我々は,量子ウォークによって駆動される符号付きエッジの量子探索モデルを構築した。 完全グラフ上のマッチングを与える任意のエッジカラー化の下で、完全グラフのエッジ集合から有色エッジの量子探索を考える。
  論文  参考訳（メタデータ） (2020-07-13T09:36:08Z)
• Online Dense Subgraph Discovery via Blurred-Graph Feedback [87.9850024070244]
  我々は高密度サブグラフ発見のための新しい学習問題を導入する。 まず,確率の高いほぼ最適解を求めるエッジ時間アルゴリズムを提案する。 そして、理論的保証のあるよりスケーラブルなアルゴリズムを設計する。
  論文  参考訳（メタデータ） (2020-06-24T11:37:33Z)
• Continuous-time quantum walks in the presence of a quadratic perturbation [55.41644538483948]
  連続時間量子ウォークの特性を、$mathcalH=L + lambda L2$という形のハミルトン群で解決する。 低/高接続性および/または対称性を持つパラダイムモデルであるため、サイクル、完全、およびスターグラフを考える。
  論文  参考訳（メタデータ） (2020-05-13T14:53:36Z)
• Search on Vertex-Transitive Graphs by Lackadaisical Quantum Walk [0.0]
  量子ウォーク(quantum walk)は、グラフ上の離散時間(離散時間)の量子ウォークである。 完全グラフ、離散トーラス、サイクル、正規完全二部グラフの空間探索を改善することができる。 この仮説を支持する数値シミュレーションをいくつか提示する。
  論文  参考訳（メタデータ） (2020-02-26T00:10:38Z)

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

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