論文の概要: A Quantum Lower Bound for Triangle Finding

• arxiv url: http://arxiv.org/abs/2611.06751v1
• Date: Wed, 04 Nov 2026 16:27:34 GMT
• ステータス: 翻訳完了
• システム内更新日: 2026-11-06 03:25:58.204199
• Title: A Quantum Lower Bound for Triangle Finding
• Title（参考訳）: 三角探傷用量子下界
• Abstract要約: 三角探索は、量子アルゴリズム技術の発達において中心的な役割を果たしてきたグラフ理論の基本的な問題である。 我々は、三角形探索のための最初の超線形量子クエリの下限を証明し、$(N13/12)$クエリが必要であることを示す。
• 参考スコア（独自算出の注目度）: 5.2990954912619666
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: Triangle finding is a fundamental problem in graph theory that has played a central role in the development of quantum algorithmic techniques. For $N$-vertex graphs given by their adjacency matrices, a long line of work has improved the quantum query upper bound from $O(N^{3/2})$ to $O(N^{5/4})$. However, the best known lower bound has remained the elementary $Ω(N)$ bound obtained from unstructured search. We prove the first superlinear quantum query lower bound for triangle finding, showing that $Ω(N^{13/12})$ queries are necessary. Our result also implies the same lower bound for triangle detection and for detecting every fixed connected non-bipartite graph. The proof builds on the compressed oracle approach of Zhandry and the transfer approaches of Belovs. It compares the computation on graphs with a planted triangle to the computation on random graphs conditioned to be triangle-free, through a map on the input registers that almost commutes with every query. We average over local changes to the input while preserving its distribution, through a procedure known as conditional resampling. Our main technical contribution is a set of estimates that let us control the query error under this averaging, despite the dependence introduced by conditioning a dense graph to be triangle-free.
• Abstract（参考訳）: 三角探索は、量子アルゴリズム技術の発達において中心的な役割を果たしてきたグラフ理論の基本的な問題である。 隣接行列によって与えられる$N$-頂点グラフに対して、長い行の作業により、量子クエリ上界が$O(N^{3/2})$から$O(N^{5/4})$に改善された。 しかし、最もよく知られた下界は、非構造探索から得られる基本$Ω(N)$境界のままである。 我々は、三角形探索のための最初の超線形量子クエリの下界を証明し、$Ω(N^{13/12})$クエリが必要であることを示す。 この結果は、三角形検出と全ての固定連結非二分グラフの検出において、同じ下界をも意味している。 この証明は Zhandry の圧縮オラクルアプローチと Belovs の転送アプローチに基づいている。 グラフ上の計算と植込み三角形と、三角形のないと条件づけられたランダムグラフの計算を、全てのクエリでほぼ通勤する入力レジスタ上のマップを通して比較する。 我々は、条件再サンプリングと呼ばれる手順を通じて、その分布を保ちながら、入力に対する局所的な変化を平均化する。 我々の主な技術的貢献は、この平均化の下でクエリエラーを制御できる一連の推定である。

関連論文リスト

• Quantum Query Lower Bounds for Triangle-Listing and Spanners [3.3186745403320326]
  固定された$kge 7$に対して、乗法的な$k$-spannerを構成するには$(n1+frac12_k)$の量子クエリが必要である。 これは三角形リストのための最初の非自明な量子下界であり、ジアンとペン(ICML 2026)が提起した質問である。
  論文  参考訳（メタデータ） (2026-09-29T09:18:33Z)
• Optimal Lower Bounds for Hamiltonian Simulation [42.227880669333835]
  ハミルトニアン$H = sum_j h_j$ の場合、ゲート上の下界と量子コンピュータ上の時間発展をシミュレートするクエリの複雑さを証明できる。 任意の項ノルムのホールドは$|h_j|$, time $t$, trace-distance error $$である。
  論文  参考訳（メタデータ） (2026-07-22T07:41:32Z)
• 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)
• Quantum Algorithms for Triangle Cut Sparsification [5.700173588723832]
  本稿では,各カットにまたがる三角形数を保存しながら,グラフサイズを小さくすることを目的とした三角形カットスペーシフィケーションの問題について検討する。 三角形を列挙する量子アルゴリズムを提案し, 頂点が$n$, 辺が$m$, 三角形が$t$のグラフが時間内に実行される。 三角関係測度に基づくクラスタリングアルゴリズムの応用を実証し、任意の$varepsilon$-triangle cutスペーサーのサイズの低い境界を証明した。
  論文  参考訳（メタデータ） (2026-06-04T15:25:34Z)
• Hardness of High-Dimensional Linear Classification [58.29089693778071]
  我々は、最大半空間離散性問題に対する次元下界の新たな指数関数を確立する。 どちらも計算幾何学と機械学習の基本的問題であり、その正確で近似的な形式である。
  論文  参考訳（メタデータ） (2026-03-19T15:53:41Z)
• Hiding, Shuffling, and Cycle Finding: Quantum Algorithms on Edge Lists [5.127310126394387]
  三角形探索問題の3つの変種の量子クエリ複雑性について検討する。 Zhandryのレコードクエリフレームワークのバウンダリが低いことを証明します。 我々はBelovsの学習グラフアルゴリズムを$k$-distinctnessに適応させる。
  論文  参考訳（メタデータ） (2024-12-23T18:43:41Z)
• Random Subgraph Detection Using Queries [29.192695995340653]
  植込み高密度部分グラフ検出問題は、与えられた(ランダム)グラフに異常に密度の高い部分グラフが存在するかどうかをテストするタスクを指す。 本稿では,適応的なエッジクエリを用いてグラフの比較的小さな部分のみを観測できる,上記の問題の自然な変形について考察する。 このモデルでは,植込み部分グラフの存在を検出するのに必要なクエリ数と十分なクエリ数(準多項式最適アルゴリズムを伴う)を決定する。
  論文  参考訳（メタデータ） (2021-10-02T07:41:17Z)
• Learning Sparse Graph with Minimax Concave Penalty under Gaussian Markov Random Fields [51.07460861448716]
  本稿では,データから学ぶための凸解析フレームワークを提案する。 三角凸分解はその上部に対応する変換によって保証されることを示す。
  論文  参考訳（メタデータ） (2021-09-17T17:46:12Z)
• Solving correlation clustering with QAOA and a Rydberg qudit system: a full-stack approach [94.37521840642141]
  量子近似最適化アルゴリズム(QAOA)とクォーディットを用いた相関クラスタリング問題について検討する。 具体的には、中性原子量子コンピュータを検討し、相関クラスタリングのためのフルスタックアプローチを提案する。 ゲート数によって定量化されるように、quditの実装はqubitエンコーディングよりも優れていることを示す。
  論文  参考訳（メタデータ） (2021-06-22T11:07:38Z)
• Quantum algorithms for spectral sums [50.045011844765185]
  正半定値行列(PSD)のスペクトル和を推定するための新しい量子アルゴリズムを提案する。 本稿では, スペクトルグラフ理論における3つの問題に対して, アルゴリズムと手法が適用可能であることを示す。
  論文  参考訳（メタデータ） (2020-11-12T16:29:45Z)

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

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