論文の概要: Hardness of Pathfinding in a Welded Tree

• arxiv url: http://arxiv.org/abs/2609.20651v1
• Date: Thu, 17 Sep 2026 16:29:09 GMT
• ステータス: 翻訳完了
• システム内更新日: 2026-09-20 08:55:54.37418
• Title: Hardness of Pathfinding in a Welded Tree
• Title（参考訳）: 溶接木におけるパスフィニングの硬さ
• Abstract要約: 我々は、出口から出口までの経路を見つけるために指数的量子クエリを低い境界で証明する。 我々の証明では,アルゴリズムが学習し忘れたグラフ情報を追跡するデータベースを構築するために,圧縮置換オラクル法を用いている。
• 参考スコア（独自算出の注目度）: 0.2864713389096699
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: Starting from the entrance of a welded tree, a quantum walk algorithm can find its exit vertex exponentially faster than any classical algorithm. However, it has been an open question whether any quantum algorithm is able to efficiently find a path from the entrance to the exit. We answer this by proving an exponential quantum query lower bound for finding such path. Specifically, for trees of height $n$, any quantum query algorithm requires at least $Ω(2^{n/24})$ queries in order to succeed with constant probability. Our proof uses the compressed permutation oracle technique in order to construct databases which track the graph information an algorithm has learned and forgotten, and show that no efficient quantum algorithm can build an entrance-to-exit path in these records.
• Abstract（参考訳）: 溶接木の入り口から始まる量子ウォークアルゴリズムは、どの古典的アルゴリズムよりも指数関数的に早く出口頂点を見つけることができる。 しかし、どの量子アルゴリズムでも出口から出口への経路を効率的に見つけることができるかどうかという未解決の問題があった。 このような経路を見つけるために指数的量子クエリを低い境界で証明することで、この問題に答える。 具体的には、高さ$n$のツリーに対して、任意の量子クエリアルゴリズムは、一定の確率で成功するためには少なくとも$Ω(2^{n/24})$クエリを必要とする。 我々の証明では,アルゴリズムが学習し,忘れたグラフ情報を追跡するデータベースを構築するために,圧縮置換オラクル法を用いており,これらのレコードに効率的な量子アルゴリズムが入出力経路を構築することができないことを示す。

関連論文リスト

• Quantum algorithms for Hopcroft's problem [45.45456673484445]
  計算幾何学の基本的な問題であるホップクロフト問題に対する量子アルゴリズムについて検討する。 この問題の古典的な複雑さはよく研究されており、最もよく知られているアルゴリズムは$O(n4/3)の時間で動作する。 我々の結果は、時間複雑性が$widetilde O(n5/6)$の2つの異なる量子アルゴリズムである。
  論文  参考訳（メタデータ） (2024-05-02T10:29:06Z)
• Generalized quantum Arimoto-Blahut algorithm and its application to quantum information bottleneck [55.22418739014892]
  量子アリーモト・ブラフトアルゴリズムをRamakrishnanらにより一般化する。 3つの量子系を持つ量子情報ボトルネックに対して,我々のアルゴリズムを適用した。 数値解析により,我々のアルゴリズムはアルゴリズムよりも優れていることが示された。
  論文  参考訳（メタデータ） (2023-11-19T00:06:11Z)
• Exponential speedup of quantum algorithms for the pathfinding problem [5.260626311429307]
  溶接木に基づいてグラフ$G$を構築し、隣接リスト oracle $O$ でパスフィニング問題を定義する。 古典的なアルゴリズムが確率の高い指数時間で$x$-$y$パスを見つけることはできないことを証明している。 我々の発見は、量子アルゴリズムがパスフィニング問題を解決するために、より多くの種類のグラフに利点をもたらす可能性があることを示唆している。
  論文  参考訳（メタデータ） (2023-07-24T02:50:34Z)
• Recovering the original simplicity: succinct and deterministic quantum algorithm for the welded tree problem [0.0]
  この研究は、よく知られた溶接木問題に対する量子アルゴリズムを再考する。 最も単純な量子ウォークに基づく非常に簡潔な量子アルゴリズムを提案する。
  論文  参考訳（メタデータ） (2023-04-17T16:03:50Z)
• Quantum algorithms and the power of forgetting [1.5791732557395555]
  本研究では,効率の良い量子アルゴリズムの自然なクラスは,ENTRANCEからEXITへの経路を確実に見つけることができないことを示す。 このことは、効率的に経路を見つける量子アルゴリズムの可能性を排除するものではないが、アルゴリズムがこの振る舞いからどのような恩恵を受けるかは定かではない。
  論文  参考訳（メタデータ） (2022-11-22T18:04:10Z)
• Entanglement and coherence in Bernstein-Vazirani algorithm [58.720142291102135]
  Bernstein-Vaziraniアルゴリズムは、オラクルに符号化されたビット文字列を決定できる。 我々はベルンシュタイン・ヴァジラニアルゴリズムの量子資源を詳細に分析する。 絡み合いがない場合、初期状態における量子コヒーレンス量とアルゴリズムの性能が直接関係していることが示される。
  論文  参考訳（メタデータ） (2022-05-26T20:32:36Z)
• Robust Quantum Walk Search Without Knowing the Number of Marked Vertices [0.2320417845168326]
  既存の量子ウォークに基づく探索アルゴリズムは、サッフル問題に悩まされている。 量子スピードアップを犠牲にすることなくロバスト性を実現する新しい量子ウォークベースの探索フレームワークを提案する。
  論文  参考訳（メタデータ） (2021-11-17T10:04: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)
• Synthesis of Quantum Circuits with an Island Genetic Algorithm [44.99833362998488]
  特定の演算を行うユニタリ行列が与えられた場合、等価な量子回路を得るのは非自明な作業である。 量子ウォーカーのコイン、トフォリゲート、フレドキンゲートの3つの問題が研究されている。 提案したアルゴリズムは量子回路の分解に効率的であることが証明され、汎用的なアプローチとして、利用可能な計算力によってのみ制限される。
  論文  参考訳（メタデータ） (2021-06-06T13:15:25Z)

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

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