Fugu-MT 論文翻訳(概要): No Infinite Tail Beats Optimal Spatial Search

論文の概要: No Infinite Tail Beats Optimal Spatial Search

arxiv url: http://arxiv.org/abs/2301.07251v2
Date: Fri, 20 Jan 2023 14:18:41 GMT
ステータス: 処理完了
システム内更新日: 2023-01-23 14:34:52.349307
Title: No Infinite Tail Beats Optimal Spatial Search
Title（参考訳）: Infinite Tailは最適な空間探索に勝てない
Authors: Weichen Xie and Christino Tamon
Abstract要約: 無限に長い経路(または尾)が存在する場合でも、空間探索は完全なグラフで最適であることを示す。検索アルゴリズムは、尾部が存在するかどうか、それに付随しているかどうかを知る必要がなくなる。
参考スコア（独自算出の注目度）: 0.0
License: http://creativecommons.org/licenses/by/4.0/
Abstract: Farhi and Gutmann (Physical Review A, 57(4):2403, 1998) proved that a continuous-time analogue of Grover search (also called spatial search) is optimal on the complete graphs. We extend this result by showing that spatial search remains optimal in a complete graph even in the presence of an infinitely long path (or tail). If we view the latter as an external quantum system that has a limited but nontrivial interaction with our finite quantum system, this suggests that spatial search is robust against a coherent infinite one-dimensional probe. Moreover, we show that the search algorithm is oblivious in that it does not need to know whether the tail is present or not, and if so, where it is attached to.
Abstract（参考訳）: Farhi and Gutmann (Physical Review A, 57(4):2403, 1998) は、グロバー探索(空間探索とも呼ばれる)の連続時間アナログが全グラフ上で最適であることを証明した。この結果は、無限に長い経路(または尾)が存在する場合でも、完全グラフにおいて空間探索が最適であることを示して拡張する。後者を有限量子系との限定的かつ非自明な相互作用を持つ外部量子系と考えると、空間探索はコヒーレントな無限一次元プローブに対して頑健であることが示唆される。さらに, 探索アルゴリズムは, 尾部が存在するか否かを知る必要がなく, かつ, 尾部がどこに取り付けられているかを知ることが困難であることを示す。

関連論文リスト

Constant search time algorithm via topological quantum walks [0.0]
本研究では,探索確率を極端に改善した探索時間量子アルゴリズムの実現が可能であることを示す。具体的には,2次元分割型量子ランダムウォークによって実現された空間探索アルゴリズムについて検討する。
論文参考訳（メタデータ） (2024-06-26T21:36:47Z)
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)
k-Means Maximum Entropy Exploration [55.81894038654918]
余分な報酬を伴う連続空間での探索は、強化学習におけるオープンな問題である。本研究では, 状態訪問分布のエントロピーに対する近似値の低界化に基づく人工好奇性アルゴリズムを提案する。提案手法は,高次元連続空間における探索のためのベンチマークにおいて,計算効率と競合性の両方を示す。
論文参考訳（メタデータ） (2022-05-31T09:05:58Z)
Of Shadows and Gaps in Spatial Search [0.0]
我々は、ハミンググラフやグラスマングラフのような距離正則グラフの族が最適空間探索を持つことを示す。また、一定の忠実度を持つ空間探索の時間的下界も示し、これは完全忠実度に対するFarhiとGutmannによる境界を延長する。
論文参考訳（メタデータ） (2022-04-09T02:02:53Z)
Exploring Complicated Search Spaces with Interleaving-Free Sampling [127.07551427957362]
本稿では,長距離接続を伴う複雑な検索空間上に探索アルゴリズムを構築する。我々はtextbfIF-NAS という単純なアルゴリズムを提案し、異なるサブネットワークを構築するために周期的なサンプリング戦略を実行する。提案した探索空間において、IF-NASはランダムサンプリングと従来の重み付け検索のアルゴリズムを有意差で上回っている。
論文参考訳（メタデータ） (2021-12-05T06:42:48Z)
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)
BR-NS: an Archive-less Approach to Novelty Search [70.13948372218849]
行動認識に基づく新規性探索(BR-NS)という,新規性推定の代替手法について議論する。 BR-NSはアーカイブを必要とせず、行動空間で定義できるメトリクスを前提にせず、近隣の検索に依存しません。我々は、その実現可能性とダイナミクス、および時間複雑性の観点からアーカイブベースのnsよりも潜在的に有利な点について洞察を得るために実験を行う。
論文参考訳（メタデータ） (2021-04-08T17:31:34Z)
Deterministic spatial search using alternating quantum walks [0.0]
最適な量子ウォーク時間と頂点位相シフトの組に対して、構造化空間探索のための決定論的アルゴリズムが確立されていることを証明した。これにより、同じグラフのクラスにおける元の空間探索アルゴリズムを改善し、50%の確率しか増幅できないことを示す。この新たなフレームワークは、グラフ構造の他のファミリーに対する決定論的空間探索に容易に拡張できると期待されている。
論文参考訳（メタデータ） (2021-04-08T14:32:48Z)
Sub-linear Regret Bounds for Bayesian Optimisation in Unknown Search Spaces [63.22864716473051]
本稿では,反復により探索空間を拡大(およびシフト)する新しいBOアルゴリズムを提案する。理論的には、どちらのアルゴリズムにおいても、累積的後悔は線形以下の速度で増大する。
論文参考訳（メタデータ） (2020-09-05T14:24:40Z)
On the optimality of spatial search by continuous-time quantum walk [0.0]
我々は、この量子探索アルゴリズムの性能を予測するハミルトン運動のスペクトル特性に依存する一般表現を導出する。例えば、スペクトルギャップが$n-1/2$よりもかなり大きいハミルトニアンの予測は有効である。
論文参考訳（メタデータ） (2020-04-27T10:05:55Z)

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