論文の概要: Quantum Query Lower Bounds for Triangle-Listing and Spanners
- arxiv url: http://arxiv.org/abs/2609.37091v1
- Date: Tue, 29 Sep 2026 09:18:33 GMT
- ステータス: 翻訳完了
- システム内更新日: 2026-09-30 21:28:47.371442
- Title: Quantum Query Lower Bounds for Triangle-Listing and Spanners
- Title（参考訳）: 三角形リストとスパナのための量子クエリローバウンド
- Abstract要約: 固定された$kge 7$に対して、乗法的な$k$-spannerを構成するには$(n1+frac12_k)$の量子クエリが必要である。
これは三角形リストのための最初の非自明な量子下界であり、ジアンとペン(ICML 2026)が提起した質問である。
- 参考スコア（独自算出の注目度）: 3.3186745403320326
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: This paper gives quantum query lower bounds for two relational graph problems, triangle listing and explicit multiplicative spanner construction, in the general graph query model, where quantum adjacency, degree and neighborhood queries are all available in arbitrary superposition. Both results are obtained by reductions via intermediate multi-block search problems. We extend the quantum query recording framework by Zhandry (CRYPTO 2019) and Hamoudi and Magniez (ToCT 2023) to handle a recording architecture for bidirectional oracles and give a generic blockwise soundness framework, which for arbitrary families of local accepting projectors, gives an exact operator-norm characterization of their maximum overlap with the subspace of bounded weight records. Using the intermediate search problems, we exhibit a family of $n$-vertex graphs with $Θ(n)$ triangles on which listing any constant fraction of the triangles requires $Ω(n^{3/2-o(1)})$ quantum queries. This is the first nontrivial quantum lower bound for triangle listing, a question raised by Jiang and Peng (ICML 2026). Further, we show that, for every fixed $k\ge 7$, constructing a multiplicative $k$-spanner requires $Ω(n^{1+\frac{1}{2μ_k}})$ quantum queries, where $μ_k=k/3+O(1)$. For $k\in\{7,8\}$ the bound is $Ω(n^{5/4})$, which matches what would be implied by an unproven instance of the Erdős girth conjecture, and for large $k$ the exponent $1+\frac{3}{2k}$ exceeds the $1+\frac{4}{3k}$ implied by the provable high girth dense graphs due to Lazebnik, Ustimenko and Woldar, 1995.
- Abstract（参考訳）: 本稿では, 2つの関係グラフ問題, 三角形リストと明示的乗法スパンナー構成について, 量子隣接性, 次数, 近傍クエリがすべて任意の重ね合わせで利用できる一般グラフクエリモデルを提案する。
どちらの結果も中間的マルチブロック探索問題による削減によって得られる。
Zhandry (CRYPTO 2019) と Hamoudi と Magniez (ToCT 2023) による量子クエリ記録フレームワークを拡張して、双方向のオラクルの記録アーキテクチャを処理し、局所受容プロジェクタの任意のファミリーに対して、境界重みレコードのサブ空間との最大重なりの正確な演算ノルム特性を与える汎用ブロックワイズ・サウンドネス・フレームワークを提供する。
中間探索問題を用いて、この三角形の任意の定数分を列挙する$n(n)$三角形を持つ$n$頂点グラフの族を、$Ω(n^{3/2-o(1)})$量子クエリーで表す。
これは三角形リストのための最初の非自明な量子下界であり、ジアンとペン(ICML 2026)が提起した質問である。
さらに、固定されたすべての$k\ge 7$に対して、乗法的な$k$-spannerを構成するには$Ω(n^{1+\frac{1}{2μ_k}})$量子クエリが必要であり、$μ_k=k/3+O(1)$である。
k に対して$k\in\{7,8\}$ は$Ω(n^{5/4})$ であり、これはエルデシュ・ギルト予想の不証明のインスタンスによって示唆されるものと一致し、大きな$k$ に対して1+\frac{3}{2k}$ はラゼブニク、ウスティメンコ、ウォルダーによる証明可能な高次グラフによって示唆される 1+\frac{4}{3k}$ を超える。
関連論文リスト
- The I3322 quantum value is attained spatially but not in finite dimension [0.0]
S$ をコリンズ・ギシン正規化の $I_3322$ Bell 関数の量子超越(古典的境界 0; 2量子ビット最大値 1/4)とする。
i) 有限次元の量子戦略が$S$(任意の有限局所次元、純粋または混合状態、射影またはPOVM測定)に達することはないこと、PalとVertesi(2010)を証明すること。
次元複雑性も決定する:$S_d$で局所次元$le d$と$D()=mind:S-S_dの最適値
論文 参考訳（メタデータ） (2026-09-03T15:48:01Z) - Quantum Speedups for Stochastic Optimization with Heavy-Tailed Noise [49.730496294398726]
重み付き確率変数に対する新しい量子平均推定器を開発した。
尾指数>4/3$のより強い下界を導出し、次元への非自明な依存が避けられないことを示す。
凸目的関数に対して,量子射影勾配降下法を提案する。
論文 参考訳（メタデータ） (2026-07-28T09:29:37Z) - No finite level of the NPA hierarchy is exact for the doubly-tilted CHSH functional near the critical tilt [0.0]
すべての NPA レベル $kge 2$ に対して、$g_k>0$ と $s*_k>0$ が存在し、$c_k(s)ge 4-s+g_k s2$ on $(0,s*_k)$ であることを示す。
$kge 3$ の量子状態はなく、量子モデルの滑らかな曲線も利得方向を実現することができないので、オーバーシュートは NPA コーンの非量子部分に厳密に存在する。
論文 参考訳（メタデータ） (2026-07-15T12:22:23Z) - Quantum Communication Lower Bounds for Search Problems via Matrix Discrepancy [4.843542453440025]
探索問題に対する一方向量子通信の低境界について検討する。
衝突検出のためには、厳密な$(N1/4)$ワンウェイ量子通信を低い境界で証明する。
三角形を見つけるためには、$m$エッジを持つグラフに対して$left(sqrt_Vright)$、$(m)$トライアングル、定数$_E$の1パス量子ストリーミング空間を低い境界で証明する。
論文 参考訳（メタデータ） (2026-07-09T14:11:09Z) - Strict Hierarchy for Quantum Channel Certification to Unitary [33.25179630727782]
量子チャネル認証問題に対する最適量子アルゴリズムをユニタリに提示する。
Fawzi, Flammarion, Garivier, Oufkirによる低いバウンダリにマッチする不整合アクセスモデルに対して,$(d/varepsilon2)$クエリが十分であることを示す。
これは、様々なアクセスモデルにまたがるユニタリへの量子チャネル認証の複雑さの厳密な階層を示している。
論文 参考訳（メタデータ） (2026-04-29T17:10:34Z) - Hardness of High-Dimensional Linear Classification [58.29089693778071]
我々は、最大半空間離散性問題に対する次元下界の新たな指数関数を確立する。
どちらも計算幾何学と機械学習の基本的問題であり、その正確で近似的な形式である。
論文 参考訳（メタデータ） (2026-03-19T15:53:41Z) - Spectral Gaps with Quantum Counting Queries and Oblivious State Preparation [47.600794349481966]
本研究では、量子ビットの対数数を用いて、加算誤差$epsilonDelta_k$まで値を近似する量子アルゴリズムを提案する。
この分析における重要な技術的ステップは、適切なランダム初期状態の準備であり、最終的には閾値よりも小さい固有値の数を効率的に数えることができる。
論文 参考訳（メタデータ） (2025-08-28T17:04:18Z) - Hiding, Shuffling, and Cycle Finding: Quantum Algorithms on Edge Lists [5.127310126394387]
三角形探索問題の3つの変種の量子クエリ複雑性について検討する。
Zhandryのレコードクエリフレームワークのバウンダリが低いことを証明します。
我々はBelovsの学習グラフアルゴリズムを$k$-distinctnessに適応させる。
論文 参考訳（メタデータ） (2024-12-23T18:43:41Z) - Beyond the Berry Phase: Extrinsic Geometry of Quantum States [77.34726150561087]
状態の量子多様体のすべての性質がゲージ不変のバーグマンによって完全に記述されることを示す。
偏光理論への我々の結果の即時適用について述べる。
論文 参考訳（メタデータ） (2022-05-30T18:01:34Z) - Quantum double aspects of surface code models [77.34726150561087]
基礎となる量子double $D(G)$対称性を持つ正方格子上でのフォールトトレラント量子コンピューティングの北エフモデルを再検討する。
有限次元ホップ代数$H$に基づいて、我々の構成がどのように$D(H)$モデルに一般化するかを示す。
論文 参考訳（メタデータ） (2021-06-25T17:03:38Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。