論文の概要: Quantum Algorithm for Identifying Hidden Graphs: Spectral Theory and Numerical Evidence

• arxiv url: http://arxiv.org/abs/2605.11228v1
• Date: Mon, 11 May 2026 20:44:32 GMT
• ステータス: 翻訳完了
• システム内更新日: 2026-05-13 21:48:56.420899
• Title: Quantum Algorithm for Identifying Hidden Graphs: Spectral Theory and Numerical Evidence
• Title（参考訳）: 隠れグラフ同定のための量子アルゴリズム:スペクトル理論と数値的エビデンス
• Authors: Pawel Wocjan,
• Abstract要約: 隠れた$d$正規基底グラフを識別するための量子アルゴリズムを、その難解バージョンへのアクセスから$n$頂点に$G$を与える。 我々のアルゴリズムは概念的には単純で、$G_rm spire$ 上で連続時間ウォークし、古典的には pret*$ で 1 つのアダマールテストを行う。
• 参考スコア（独自算出の注目度）: 0.0
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: We give a quantum algorithm for a novel type of black-box problem: identifying a hidden $d$-regular base graph $G$ on $n$ vertices from oracle access to an obfuscated version of it, rather than traversing it. From $G$ we build the spired graph $G_{\rm spire}$ in three steps: each vertex is lifted into an exponentially large cluster, with adjacent clusters joined by a random bipartite graph; each cluster is then crowned with a balanced spire; finally, all vertices are randomly relabelled. Specializing to $G=K_2$ recovers the welded-trees graph. Our algorithm is conceptually simple: a continuous-time quantum walk on $G_{\rm spire}$, followed by a single Hadamard test at a classically precomputed time $t^*$; the algorithm returns the candidate whose predicted amplitude is closest to the measurement. The design rests on a rigorous spectral theory: from the apex of any spire, the walk is confined to a polynomial-dimensional invariant subspace evolving under the adjacency matrix of a simpler towered graph $G_{\rm tower}$; that matrix block-diagonalizes into $n$ independent tridiagonal systems of size $n$, each solved in closed form by a Chebyshev secular equation. Efficient numerics enabled by this decomposition supply $t^*$ and the predicted amplitudes. On the prism graphs $Y_m$ versus the Möbius ladders $M_m$ (each on $n=2m$ vertices), the numerical study supports a precise conjecture that $\widetilde O(n^2/\log n)$ measurements at evolution time of order $m^2$ suffice to distinguish the two families; we have tested $4 \le m \le 5121$ ($n$ up to $10242$). By analogy with the welded-trees lower bounds, we further conjecture that any classical algorithm requires queries exponential in $n$. Together these conjectures point to an exponential quantum speedup for the identification of an obfuscated base graph.
• Abstract（参考訳）: 隠れた$d$-regular基底グラフ $G$ on $n$ vertices を、難読化バージョンをトラバースするのではなく、オラクルアクセスから同定する。 それぞれの頂点は指数関数的に大きなクラスタに持ち上げられ、隣のクラスタはランダムな二部グラフで結合されます。 特別な$G=K_2$は溶接木グラフを復元する。 我々のアルゴリズムは概念的には単純である:$G_{\rm spire}$上の連続時間量子ウォーク、次いで古典的に事前計算された時間$t^*$での1つのアダマール試験により、アルゴリズムは予測振幅が測定に最も近い候補を返す。 この設計は厳密なスペクトル理論に基づいており、任意の尖点の頂点から、ウォークは単純なタワー付きグラフ $G_{\rm Tower}$ の隣接行列の下で進化する多項式次元不変部分空間に制限される。 この分解によって実現された効率的な数値は、$t^*$と予測振幅を供給する。 プリズムグラフの$Y_m$とMöbiusのはしごの$M_m$(いずれも$n=2m$ vertices)では、数値的な研究は、$\widetilde O(n^2/\log n)$が2つの族を区別するために階数$m^2$ sufficeの進化時の測定である、という正確な予想を支持している。 溶接木の下限の類似により、任意の古典的アルゴリズムは$n$で指数関数的なクエリを必要とすると推測する。 これらの予想は、難解な基底グラフの同定のための指数的量子スピードアップを示している。

関連論文リスト

