論文の概要: Algorithmic Wave-Particle Duality: Pathfinding in Welded Trees is Hard

• arxiv url: http://arxiv.org/abs/2611.05912v1
• Date: Wed, 04 Nov 2026 04:02:14 GMT
• ステータス: 翻訳完了
• システム内更新日: 2026-11-06 03:25:57.937793
• Title: Algorithmic Wave-Particle Duality: Pathfinding in Welded Trees is Hard
• Title（参考訳）: アルゴリズムによる波動粒子二重性:溶接木におけるパスフィニングは困難である
• Abstract要約: 量子ウォークは、どの古典的アルゴリズムよりも指数関数的に速くルートからルートへ移動することができる。 高さ$n$のツリーの場合、一定確率のルート間の経路を見つけるという量子クエリの複雑さは$tilde(2n/3)$であることを証明する。
• 参考スコア（独自算出の注目度）: 1.4675095722281564
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: In the welded trees problem, an algorithm navigates a randomly labeled graph formed from two binary trees joined at their leaves through a "weld" of connecting edges. A quantum walk can navigate from root to root exponentially faster than any classical algorithm. However, recording its path destroys the constructive interference responsible for the speedup, leaving open whether some quantum algorithm can efficiently find a path between the roots. We prove that, for trees of height $n$, the quantum query complexity of finding a path between the roots with constant probability is $\tildeΘ(2^{n/3})$. This establishes an algorithmic wave-particle duality, adapting the double-slit experiment to the high-complexity regime: interference between many paths lets a quantum algorithm reach the exit efficiently, but finding a single path (the algorithmic analog of the route of a particle) requires exponentially many queries. Furthermore, the bound is tight, matching the cost of a quantum algorithm that finds collisions between paths from each root to the weld. Our proof uses the compressed permutation oracle to track the information about the graph that an algorithm retains and forgets. We show that the compressed database remains close to a space of states that do not record a path between the roots by bounding the error introduced by each compressed oracle query.
• Abstract（参考訳）: 溶接木問題において、アルゴリズムは2つの二分木が葉に結合したランダムなラベル付きグラフを連結エッジの「12」を介してナビゲートする。 量子ウォークは、どの古典的アルゴリズムよりも指数関数的に速くルートからルートへ移動することができる。 しかし、その経路を記録すると、スピードアップの原因となる建設的干渉が破壊され、ある量子アルゴリズムがルート間の経路を効率的に見つけることができるかどうかが明らかになる。 高さが$n$のツリーの場合、一定確率のルート間の経路を見つけるという量子クエリの複雑さは$\tilde*(2^{n/3})$であることを証明する。 多くの経路間の干渉は量子アルゴリズムを効率的に出口に到達させるが、単一経路(粒子の経路のアルゴリズム的類似)を見つけるには指数関数的に多くのクエリを必要とする。 さらに、境界は厳密であり、各ルートから溶接部への経路間の衝突を見つける量子アルゴリズムのコストと一致する。 我々の証明では、圧縮された置換オラクルを用いて、アルゴリズムが保持し忘れているグラフに関する情報を追跡する。 圧縮されたデータベースは、各圧縮されたオラクルクエリによって導入されたエラーをバウンドすることで、ルート間の経路を記録しない状態の空間に近づいたままであることを示す。

関連論文リスト

• A quantum lower bound for path finding in welded trees [1.43494686131174]
  量子ウォークは、どの古典的アルゴリズムよりも指数関数的に速くルートからルートへ移動することができる。 我々は任意の量子アルゴリズムが根間の経路を見つけるために指数関数的に多くのクエリを必要とすることを証明した。 圧縮されたデータベースは小誤差までパスフリーのままであることを示す。
  論文  参考訳（メタデータ） (2026-09-22T17:03:38Z)
• Hardness of Pathfinding in a Welded Tree [0.2864713389096699]
  我々は、出口から出口までの経路を見つけるために指数的量子クエリを低い境界で証明する。 我々の証明では,アルゴリズムが学習し忘れたグラフ情報を追跡するデータベースを構築するために,圧縮置換オラクル法を用いている。
  論文  参考訳（メタデータ） (2026-09-17T16:29:09Z)
• 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)
• 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)
• Synthesis of Quantum Circuits with an Island Genetic Algorithm [44.99833362998488]
  特定の演算を行うユニタリ行列が与えられた場合、等価な量子回路を得るのは非自明な作業である。 量子ウォーカーのコイン、トフォリゲート、フレドキンゲートの3つの問題が研究されている。 提案したアルゴリズムは量子回路の分解に効率的であることが証明され、汎用的なアプローチとして、利用可能な計算力によってのみ制限される。
  論文  参考訳（メタデータ） (2021-06-06T13:15:25Z)
• Lagrangian Decomposition for Neural Network Verification [148.0448557991349]
  ニューラルネットワーク検証の基本的なコンポーネントは、出力が取ることのできる値のバウンダリの計算である。 ラグランジアン分解に基づく新しい手法を提案する。 ランニングタイムのごく一部で、既成の解法に匹敵するバウンダリが得られることを示す。
  論文  参考訳（メタデータ） (2020-02-24T17:55:10Z)

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

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