論文の概要: Superlinear Quantum Query Lower Bounds for Subgraph Detection

• arxiv url: http://arxiv.org/abs/2609.40263v1
• Date: Wed, 30 Sep 2026 17:42:46 GMT
• ステータス: 翻訳完了
• システム内更新日: 2026-10-01 18:57:28.207608
• Title: Superlinear Quantum Query Lower Bounds for Subgraph Detection
• Title（参考訳）: サブグラフ検出のための超線形量子クエリロー境界
• Abstract要約: サブグラフ検出は、その隣接行列にクエリを通してアクセスされる$n$-vertexグラフが、固定グラフ$H$のコピーを含むかどうかを問う。 本研究では、この問題の有界エラー量子クエリの複雑性について、非条件超線形下界を初めて証明する。
• 参考スコア（独自算出の注目度）: 5.69782807899183
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: Subgraph detection asks whether an $n$-vertex graph, accessed through queries to its adjacency matrix, contains a copy of a fixed graph $H$. We prove the first unconditional superlinear lower bounds on the bounded-error quantum query complexity of this problem, answering a longstanding open question. A copy of $H$ is a certificate of constant size, so the adversary method with nonnegative weights cannot prove superlinear lower bounds. For every fixed $r\ge 4$, detecting the clique $K_r$ requires $n^{λ_r-o(1)}$ queries, where $λ_4=19/18$, the exponents $λ_r$ increase strictly with $r$, and $λ_r\ge 2-4\sqrt{2/r}+O(1/r)$. More generally, we prove superlinear lower bounds for detecting every fixed connected graph $H$ with chromatic number $c\ge 4$. These bounds approach quadratic as $c$ grows: for sufficiently large $c$, detection requires $n^{2-O(\sqrt{\log\log c/c})-o(1)}$ queries. Chromatic number alone does not characterize the quantum query complexity of subgraph detection: we show that detecting the complete bipartite graph $K_{r,r}$ requires $n^{β_r-o(1)}$ queries, where $β_{10}=181/180$ and $β_r\ge 2-O(1/\sqrt{r})$. Our main technical result is a lower bound for finding an all-ones certificate from a known family when the input bits are sampled independently. Its proof combines Zhandry's compressed oracle (CRYPTO 2019) with conditioning on a randomly planted certificate, adapting an argument of Belovs (FOCS 2026). Our hard instances are built from graphs containing many copies of the desired subgraph with limited overlap. For cliques, we use a construction of Gowers and Janzer (CPC 2021); for complete bipartite graphs, we use a random construction.
• Abstract（参考訳）: サブグラフ検出は、その隣接行列にクエリを通してアクセスされる$n$-vertexグラフが、固定グラフ$H$のコピーを含むかどうかを問う。 我々は、この問題の有界エラー量子クエリの複雑さに対して、最初の非条件超線形下界を証明し、長年の未解決問題に答える。 H$のコピーは一定サイズの証明書なので、非負の重みを持つ逆法は超線型な下界を証明できない。 すべての固定$r\ge 4$に対して、clique $K_r$を検出するには$n^{λ_r-o(1)}$クエリが必要であり、ここでは$λ_4=19/18$、指数$λ_r$は$r$で厳密に増加し、$λ_r\ge 2-4\sqrt{2/r}+O(1/r)$である。 より一般に、色数 $c\ge 4$ のすべての固定連結グラフ $H$ を検出するための超線型下界を証明する。 十分に大きな$c$の場合、検出には$n^{2-O(\sqrt{\log\log c/c})-o(1)} のクエリが必要である。 クロマティック数だけでは、部分グラフ検出の量子クエリの複雑さを特徴づけるものではない: 完全二部グラフを検出できる$K_{r,r}$は$n^{β_r-o(1)}$クエリを必要とし、$β_{10}=181/180$と$β_r\ge 2-O(1/\sqrt{r})$である。 我々の主な技術的結果は、入力ビットが独立してサンプリングされたとき、既知の家族からオールワン証明書を見つけるための低い境界である。 この証明は、Zhandry's compressed Oracle (CRYPTO 2019) とランダムに植えられた証明書の条件付けを組み合わせ、Belovs (FOCS 2026) の議論に適合させる。 私たちのハードインスタンスは、所望のサブグラフのコピーを多く含むグラフから構築され、重複は限定されています。 斜めの場合、Gowers and Janzer (CPC 2021) の構成を使い、完全二部グラフではランダムな構成を用いる。

関連論文リスト

• Faster quantum linear system solver beyond the condition number [50.84794327094274]
  線形系の正規化解 $|xrangle$ を生成する2つの量子アルゴリズムを、条件数$=lVert A-1rVert$ に依存しない複雑性を持つ精度 $Ax=| b rangle$ に提示する。 フィルタベースのソルバは非常にシンプルで、実行時プレファクタが適しています。
  論文  参考訳（メタデータ） (2026-07-08T17:49:40Z)
• Detecting Arbitrary Planted Subgraphs in Random Graphs [7.320365821066746]
  本稿では,ErdHos-R'enyi乱数グラフ$mathcalG(n, q_n)$における仮設植木部分グラフ$Gamma = Gamma_n$の検出について検討する。 エッジ確率が$p_n$と$q_n$が固定された高密度な状態では、Gamma$を検出するための情報理論および計算しきい値が強く特徴付けられる。
  論文  参考訳（メタデータ） (2025-03-24T18:54:43Z)
• Fingerprinting Codes Meet Geometry: Improved Lower Bounds for Private Query Release and Adaptive Data Analysis [25.476062424924713]
  本稿では,フィンガープリント方式の下位境界の証明のための一般的なフレームワークを提案する。 宇宙上の任意の適応的数え上げクエリにQ$$$mathcalX$ to accuracy $alpha$ needs $Omega(fracsqrt log|mathcalX| log (1/delta) log Qvarepsilonalpha2)$ sample, matching known upper bounds to constants。
  論文  参考訳（メタデータ） (2024-12-18T23:11:07Z)
• A quantum algorithm for learning a graph of bounded degree [1.8130068086063336]
  本稿では,最大$tildeO(d2m3/4)$量子クエリにおいて,$G$のエッジを学習するアルゴリズムを提案する。 特に、確率の高い確率で$tildeO(sqrtm)$量子クエリでサイクルとマッチングを学習するランダム化アルゴリズムを提案する。
  論文  参考訳（メタデータ） (2024-02-28T21:23:40Z)
• Detection of Dense Subhypergraphs by Low-Degree Polynomials [72.4451045270967]
  ランダムグラフにおける植込み高密度部分グラフの検出は、基本的な統計的および計算上の問題である。 我々は、$Gr(n, n-beta)ハイパーグラフにおいて、植えた$Gr(ngamma, n-alpha)$ subhypergraphの存在を検出することを検討する。 平均値の減少に基づく硬さが不明な微妙な対数密度構造を考えると,この結果はグラフの場合$r=2$で既に新しくなっている。
  論文  参考訳（メタデータ） (2023-04-17T10:38:08Z)
• Low-degree learning and the metric entropy of polynomials [44.99833362998488]
  少なくとも$Omega(sqrtvarepsilon)2dlog n leq log mathsfM(mathscrF_n,d,|cdot|_L,varepsilon)は2辺の推定値$c(1-varepsilon)2dlogを満たす。
  論文  参考訳（メタデータ） (2022-03-17T23:52:08Z)
• 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)

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

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