論文の概要: Quantum algorithms for path and cycle containment problems

• arxiv url: http://arxiv.org/abs/2605.09017v1
• Date: Sat, 09 May 2026 15:55:07 GMT
• ステータス: 翻訳完了
• システム内更新日: 2026-05-12 23:28:50.023449
• Title: Quantum algorithms for path and cycle containment problems
• Title（参考訳）: 経路とサイクルの包含問題に対する量子アルゴリズム
• Abstract要約: 本稿では,隣接行列モデルにおけるパスとサイクルを含む問題の変種について考察する。 経路包含問題のいくつかは、線形数のクエリを使って解決でき、他の全ては互いに等価である。 クエリ複雑性を$widetildeO(n3/2-_k)$, $_k in (c-k)$, $c = sqrt3+sqrt17/2 で実現する新しい量子ウォークベースのアルゴリズムを証明した。
• 参考スコア（独自算出の注目度）: 0.22940141855172036
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: The quantum query complexity of subgraph-containment problems, which ask whether a given subgraph $H$ is present in an input graph $G$, has been the subject of considerable study. However, even for relatively simple subgraphs, such as paths and cycles, a complete understanding of their query complexities remains elusive. In this work, we consider several variants of path- and cycle-containment problems in the adjacency matrix model, where we search for paths or cycles of constant length $k$. We compare the settings where the graphs are directed or undirected, where the goal is to detect or find the existence of a path/cycle, and where the path/cycle we are looking for has length exactly $k$, or at most $k$. We also consider several promise versions of these problems, where we suppose that the input graph has a certain structure. We characterize the relative difficulty of these variants of the path/cycle-containment problems, by relating them to one another using randomized reductions, and grouping them into equivalence classes. When we restrict our attention to path-containment problems, we get a dichotomy result. Some of the path-containment problems can be solved using a linear number of queries, and all the others are equivalent to one another (and additionally to several cycle-containment problems) under randomized reductions, up to constant overhead. For the latter equivalence class, we prove a novel quantum-walk-based algorithm that achieves query complexity $\widetilde{O}(n^{3/2-α_k})$, where $α_k \in Θ(c^{-k})$ and $c = \sqrt{3+\sqrt{17}}/2 \approx 1.33$, beating the previous best upper bound $O(n^{3/2})$ on its query complexity. We also provide a conditional lower bound based on the graph-collision problem, which implies that this equivalence class does not admit linear-query quantum algorithms unless graph collision admits an $O(\sqrt{n})$ query algorithm.
• Abstract（参考訳）: 与えられたサブグラフ$H$が入力グラフ$G$に存在するかどうかを問うサブグラフ包含問題の量子クエリ複雑性は、かなりの研究対象となっている。 しかし、パスやサイクルのような比較的単純な部分グラフであっても、それらのクエリの複雑さの完全な理解はいまだに解明されていない。 本研究では,定常長の経路や周期を探索する隣接行列モデルにおいて,経路と周期を含む問題のいくつかの変種について考察する。 グラフが方向付けされているか、方向付けされていないか、パス/サイクルの存在を検知または発見すること、探しているパス/サイクルが正確に$k$か、少なくとも$k$であるような設定を比較します。 また、入力グラフが一定の構造を持つと仮定して、これらの問題のいくつかの有望バージョンも検討する。 経路・サイクル・包含問題におけるこれらの変異の相対的困難さを、ランダム化還元を用いて互いに関連付け、同値類に分類することで特徴づける。 経路内容の問題に注意を向けると、二分法の結果が得られます。 経路包含問題のいくつかは、線形なクエリ数を用いて解決することができ、他の全ては、ランダム化還元の下で、一定オーバーヘッドまで、互いに等価である(さらに、いくつかのサイクル包含問題も含む)。 後者の同値類に対して、クエリ複雑性を$\widetilde{O}(n^{3/2-α_k})$, and $c = \sqrt{3+\sqrt{17}}/2 \approx 1.33$ とする新しい量子ウォークベースのアルゴリズムを証明した。 グラフの衝突が$O(\sqrt{n})$クエリーアルゴリズムを許容しない限り、この同値類は線形暗号量子アルゴリズムを認めない。