• Combinatorial foundations for solvable chaotic local Euclidean quantum circuits in two dimensions [0.0]
  我々は、$mathbbZ2$ の任意の有界拡張が測地的に直交可能であることを示す。 これは、正確に解けるカオス局所量子回路を考案できる設定を提供する。
  論文  参考訳（メタデータ） (2025-12-02T18:54:23Z)
• Quantum phase discrimination with applications to quantum search on graphs [0.0]
  本稿では,この課題に対して量子位相判別(QPD)という量子アルゴリズムを提案する。 QPDを用いることで、Li と Zur が提案するパスフィニングアルゴリズムのクエリ複雑性を低減できる。 グラフ上の量子探索に2つの応用を提案する。
  論文  参考訳（メタデータ） (2025-04-21T16:06:43Z)
• Quantum computing algorithms for inverse problems on graphs and an NP-complete inverse problem [2.107421958337625]
  有限グラフ $(X,E)$ に対する逆問題を考える。 この問題には特定の条件下でのユニークな解法があることを示し、量子計算法を開発した。
  論文  参考訳（メタデータ） (2023-06-08T14:48:48Z)
• Improved High-Probability Regret for Adversarial Bandits with Time-Varying Feedback Graphs [62.52390282012508]
  我々は、T$ラウンド以上の時間変化フィードバックグラフを持つ、敵対的な$K$武器付きバンディットに対する高い確率的後悔境界について検討する。 提案アルゴリズムは,高い確率で最適に後悔する$widetildemathcalO((sum_t=1Talpha_t)1/2+max_tin[T]alpha_t]$を達成するアルゴリズムを開発した。 また,弱可観測グラフに対する最適高確率残差を求めるアルゴリズムを開発した。
  論文  参考訳（メタデータ） (2022-10-04T04:36:15Z)
• Fast Graph Sampling for Short Video Summarization using Gershgorin Disc Alignment [52.577757919003844]
  高速グラフサンプリングの最近の進歩を利用して,短い動画を複数の段落に効率よく要約する問題について検討する。 実験結果から,本アルゴリズムは最先端の手法と同等の映像要約を実現し,複雑さを大幅に低減した。
  論文  参考訳（メタデータ） (2021-10-21T18:43:00Z)
• Random Subgraph Detection Using Queries [29.192695995340653]
  植込み高密度部分グラフ検出問題は、与えられた(ランダム)グラフに異常に密度の高い部分グラフが存在するかどうかをテストするタスクを指す。 本稿では,適応的なエッジクエリを用いてグラフの比較的小さな部分のみを観測できる,上記の問題の自然な変形について考察する。 このモデルでは,植込み部分グラフの存在を検出するのに必要なクエリ数と十分なクエリ数(準多項式最適アルゴリズムを伴う)を決定する。
  論文  参考訳（メタデータ） (2021-10-02T07:41:17Z)
• A framework for optimal quantum spatial search using alternating phase-walks [0.0]
  我々は、マーク頂点位相シフトと連続時間量子ウォークの交互適用により、Childs & Goldstone(mathcalCG$)アルゴリズムを一般化する。 様々なグラフ上の$mathcalO(sqrtN)$検索にアルゴリズムを適用することで,アルゴリズムの有効性を実証する。
  論文  参考訳（メタデータ） (2021-09-29T11:16:52Z)
• Quantum double aspects of surface code models [77.34726150561087]
  基礎となる量子double $D(G)$対称性を持つ正方格子上でのフォールトトレラント量子コンピューティングの北エフモデルを再検討する。 有限次元ホップ代数$H$に基づいて、我々の構成がどのように$D(H)$モデルに一般化するかを示す。
  論文  参考訳（メタデータ） (2021-06-25T17:03:38Z)
• Learning Sparse Graph Laplacian with K Eigenvector Prior via Iterative GLASSO and Projection [58.5350491065936]
  グラフ Laplacian 行列 $L$ 上の構造的仮定を考える。 最初の$K$ eigenvectors of $L$は、例えばドメイン固有の基準に基づいて事前選択される。 本稿では,H_u+$$$$barC$で最も適切なグラフラプラシアン行列$L*を計算するために,効率的なハイブリッドグラフラッソ/投影アルゴリズムを設計する。
  論文  参考訳（メタデータ） (2020-10-25T18:12:50Z)

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

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