論文の概要: Optimality conditions for spatial search with multiple marked vertices
- arxiv url: http://arxiv.org/abs/2201.12937v3
- Date: Thu, 5 Jan 2023 08:22:34 GMT
- ステータス: 処理完了
- システム内更新日: 2023-02-27 07:10:36.461746
- Title: Optimality conditions for spatial search with multiple marked vertices
- Title（参考訳）: 複数頂点をもつ空間探索のための最適条件
- Authors: Mathieu Roget, Hachem Kadri and Giuseppe Di Molfetta
- Abstract要約: マルチイテムQWSearchアルゴリズムの最適条件について述べる。
古典的対数に対する計算上の優位性は必ずしも確実ではないことを数値的に示す。
- 参考スコア（独自算出の注目度）: 5.28539620288341
- License: http://creativecommons.org/licenses/by/4.0/
- Abstract: We contribute to fulfil the long-lasting gap in the understanding of the
spatial search with multiple marked vertices. The theoretical framework is that
of discrete-time quantum walks (QW), \textit{i.e.} local unitary matrices that
drive the evolution of a single particle on the lattice. QW based search
algorithms are well understood when they have to tackle the fundamental problem
of finding only one marked element in a $d-$dimensional grid and it has been
proven they provide a quadratic advantage over classical searching protocols.
However, once we consider to search more than one element, the behaviour of the
algorithm may be affected by the spatial configuration of the marked elements
and even the quantum advantage is no longer guaranteed. Here our main
contribution is threefold~: (i)~we provide \textit{sufficient conditions for
optimality} for a multi-items QWSearch algorithm~; (ii)~we provide analytical
evidences that \textit{almost, but not all} spatial configurations with
multiple marked elements are optimal; and (iii)~we numerically show that the
computational advantage with respect to the classical counterpart is not always
certain and it does depend on the proportion of searched elements over the
total number of grid points.
- Abstract（参考訳）: 我々は,複数頂点による空間探索の理解において,長期間のギャップを埋めることに貢献した。
理論的枠組みは、格子上の1つの粒子の進化を駆動する離散時間量子ウォーク(qw) \textit{i.e} 局所ユニタリ行列である。
qwベースの検索アルゴリズムは、$d-$次元グリッド内のマークされた要素を1つだけ見つけるという根本的な問題に取り組む必要があるときによく理解されており、古典的な検索プロトコルに対して二次的な利点があることが証明されている。
しかし、一度1つ以上の要素の探索を考えると、アルゴリズムの挙動はマークされた要素の空間的配置に影響され、量子的優位性ももはや保証されない。
主な貢献は次の3つです。
(i)~多項目QWSearchアルゴリズムに対して,最適性に十分な条件を提供する。
(ii)→複数のマークされた要素を持つ空間配置が最適であることを示す分析的証拠を提供する。
(iii)~古典的対象に対する計算上の優位性は必ずしも確実ではなく、グリッド点の総数に対する探索要素の割合に依存することを数値的に示している。
関連論文リスト
- Variational Quantum Algorithms for the Allocation of Resources in a Cloud/Edge Architecture [1.072460284847973]
変分量子アルゴリズムは, 近い将来, 古典的アルゴリズムの代替となる可能性が示唆された。
特に、2つのアルゴリズム、すなわち量子近似最適化アルゴリズム(QAOA)と変分量子固有解器(VQE)の性能を比較した。
シミュレーション実験は、クラウドと2つのエッジノードを含む %CM230124 の単純な問題に対して実施され、VQE アルゴリズムは、検索空間を制限できる適切な回路テクスタイタンサッチを備えている場合に、より良い性能を保証することを示す。
論文 参考訳（メタデータ） (2024-01-25T17:37:40Z) - Quantum search by continuous-time quantum walk on t-designs [0.0]
本研究は、連続時間量子ウォークを用いて、複数のマークされた要素を持つ$t$-designs上の量子検索アルゴリズムの時間的複雑さについて検討する。
ランダムウォークに基づく探索アルゴリズムと比較して,成功に導かれる二部グラフのサブセットを同定する。
論文 参考訳（メタデータ） (2023-10-22T00:37:52Z) - Sample Complexity for Quadratic Bandits: Hessian Dependent Bounds and
Optimal Algorithms [64.10576998630981]
最適なヘッセン依存型サンプルの複雑さを, 初めて厳密に評価した。
ヘシアン非依存のアルゴリズムは、すべてのヘシアンインスタンスに対して最適なサンプル複雑さを普遍的に達成する。
本アルゴリズムにより得られたサンプルの最適複雑さは,重み付き雑音分布においても有効である。
論文 参考訳（メタデータ） (2023-06-21T17:03:22Z) - HKNAS: Classification of Hyperspectral Imagery Based on Hyper Kernel
Neural Architecture Search [104.45426861115972]
設計したハイパーカーネルを利用して,構造パラメータを直接生成することを提案する。
我々は1次元または3次元の畳み込みを伴う画素レベルの分類と画像レベルの分類を別々に行う3種類のネットワークを得る。
6つの公開データセットに関する一連の実験は、提案手法が最先端の結果を得ることを示した。
論文 参考訳（メタデータ） (2023-04-23T17:27:40Z) - Exploring Complicated Search Spaces with Interleaving-Free Sampling [127.07551427957362]
本稿では,長距離接続を伴う複雑な検索空間上に探索アルゴリズムを構築する。
我々はtextbfIF-NAS という単純なアルゴリズムを提案し、異なるサブネットワークを構築するために周期的なサンプリング戦略を実行する。
提案した探索空間において、IF-NASはランダムサンプリングと従来の重み付け検索のアルゴリズムを有意差で上回っている。
論文 参考訳（メタデータ） (2021-12-05T06:42:48Z) - Sparse Quadratic Optimisation over the Stiefel Manifold with Application
to Permutation Synchronisation [71.27989298860481]
二次目的関数を最大化するスティーフェル多様体上の行列を求める非最適化問題に対処する。
そこで本研究では,支配的固有空間行列を求めるための,単純かつ効果的なスパーシティプロモーティングアルゴリズムを提案する。
論文 参考訳（メタデータ） (2021-09-30T19:17:35Z) - 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) - Deterministic spatial search using alternating quantum walks [0.0]
最適な量子ウォーク時間と頂点位相シフトの組に対して、構造化空間探索のための決定論的アルゴリズムが確立されていることを証明した。
これにより、同じグラフのクラスにおける元の空間探索アルゴリズムを改善し、50%の確率しか増幅できないことを示す。
この新たなフレームワークは、グラフ構造の他のファミリーに対する決定論的空間探索に容易に拡張できると期待されている。
論文 参考訳（メタデータ） (2021-04-08T14:32:48Z) - Quantum walk-based search algorithms with multiple marked vertices [0.0]
量子ウォークは量子アルゴリズムを開発するための強力なツールである。
我々は、Szegedyの量子ウォークに基づく従来の解析手法を拡張した。
2次元格子とハイパーキューブ上の量子ウォークに基づく2つの例は、我々の方法の詳細を示している。
論文 参考訳（メタデータ） (2021-03-23T22:57:07Z) - 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) - On the optimality of spatial search by continuous-time quantum walk [0.0]
我々は、この量子探索アルゴリズムの性能を予測するハミルトン運動のスペクトル特性に依存する一般表現を導出する。
例えば、スペクトルギャップが$n-1/2$よりもかなり大きいハミルトニアンの予測は有効である。
論文 参考訳（メタデータ） (2020-04-27T10:05:55Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。