関連論文リスト

• Advances in quantum algorithms for the shortest path problem [0.18416014644193066]
  我々は、構造化インスタンスの問題を解くために、隣接リストモデルに2つの有界エラー量子アルゴリズムを与える。 最初のアプローチは、量子フロー状態をサンプリングし、より小さな問題に対して古典的なアルゴリズムを実行することによって、元のグラフをスパース化することに基づいている。 2つ目のアプローチは、$tildeO(lsqrtm)$ stepsで最も短いパスを出力する分割および征服手順に基づいている。
  論文  参考訳（メタデータ） (2024-08-19T21:30:02Z)
• Quantum algorithms for Hopcroft's problem [45.45456673484445]
  計算幾何学の基本的な問題であるホップクロフト問題に対する量子アルゴリズムについて検討する。 この問題の古典的な複雑さはよく研究されており、最もよく知られているアルゴリズムは$O(n4/3)の時間で動作する。 我々の結果は、時間複雑性が$widetilde O(n5/6)$の2つの異なる量子アルゴリズムである。
  論文  参考訳（メタデータ） (2024-05-02T10:29:06Z)
• Do you know what q-means? [42.96240569413475]
  古典的な$varepsilon$-$k$-meansアルゴリズムは、ロイドのアルゴリズムの1つの反復の近似バージョンを時間的複雑さで実行する。 また,時間的複雑さを考慮した$q$-means量子アルゴリズムも提案する。
  論文  参考訳（メタデータ） (2023-08-18T17:52:12Z)
• Exponential speedup of quantum algorithms for the pathfinding problem [5.260626311429307]
  溶接木に基づいてグラフ$G$を構築し、隣接リスト oracle $O$ でパスフィニング問題を定義する。 古典的なアルゴリズムが確率の高い指数時間で$x$-$y$パスを見つけることはできないことを証明している。 我々の発見は、量子アルゴリズムがパスフィニング問題を解決するために、より多くの種類のグラフに利点をもたらす可能性があることを示唆している。
  論文  参考訳（メタデータ） (2023-07-24T02:50:34Z)
• Detection-Recovery Gap for Planted Dense Cycles [72.4451045270967]
  期待帯域幅$n tau$とエッジ密度$p$をエルドホス=R'enyiグラフ$G(n,q)$に植え込むモデルを考える。 低次アルゴリズムのクラスにおいて、関連する検出および回復問題に対する計算しきい値を特徴付ける。
  論文  参考訳（メタデータ） (2023-02-13T22:51:07Z)
• Random Subgraph Detection Using Queries [29.192695995340653]
  植込み高密度部分グラフ検出問題は、与えられた(ランダム)グラフに異常に密度の高い部分グラフが存在するかどうかをテストするタスクを指す。 本稿では,適応的なエッジクエリを用いてグラフの比較的小さな部分のみを観測できる,上記の問題の自然な変形について考察する。 このモデルでは,植込み部分グラフの存在を検出するのに必要なクエリ数と十分なクエリ数(準多項式最適アルゴリズムを伴う)を決定する。
  論文  参考訳（メタデータ） (2021-10-02T07:41:17Z)
• Solving correlation clustering with QAOA and a Rydberg qudit system: a full-stack approach [94.37521840642141]
  量子近似最適化アルゴリズム(QAOA)とクォーディットを用いた相関クラスタリング問題について検討する。 具体的には、中性原子量子コンピュータを検討し、相関クラスタリングのためのフルスタックアプローチを提案する。 ゲート数によって定量化されるように、quditの実装はqubitエンコーディングよりも優れていることを示す。
  論文  参考訳（メタデータ） (2021-06-22T11:07:38Z)

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

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