論文の概要: Quantum Search Approaches to Sampling-Based Motion Planning
- arxiv url: http://arxiv.org/abs/2304.06479v2
- Date: Fri, 7 Jul 2023 21:01:23 GMT
- ステータス: 処理完了
- システム内更新日: 2023-07-11 22:06:31.062045
- Title: Quantum Search Approaches to Sampling-Based Motion Planning
- Title（参考訳）: サンプリングに基づく動き計画のための量子探索手法
- Authors: Paul Lathrop, Beth Boardman, Sonia Mart\'inez
- Abstract要約: 本稿では,従来のサンプリング型モーションプランナを,量子探索アルゴリズムを用いて解くことのできるデータベース・オーラル構造として,新しい定式化を提案する。
より単純なスパース環境では、量子完全経路探索アルゴリズム (Quantum Full Path Search Algorithm, Q-FPS) を定式化し、完全なランダムパス解の重ね合わせを生成する。
密集した非構造環境において、親子接続の量子重ね合わせを生成する量子高速探索ランダムツリーアルゴリズム q-RRT を定式化する。
- 参考スコア（独自算出の注目度）: 0.0
- License: http://creativecommons.org/licenses/by/4.0/
- Abstract: In this paper, we present a novel formulation of traditional sampling-based
motion planners as database-oracle structures that can be solved via quantum
search algorithms. We consider two complementary scenarios: for simpler sparse
environments, we formulate the Quantum Full Path Search Algorithm (q-FPS),
which creates a superposition of full random path solutions, manipulates
probability amplitudes with Quantum Amplitude Amplification (QAA), and quantum
measures a single obstacle free full path solution. For dense unstructured
environments, we formulate the Quantum Rapidly Exploring Random Tree algorithm,
q-RRT, that creates quantum superpositions of possible parent-child
connections, manipulates probability amplitudes with QAA, and quantum measures
a single reachable state, which is added to a tree. As performance depends on
the number of oracle calls and the probability of measuring good quantum
states, we quantify how these errors factor into the probabilistic completeness
properties of the algorithm. We then numerically estimate the expected number
of database solutions to provide an approximation of the optimal number of
oracle calls in the algorithm. We compare the q-RRT algorithm with a classical
implementation and verify quadratic run-time speedup in the largest connected
component of a 2D dense random lattice. We conclude by evaluating a proposed
approach to limit the expected number of database solutions and thus limit the
optimal number of oracle calls to a given number.
- Abstract（参考訳）: 本稿では,従来のサンプリングベースモーションプランナーを,量子探索アルゴリズムを用いて解くデータベース・オラクル構造として,新しい定式化手法を提案する。
単純なスパース環境の場合、完全ランダムパス解の重ね合わせを作成し、量子振幅増幅 (qaa) で確率振幅を操作する量子全経路探索アルゴリズム (q-fps) を定式化し、単一障害自由全経路解を量子的に測定する。
密集した非構造環境に対しては,親子接続の量子重ね合わせを生成し,qaaで確率振幅を演算し,単一の到達可能な状態を木に追加する量子アルゴリズム q-rrt を高速に探索するランダムツリーアルゴリズムを定式化する。
性能はオラクル呼び出しの数と良い量子状態を測定する確率に依存するため、これらの誤差がアルゴリズムの確率論的完全性にどう影響するかを定量化する。
次に,提案アルゴリズムにおける最適なオラクル呼び出し数を近似するために,期待するデータベース解の数を数値的に推定する。
q-rrtアルゴリズムを古典的実装と比較し、2次元密閉乱数格子の最大連結成分における二次実行速度の検証を行う。
最後に、提案手法を評価してデータベースソリューションの期待数を制限することにより、oracle呼び出しの最適な数を所定の数に制限する。
関連論文リスト
- An Analysis of Quantum Annealing Algorithms for Solving the Maximum Clique Problem [49.1574468325115]
我々は、QUBO問題として表されるグラフ上の最大傾きを見つける量子D波アンナーの能力を解析する。
本稿では, 相補的な最大独立集合問題に対する分解アルゴリズムと, ノード数, 傾き数, 密度, 接続率, 解サイズの他のノード数に対する比を制御するグラフ生成アルゴリズムを提案する。
論文 参考訳（メタデータ） (2024-06-11T04:40:05Z) - Quantum Subroutine for Variance Estimation: Algorithmic Design and Applications [80.04533958880862]
量子コンピューティングは、アルゴリズムを設計する新しい方法の基礎となる。
どの場の量子スピードアップが達成できるかという新たな課題が生じる。
量子サブルーチンの設計は、従来のサブルーチンよりも効率的で、新しい強力な量子アルゴリズムに固い柱を向ける。
論文 参考訳（メタデータ） (2024-02-26T09:32:07Z) - 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 Semidefinite Programming with Thermal Pure Quantum States [0.5639904484784125]
行列乗法重み付けアルゴリズムの量子化'''は、古典的アルゴリズムよりも2次的に高速なSDPの近似解が得られることを示す。
この量子アルゴリズムを改良し、ギブス状態サンプリング器を熱純量子(TPQ)状態に置き換えることで、同様のスピードアップが得られることを示す。
論文 参考訳（メタデータ） (2023-10-11T18:00:53Z) - Quantum-Based Feature Selection for Multi-classification Problem in
Complex Systems with Edge Computing [15.894122816099133]
マルチクラス化問題,すなわちQReliefFに対する量子ベースの特徴選択アルゴリズムを提案する。
我々のアルゴリズムは、O(M) から O(sqrt(M)) への複雑さを減らし、最も近い隣人を見つけるのに優れている。
論文 参考訳（メタデータ） (2023-10-01T03:57:13Z) - Optimization of probabilistic quantum search algorithm with a priori
information [0.21756081703276003]
グロバーの量子探索アルゴリズムは古典計算よりも量子コンピューティングの優位性を証明する典型的な量子アルゴリズムである。
本稿では,一般の確率分布を持つデータベースの故障確率をゼロにできる確率論的グロバー探索アルゴリズムについて考察する。
論文 参考訳（メタデータ） (2023-04-06T04:33:37Z) - Quantum Clustering with k-Means: a Hybrid Approach [117.4705494502186]
我々は3つのハイブリッド量子k-Meansアルゴリズムを設計、実装、評価する。
我々は距離の計算を高速化するために量子現象を利用する。
我々は、我々のハイブリッド量子k-平均アルゴリズムが古典的バージョンよりも効率的であることを示す。
論文 参考訳（メタデータ） (2022-12-13T16:04:16Z) - End-to-end resource analysis for quantum interior point methods and portfolio optimization [63.4863637315163]
問題入力から問題出力までの完全な量子回路レベルのアルゴリズム記述を提供する。
アルゴリズムの実行に必要な論理量子ビットの数と非クリフォードTゲートの量/深さを報告する。
論文 参考訳（メタデータ） (2022-11-22T18:54:48Z) - Quantum Speedup for Higher-Order Unconstrained Binary Optimization and
MIMO Maximum Likelihood Detection [2.5272389610447856]
実数値の高次非制約二項最適化問題をサポートする量子アルゴリズムを提案する。
提案アルゴリズムは,古典的領域におけるクエリの複雑さを低減し,量子領域における2次高速化を実現する。
論文 参考訳（メタデータ） (2022-05-31T00:14:49Z) - Entanglement and coherence in Bernstein-Vazirani algorithm [58.720142291102135]
Bernstein-Vaziraniアルゴリズムは、オラクルに符号化されたビット文字列を決定できる。
我々はベルンシュタイン・ヴァジラニアルゴリズムの量子資源を詳細に分析する。
絡み合いがない場合、初期状態における量子コヒーレンス量とアルゴリズムの性能が直接関係していることが示される。
論文 参考訳（メタデータ） (2022-05-26T20:32:36Z) - Q-Match: Iterative Shape Matching via Quantum Annealing [64.74942589569596]
形状対応を見つけることは、NP-hard quadratic assignment problem (QAP)として定式化できる。
本稿では,アルファ拡大アルゴリズムに触発されたQAPの反復量子法Q-Matchを提案する。
Q-Match は、実世界の問題にスケールできるような長文対応のサブセットにおいて、反復的に形状マッチング問題に適用できる。
論文 参考訳（メタデータ） (2021-05-06T17:59:38Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。