論文の概要: Quantum Fine-Grained Lower Bounds for SetDisjointness via Sub-Linear Reductions from 3SUM

• arxiv url: http://arxiv.org/abs/2609.40293v1
• Date: Wed, 30 Sep 2026 17:50:11 GMT
• ステータス: 翻訳完了
• システム内更新日: 2026-10-01 18:57:28.262477
• Title: Quantum Fine-Grained Lower Bounds for SetDisjointness via Sub-Linear Reductions from 3SUM
• Title（参考訳）: 3SUMからのサブ線形還元によるSetDisjointnessのための量子微粒下界
• Abstract要約: 3SUMからオンラインSetDisjointnessへ、最初のサブ線形時間量子還元を与える。 また、3XORとの類似の低減も行います。 これらの結果は、SetDisjointnessへのきめ細かい還元のための一般的なフレームワークに由来する。
• 参考スコア（独自算出の注目度）: 3.593955557310285
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: In classical fine-grained complexity, the 3SUM Conjecture is used to prove a variety of conditional lower bounds on data structure and graph problems via an initial reduction to the SetDisjointness problem. However, there is an $\tilde{O}(n)$-time quantum algorithm for 3SUM and a direct application of Grover's algorithm to SetDisjointness queries beats the state-of-the-art classical conditional bound by Kopelowitz, Pettie, and Porat (SODA 2016); this shows that these classical bounds do not apply in the quantum setting. Thus establishing analogous conditional lower bounds in the quantum setting requires applying the quantum 3SUM Conjecture to a \emph{quantum} fine-grained reduction from 3SUM to SetDisjointness. We give the first sub-linear time quantum reductions from 3SUM to online SetDisjointness. Via our reduction, the quantum 3SUM conjecture implies a $p + 2q \geqslant 1$ tradeoff bound for quantum SetDisjointness algorithms with $O(N^p)$ preprocessing time and $O(N^q)$ query time. We also give an analogous reduction from 3XOR. These results are derived from a general framework for fine-grained reductions to SetDisjointness which applies to any Abelian 3-Orthogonal Array (3OA) problem with suitable almost-linear hash functions.
• Abstract（参考訳）: 古典的なきめ細かい複雑性では、3SUM Conjecture は、SetDisjointness問題への初期還元を通じて、データ構造とグラフ問題に対する様々な条件付き下界を証明するために用いられる。 しかし、3SUM に対する $\tilde{O}(n)$-time 量子アルゴリズムがあり、Grover のアルゴリズムの SetDisjointness クエリへの直接適用は、Kopelowitz, Pettie, Porat (SODA 2016) による最先端の古典的条件を破る。 したがって、量子設定において類似条件下界を確立するには、量子3SUM Conjecture を 3SUM から SetDisjointness への微細な還元に応用する必要がある。 3SUMからオンラインSetDisjointnessへ、最初のサブ線形時間量子還元を与える。 我々の減少のため、量子3SUM予想は、$O(N^p)$プレプロセッシング時間と$O(N^q)$クエリ時間を持つ量子SetDisjointnessアルゴリズムのトレードオフ境界を$p + 2q \geqslant 1$とする。 また、3XORとの類似の低減も行います。 これらの結果は,任意のAbelian 3-Orthogonal Array (3OA)問題に適用可能なSetDisjointnessの微細化のための一般的なフレームワークから導かれる。

関連論文リスト

• Quantum Speedups for Stochastic Optimization with Heavy-Tailed Noise [49.730496294398726]
  重み付き確率変数に対する新しい量子平均推定器を開発した。 尾指数>4/3$のより強い下界を導出し、次元への非自明な依存が避けられないことを示す。 凸目的関数に対して,量子射影勾配降下法を提案する。
  論文  参考訳（メタデータ） (2026-07-28T09:29:37Z)
• 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 state isomorphism problems for groups [41.49556721904551]
  群作用下での量子状態同型問題の計算複雑性について検討する。 純粋状態バージョンの場合、問題はすべての非自明な群に対して BQP-hard であることが示される。 混合状態バージョンの場合、非自明で有限で効率的な表現可能な群に対して、問題はQSZK完全である。
  論文  参考訳（メタデータ） (2026-05-12T18:05:27Z)
• On the (Classical and Quantum) Fine-Grained Complexity of Log-Approximate CVP and Max-Cut [2.2776283699063664]
  最大カット問題(Max-Cut)の1-varepsilon$と1-varepsilon1/2$から、任意の有限$ell_p$-normの下での$gamma$-Approximate Closest Vector Problemへの線形サイズの縮小を示す。 有限 $ell_p$-norm における $o(sqrtlog nfrac1p)$- Approximate Closest Vector Problem に対する部分指数時間(古典的あるいは量子的)アルゴリズムは、状態よりも高速であることを示す。
  論文  参考訳（メタデータ） (2024-11-06T18:58:17Z)
• Calculating response functions of coupled oscillators using quantum phase estimation [40.31060267062305]
  量子コンピュータを用いた結合型古典的高調波発振器系の周波数応答関数の推定問題について検討する。 提案する量子アルゴリズムは,標準的な$sスパース,オーラクルベースのクエリアクセスモデルで動作する。 そこで,本アルゴリズムの簡単な適応により,時間内に無作為な結束木問題を解くことを示す。
  論文  参考訳（メタデータ） (2024-05-14T15:28:37Z)
• Quantum Lower Bounds for Finding Stationary Points of Nonconvex Functions [8.495749905129278]
  非最適化に対する古典的な下界の進歩にもかかわらず、これらの境界は依然として広く開である。 最初の設定について、Omegabig(frac-1+ppp)$。 第二設定については、おめがの()$。 Omega()$ if 勾配関数は滑らかである。 Omega()$ if 勾配関数は滑らかである。 Omega()$ if 勾配関数は滑らかである。 Omega()$ if 勾配関数は滑らかである。
  論文  参考訳（メタデータ） (2022-12-07T19:02:36Z)
• Quantum Worst-Case to Average-Case Reductions for All Linear Problems [66.65497337069792]
  量子アルゴリズムにおける最悪のケースと平均ケースの削減を設計する問題について検討する。 量子アルゴリズムの明示的で効率的な変換は、入力のごく一部でのみ正し、全ての入力で正しくなる。
  論文  参考訳（メタデータ） (2022-12-06T22:01:49Z)
• Matching Triangles and Triangle Collection: Hardness based on a Weak Quantum Conjecture [0.8924669503280332]
  これら2つのグラフ問題のいずれかに対する$n1.5-epsilon$の時間量子アルゴリズムは、k-SAT, 3SUM, APSPの量子アルゴリズムを高速化することを示す。 また、データ構造とアムバイニスの変動時間探索を慎重に利用する必要がある量子アルゴリズムを提案する。
  論文  参考訳（メタデータ） (2022-07-22T13:16:50Z)
• Limits of quantum speed-ups for computational geometry and other problems: Fine-grained complexity via quantum walks [0.0]
  いくつかの計算問題に対して、量子アルゴリズムの時間的複雑さを最適に下界として証明する。 我々の下界のほとんどは、既知の上界と一致しているため、量子スピードアップに厳しい制限が課せられるため、最適である。
  論文  参考訳（メタデータ） (2021-06-03T17:22:08Z)

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

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