論文の概要: Exponential quantum speedup for $\mathbb{F}_3^n$-Subset-Sum? Or, rigorous classical algorithms for Binary-Error LWE

• arxiv url: http://arxiv.org/abs/2609.40321v1
• Date: Wed, 30 Sep 2026 17:54:52 GMT
• ステータス: 翻訳完了
• システム内更新日: 2026-10-01 18:57:28.304177
• Title: Exponential quantum speedup for $\mathbb{F}_3^n$-Subset-Sum? Or, rigorous classical algorithms for Binary-Error LWE
• Title（参考訳）: $\mathbb{F}_3^n$-Subset-Sum? あるいは、バイナリエラーLWEの厳密な古典的アルゴリズムの指数量子スピードアップ
• Abstract要約: 我々は$mathbbF_3n$ 上のベクトル部分集合和を研究する。 $mathbbF_3n$から$m$のランダムベクトルが与えられたとき、0に和する空でない部分集合を見つける。 我々の量子アルゴリズムは$mathbbF_3$-subset sum in time with $m=cdot n2$。
• 参考スコア（独自算出の注目度）: 3.226707850282507
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: We study vector subset sum over $\mathbb{F}_3^n$: given $m$ random vectors from $\mathbb{F}_3^n$, find a nonempty subset that sums to zero; the smaller $m$, the more difficult it is to find such a subset. Chen, Liu, and Zhandry (EUROCRYPT'22) introduced an efficient quantum algorithm that solves this problem when $m\approx n^2/2$, where a naive classical algorithm would require exponential time. Subsequently, Kothari, O'Donnell, and Wu (STOC'2026) gave an efficient classical algorithm that only requires $m \approx n^2/3$ vectors, thus removing the hope for an exponential quantum advantage in this parameter regime. Using the framework of Chen, Liu, and Zhandry, we give quantum algorithms that require much fewer input vectors, renewing the possibility of an exponential quantum speedup: for any fixed $ε>0$, our quantum algorithm solves $\mathbb{F}_3$-subset sum in polynomial time with $m=ε\cdot n^2$ vectors. More generally, we establish a full sample--time tradeoff that interpolates between exponential and polynomial runtime. The main ingredient is a deterministic classical algorithm for the binary-error Learning-with-Errors problem, which is of independent cryptographic interest. For this, we rigorously establish a sample--time tradeoff that was predicted by earlier algebraic heuristics. For vector subset sums over larger fields, we also significantly improve classical algorithms in Kothari, O'Donnell, and Wu (STOC'2026).
• Abstract（参考訳）: 我々は $\mathbb{F}_3^n$ 上のベクトル部分集合和について研究する:$\mathbb{F}_3^n$ から$m$ランダムベクトルを与えられたとき、0 に和する空でない部分集合を見つける。 Chen, Liu, and Zhandry (EUROCRYPT'22) はこの問題を$m\approx n^2/2$で解く効率的な量子アルゴリズムを導入した。 その後、Kothari, O'Donnell, Wu (STOC'2026) は、$m \approx n^2/3$ベクトルしか必要としない効率的な古典的アルゴリズムを与えた。 Chen, Liu, Zhandry の枠組みを用いて、指数的量子スピードアップの可能性を更新し、より少ない入力ベクトルを必要とする量子アルゴリズムを与える:任意の固定$ε>0$に対して、我々の量子アルゴリズムは、$m=ε\cdot n^2$ベクトルで多項式時間で$\mathbb{F}_3$-subset sumを解く。 より一般的に、指数型ランタイムと多項式ランタイムを補間する完全なサンプル時間トレードオフを確立する。 主な要素は、バイナリエラー学習-エラー問題に対する決定論的古典的アルゴリズムである。 このため、より初期の代数的ヒューリスティックスによって予測されたサンプル時間トレードオフを厳格に確立する。 大体上のベクトル部分集合和に対しては、Kothari, O'Donnell, Wu (STOC'2026) の古典的アルゴリズムも大幅に改善する。

関連論文リスト

• Solving Sparse SDPs in Sublinear Time: A Classical Algorithm Inspired by the Quantum OR Lemma [70.99943094379263]
  有界ラディウス系におけるスパース半定値プログラムに対する最初の準時間古典的解法を与える。 我々の主な技術的貢献は、ハミルトンのギブス状態を同時に表す古典的な手続きである。
  論文  参考訳（メタデータ） (2026-09-30T17:51:21Z)
• No exponential quantum speedup for $\mathrm{SIS}^\infty$ anymore [2.8004615208539523]
  平均ケース$ell_infty暗号$-Short Solution(mathrmSISinfty$)問題に対する効率的な量子アルゴリズムを提案する。
  論文  参考訳（メタデータ） (2025-10-08T20:28:47Z)
• Space-Efficient Quantum Error Reduction without log Factors [50.10645865330582]
  本稿では,多数決のランダムウォーク解釈に類似したライン上の重み付けウォークとして理解可能な,新たに単純化された浄化器の構成を提案する。 我々の浄化器は、前者よりも指数関数的に空間の複雑さが良く、精製されるアルゴリズムの音質-完全性ギャップに四分法的に依存している。
  論文  参考訳（メタデータ） (2025-02-13T12:04:39Z)
• Quantum algorithm for the gradient of a logarithm-determinant [0.0]
  スパースランク入力演算子の逆を効率的に決定することができる。 このアルゴリズムは、完全に誤り訂正された量子コンピュータのために想定されている。 このアルゴリズムがカーネルベースの量子機械学習にどのように使えるかについて議論する。
  論文  参考訳（メタデータ） (2025-01-16T09:39:31Z)
• Sum-of-Squares inspired Quantum Metaheuristic for Polynomial Optimization with the Hadamard Test and Approximate Amplitude Constraints [76.53316706600717]
  最近提案された量子アルゴリズムarXiv:2206.14999は半定値プログラミング(SDP)に基づいている SDPにインスパイアされた量子アルゴリズムを2乗和に一般化する。 この結果から,本アルゴリズムは大きな問題に適応し,最もよく知られた古典学に近似することが示唆された。
  論文  参考訳（メタデータ） (2024-08-14T19:04:13Z)
• A Quantum Speed-Up for Approximating the Top Eigenvectors of a Matrix [2.7050250604223693]
  与えられた$dtimes d$ matrix $A$ のトップ固有ベクトルのよい近似を見つけることは、基礎的で重要な計算問題である。 上位固有ベクトルの近似の古典的な記述を出力する2つの異なる量子アルゴリズムを与える。
  論文  参考訳（メタデータ） (2024-05-23T16:33:13Z)
• Quantum algorithms for spectral sums [50.045011844765185]
  正半定値行列(PSD)のスペクトル和を推定するための新しい量子アルゴリズムを提案する。 本稿では, スペクトルグラフ理論における3つの問題に対して, アルゴリズムと手法が適用可能であることを示す。
  論文  参考訳（メタデータ） (2020-11-12T16:29:45Z)
• Quantum Gram-Schmidt Processes and Their Application to Efficient State Read-out for Quantum Algorithms [87.04438831673063]
  本稿では、生成した状態の古典的ベクトル形式を生成する効率的な読み出しプロトコルを提案する。 我々のプロトコルは、出力状態が入力行列の行空間にある場合に適合する。 我々の技術ツールの1つは、Gram-Schmidt正則手順を実行するための効率的な量子アルゴリズムである。
  論文  参考訳（メタデータ） (2020-04-14T11:05:26Z)

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

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