論文の概要: A quantum lower bound for path finding in welded trees

• arxiv url: http://arxiv.org/abs/2609.26712v1
• Date: Tue, 22 Sep 2026 17:03:38 GMT
• ステータス: 翻訳完了
• システム内更新日: 2026-09-24 01:05:39.763949
• Title: A quantum lower bound for path finding in welded trees
• Title（参考訳）: 溶接木における経路探索のための量子下界
• Abstract要約: 量子ウォークは、どの古典的アルゴリズムよりも指数関数的に速くルートからルートへ移動することができる。 我々は任意の量子アルゴリズムが根間の経路を見つけるために指数関数的に多くのクエリを必要とすることを証明した。 圧縮されたデータベースは小誤差までパスフリーのままであることを示す。
• 参考スコア（独自算出の注目度）: 1.43494686131174
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: In the welded tree problem, an algorithm is tasked with navigating a graph formed from two binary trees joined at the leaves through a ``weld'' of connecting edges. A quantum walk can navigate from root to root exponentially faster than any classical algorithm. However, known efficient quantum algorithms cannot find a path between the roots, as recording the path destroys constructive interference and thus the speedup. We prove that this is inherent: any quantum algorithm needs exponentially many queries to find a path between the roots of an independently matched welded tree graph. This provides an example of a problem that a quantum computer can solve exponentially faster than any classical algorithm by exploring exponentially many paths in superposition, but where it is provably intractable to find any such path. The proof uses compressed permutation oracles to record the progress of a quantum algorithm as it queries the graph. We show that the compressed database remains path-free up to a small error. By controlling such errors and bounding the progress of the algorithm with each compressed oracle query, we show that $Ω(2^{n/12})$ queries are required to find a path in a height-$n$ tree with constant success probability.
• Abstract（参考訳）: 溶接木問題では、葉に結合された2本の二分木からなるグラフを、エッジを接続する ``weld'' を介してナビゲートするアルゴリズムが課される。 量子ウォークは、どの古典的アルゴリズムよりも指数関数的に速くルートからルートへ移動することができる。 しかし、既知の効率的な量子アルゴリズムはルート間の経路を見つけることができない。 任意の量子アルゴリズムは、独立に一致した溶接木グラフのルート間の経路を見つけるために指数関数的に多くのクエリを必要とする。 これは、量子コンピュータが任意の古典的アルゴリズムよりも指数関数的に高速に解けるという問題の例として、重ね合わせにおいて指数関数的に多くの経路を探索するが、そのような経路を見つけることは確実に難解である。 この証明は、圧縮された置換オラクルを使用して、グラフをクエリする量子アルゴリズムの進捗を記録する。 圧縮されたデータベースは小誤差までパスフリーのままであることを示す。 このようなエラーを制御し,各オラクルクエリでアルゴリズムの進捗をバウンディングすることにより,$Ω(2^{n/12})$クエリが一定の成功確率を持つ高さ$n$ツリー内の経路を見つけるために必要であることを示す。

関連論文リスト

• Hardness of Pathfinding in a Welded Tree [0.2864713389096699]
  我々は、出口から出口までの経路を見つけるために指数的量子クエリを低い境界で証明する。 我々の証明では,アルゴリズムが学習し忘れたグラフ情報を追跡するデータベースを構築するために,圧縮置換オラクル法を用いている。
  論文  参考訳（メタデータ） (2026-09-17T16:29:09Z)
• Verifiable quantum advantage in extremely low depth [52.51019642214249]
  浅量子回路では解けない問題を格子ベースの仮定で解くのが困難である。 浅量子回路は、解を効率よく検証できる古典的な難題を解くのに十分な構造を持っていることを証明している。
  論文  参考訳（メタデータ） (2026-09-01T15:54:34Z)
• Space-Efficient Quantum Error Reduction without log Factors [50.10645865330582]
  本稿では,多数決のランダムウォーク解釈に類似したライン上の重み付けウォークとして理解可能な,新たに単純化された浄化器の構成を提案する。 我々の浄化器は、前者よりも指数関数的に空間の複雑さが良く、精製されるアルゴリズムの音質-完全性ギャップに四分法的に依存している。
  論文  参考訳（メタデータ） (2025-02-13T12:04:39Z)
• Quantum algorithms for Hopcroft's problem [45.45456673484445]
  計算幾何学の基本的な問題であるホップクロフト問題に対する量子アルゴリズムについて検討する。 この問題の古典的な複雑さはよく研究されており、最もよく知られているアルゴリズムは$O(n4/3)の時間で動作する。 我々の結果は、時間複雑性が$widetilde O(n5/6)$の2つの異なる量子アルゴリズムである。
  論文  参考訳（メタデータ） (2024-05-02T10:29:06Z)
• Global Phase Helps in Quantum Search: Yet Another Look at the Welded Tree Problem [55.80819771134007]
  本稿では、離散時間量子ウォークによる溶接木問題に対する最適線形打撃時間の簡単な証明を行う。 同じ手法は他の1次元階層グラフにも適用できる。
  論文  参考訳（メタデータ） (2024-04-30T11:45:49Z)
• Exponential speedup of quantum algorithms for the pathfinding problem [5.260626311429307]
  溶接木に基づいてグラフ$G$を構築し、隣接リスト oracle $O$ でパスフィニング問題を定義する。 古典的なアルゴリズムが確率の高い指数時間で$x$-$y$パスを見つけることはできないことを証明している。 我々の発見は、量子アルゴリズムがパスフィニング問題を解決するために、より多くの種類のグラフに利点をもたらす可能性があることを示唆している。
  論文  参考訳（メタデータ） (2023-07-24T02:50:34Z)
• Quantum algorithms and the power of forgetting [1.5791732557395555]
  本研究では,効率の良い量子アルゴリズムの自然なクラスは,ENTRANCEからEXITへの経路を確実に見つけることができないことを示す。 このことは、効率的に経路を見つける量子アルゴリズムの可能性を排除するものではないが、アルゴリズムがこの振る舞いからどのような恩恵を受けるかは定かではない。
  論文  参考訳（メタデータ） (2022-11-22T18:04:10Z)
• Complexity-Theoretic Limitations on Quantum Algorithms for Topological Data Analysis [59.545114016224254]
  トポロジカルデータ解析のための量子アルゴリズムは、古典的手法よりも指数関数的に有利である。 我々は、量子コンピュータにおいても、TDA(ベッチ数の推定)の中心的なタスクが難解であることを示します。 我々は、入力データが単純さの仕様として与えられると、指数的量子優位性を取り戻すことができると論じる。
  論文  参考訳（メタデータ） (2022-09-28T17:53:25Z)
• 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)

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

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