論文の概要: Lackadaisical quantum walk in the hypercube to search for multiple
marked vertices
- arxiv url: http://arxiv.org/abs/2108.09399v2
- Date: Wed, 15 Dec 2021 15:07:21 GMT
- ステータス: 処理完了
- システム内更新日: 2023-03-17 22:54:15.273408
- Title: Lackadaisical quantum walk in the hypercube to search for multiple
marked vertices
- Title（参考訳）: マルチマーク頂点探索のためのハイパーキューブにおけるラカダシカル量子ウォーク
- Authors: Luciano S. de Souza and Jonathan H. A. de Carvalho and Tiago A. E.
Ferreira
- Abstract要約: 本稿では,自己ループを用いたハイパーキューブにおける量子ウォーキングに関するいくつかの問題を実験的に解決する。
隣人がマークされている場合、成功の確率は1ドル近くになる。
- 参考スコア（独自算出の注目度）: 0.0
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: Adding self-loops at each vertex of a graph improves the performance of
quantum walks algorithms over loopless algorithms. Many works approach quantum
walks to search for a single marked vertex. In this article, we experimentally
address several problems related to quantum walk in the hypercube with
self-loops to search for multiple marked vertices. We first investigate the
quantum walk in the loopless hypercube. We saw that neighbor vertices are also
amplified and that approximately $1/2$ of the system energy is concentrated in
them. We show that the optimal value of $l$ for a single marked vertex is not
optimal for multiple marked vertices. We define a new value of $l = (n/N)\cdot
k$ to search multiple marked vertices. Next, we use this new value of $l$ found
to analyze the search for multiple marked vertices non-adjacent and show that
the probability of success is close to $1$. We also use the new value of $l$
found to analyze the search for several marked vertices that are adjacent and
show that the probability of success is directly proportional to the density of
marked vertices in the neighborhood. We also show that, in the case where
neighbors are marked, if there is at least one non-adjacent marked vertex, the
probability of success increases to close to $1$. The results found show that
the self-loop value for the quantum walk in the hypercube to search for several
marked vertices is $l = (n / N) \cdot k $.
- Abstract（参考訳）: グラフの各頂点に自己ループを追加することで、ループレスアルゴリズムよりも量子ウォークアルゴリズムの性能が向上する。
多くの研究が量子ウォークにアプローチし、1つのマークされた頂点を探す。
本稿では,複数頂点を探索する自己ループを用いたハイパーキューブにおける量子ウォーキングに関するいくつかの問題について実験的に検討する。
まずループレスハイパーキューブにおける量子ウォークについて検討する。
隣の頂点も増幅され、システムエネルギーの約1/2ドルのエネルギーが集中していることがわかった。
1つのマークされた頂点に対して$l$の最適値は、複数のマークされた頂点に対して最適でないことを示す。
複数のマークされた頂点を検索するために、$l = (n/n)\cdot k$ の新しい値を定義する。
次に、この新しい値である$l$を使用して、複数のマークされた頂点を非隣接的に検索し、成功の確率が1ドルに近いことを示す。
また、隣接するいくつかのマークされた頂点の探索を解析し、成功確率が近隣のマークされた頂点の密度に直接比例することを示すために、$l$の新しい値を用いる。
また、隣人がマークされている場合、少なくとも1つの非隣接マークされた頂点がある場合、成功の確率は1ドル近くになることも示しています。
その結果、ハイパーキューブの量子ウォークがいくつかのマークされた頂点を探索する自己ループ値は、$l = (n / N) \cdot k $であることがわかった。
関連論文リスト
- Quantum algorithms for Hopcroft's problem [45.45456673484445]
計算幾何学の基本的な問題であるホップクロフト問題に対する量子アルゴリズムについて検討する。
この問題の古典的な複雑さはよく研究されており、最もよく知られているアルゴリズムは$O(n4/3)の時間で動作する。
我々の結果は、時間複雑性が$widetilde O(n5/6)$の2つの異なる量子アルゴリズムである。
論文 参考訳（メタデータ） (2024-05-02T10:29:06Z) - A Scalable Algorithm for Individually Fair K-means Clustering [77.93955971520549]
Jung et al. と Mahabadi et al が導入した個別フェア (p$, $k$) クラスタリング問題に対するスケーラブルなアルゴリズムを提案する。
クラスタリングは、各$xin P$に対して$delta(x)$ of $x$の範囲内で中心となる場合、個別にフェアと呼ばれる。
我々は,従来よりもアルゴリズムがはるかに高速であるだけでなく,低コストのソリューションを生み出すことを実証的に示す。
論文 参考訳（メタデータ） (2024-02-09T19:01:48Z) - Sketching Algorithms for Sparse Dictionary Learning: PTAS and Turnstile
Streaming [48.18845814885398]
本研究は,スプリス辞書学習とユークリッド語$k$-meansクラスタリング問題に対するスケッチベースアプローチの適用性を高めるための新しい手法を開発した。
高速アルゴリズムでは、$k$-meansクラスタリング問題に対してPTASを設計するための新しいアプローチを得る。
ストリーミングアルゴリズムの分野では、辞書学習と$k$-meansクラスタリングのための新しい上限と下位境界を得る。
論文 参考訳（メタデータ） (2023-10-29T16:46:26Z) - Low-depth Clifford circuits approximately solve MaxCut [44.99833362998488]
低深さクリフォード回路に基づくMaxCutの量子インスピレーション近似アルゴリズムを提案する。
我々のアルゴリズムは、深さ$O(N)$ Clifford回路を構築することにより、$N$頂点グラフ上のMaxCutの近似解を求める。
論文 参考訳（メタデータ） (2023-10-23T15:20:03Z) - Search for Multiple Adjacent Marked Vertices on the Hypercube by a Quantum Walk with Partial Phase Inversion [3.8436076642278754]
量子ウォークは、目標状態の確率振幅を増幅し、1ドルに近い値の確率に達することを示す。
この結果から, ターゲット状態の部分位相逆転は, 量子ウォークを用いた近接解探索の代替となる可能性が示唆された。
論文 参考訳（メタデータ） (2023-05-31T07:30:04Z) - Walking on Vertices and Edges by Continuous-Time Quantum Walk [0.0]
私たちは、歩行者が頂点から端までホップできる連続時間量子ウォークのバージョンを定義します。
両部グラフ上の空間探索アルゴリズムをハミルトン版の修正により解析する。
論文 参考訳（メタデータ） (2022-06-07T15:10:18Z) - Multimarked Spatial Search by Continuous-Time Quantum Walk [0.0]
任意のグラフ上の連続時間量子ウォークによる空間探索の計算複雑性を決定するためのフレームワークについて述べる。
量子ウォークは、マークされた頂点の存在によって修正されたグラフの隣接行列に由来するハミルトン行列によって駆動される。
論文 参考訳（メタデータ） (2022-03-27T20:22:17Z) - Universality of the fully connected vertex in Laplacian continuous-time
quantum walk problems [0.0]
連続時間量子ウォーク(CTQW)がハミルトニアン$H=ガンマ L$で、グラフ$G$に依存しないことを証明する。
本研究では,空間探索と量子輸送に本研究の結果を適用した。
論文 参考訳（メタデータ） (2022-02-28T14:33:44Z) - 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) - Lackadaisical quantum walks on 2D grids with multiple marked vertices [0.0]
ラカダシカル量子ウォーク(英: Lackadaisical quantum walk、LQW)は、古典的な遅延ウォークの量子アナログである。
我々は,LQWによる三角形,長方形,ハニカムの2次元格子の探索について数値解析を行った。
論文 参考訳（メタデータ） (2021-04-20T13:33:16Z) - Streaming Complexity of SVMs [110.63976030971106]
本稿では,ストリーミングモデルにおけるバイアス正規化SVM問題を解く際の空間複雑性について検討する。
両方の問題に対して、$frac1lambdaepsilon$の次元に対して、$frac1lambdaepsilon$よりも空間的に小さいストリーミングアルゴリズムを得ることができることを示す。
論文 参考訳（メタデータ） (2020-07-07T17:10:00Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。