論文の概要: Regev's reduction as a candidate quantum algorithm for the discrete logarithm problem in finite abelian groups

• arxiv url: http://arxiv.org/abs/2605.03972v1
• Date: Tue, 05 May 2026 16:54:14 GMT
• ステータス: 翻訳完了
• システム内更新日: 2026-05-06 19:35:44.048997
• Title: Regev's reduction as a candidate quantum algorithm for the discrete logarithm problem in finite abelian groups
• Title（参考訳）: 有限アーベル群における離散対数問題に対する候補量子アルゴリズムとしてのレゲフの還元
• Authors: M. Isabel Franco Garrido, André Chailloux,
• Abstract要約: 我々は、有限体上の離散対数問題(DLOG)のインスタンスをリード・ソロモン符号の復号問題に変換するCheng and Wanの縮小を再考する。 レゲフの還元は、符号の復号器を二重符号上の復号問題のための量子解法器に変える。 我々は、Cheng-Wanインスタンスに対するRegevの削減を評価し、それを既知の効率的なデコーダで評価する。
• 参考スコア（独自算出の注目度）: 2.5782420501870296
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: We revisit the reduction of Cheng and Wan, which transforms instances of the discrete logarithm problem (DLOG) over finite fields into a decoding problem for Reed--Solomon codes, and study how Regev's reduction can be used to solve these instances. Regev's reduction turns a decoder for a code into a quantum solver for a decoding problem on the dual code. The quantum advantage depends on the dual problem being classically hard, which has proven difficult to establish. The Cheng--Wan reduction offers a natural source of such instances: solving them would solve discrete logarithm. Since Shor's algorithm already solves discrete logarithm, the goal is not a new quantum speedup but to understand whether Regev's reduction, applied to a problem we have independent reasons to believe is hard, can solve discrete logarithm, and if not, where it falls short. We generalize the hardness consequence of the Cheng--Wan reduction for Reed--Solomon bounded distance decoding -- from solving DLOG in $\mathbb{F}_{q^h}^\times$ to solving DLOG in finite abelian groups, and we prove that bounded distance decoding for Reed--Solomon codes is NP-hard even at asymptotically zero rate, though the known NP-hard radius lies well above the Cheng--Wan decoding radius. We then carry out Regev's reduction on the Cheng--Wan instances and evaluate it with known efficient decoders. All fall short of the Cheng--Wan threshold by a constant factor, and under an assumption on the Cheng--Wan instances we identify the QDP parameter a decoder would need to reach in order to solve discrete logarithm. The obstruction is one of efficiency rather than solvability: the Pretty Good Measurement solves the corresponding decoding problem on every instance, including NP-hard instances, but its implementation requires exponential resources in general.
• Abstract（参考訳）: 有限フィールド上の離散対数問題(DLOG)のインスタンスをReed-Solomon符号の復号問題に変換するChengとWanの減算を再検討し、Regevの減算がこれらの問題を解くためにどのように使えるかを研究する。Regevの減算は、符号の復号問題を復号する量子ソルバに変換する。量子上の優位性は、古典的に難しい双対問題に依存するため、確立が困難である。Cheng-Wan減算は、そのようなインスタンスの自然な情報源を提供する。 Shorのアルゴリズムは離散対数はすでに解いているので、ゴールは新しい量子スピードアップではなく、Regevの減少が、私たちが信じている独立した理由を持つ問題に適用され、離散対数を解決することができ、もしそうでなければ、不足するであろう問題に適用されるかどうかを理解することである。 我々は、Reed-Solomonの有界距離復号 -- $\mathbb{F}_{q^h}^\times$でのDLOGの解から有限アーベル群でのDLOGの解に至るまでのCheng-Solomon境界距離復号の硬さを一般化し、Reed-Solomon符号の有界距離復号がNP-hardであることを証明する。 Cheng-Wan のしきい値のすべては定数係数で不足し、Cheng-Wan のインスタンス上で仮定すると、デコーダが離散対数問題を解決するために到達しなければならない QDP パラメータを特定できる。 Pretty Good MeasurementはNPハードインスタンスを含む全てのインスタンスで対応する復号問題を解くが、その実装は一般に指数的なリソースを必要とする。

関連論文リスト

• Distributed Quantum Discrete Logarithm Algorithm [6.582879593820295]
  本稿では,必要な量子レジスタサイズを削減する分散量子離散対数アルゴリズムを提案する。 具体的には,その解が与えられた集合に含まれるか否かを決定するために,分散量子アルゴリズムを設計する。 Shorのアルゴリズムと比較して、我々の手法はレジスタサイズを小さくし、量子通信を必要とせず、成功確率を向上させることができる。
  論文  参考訳（メタデータ） (2026-03-27T08:23:46Z)
• Exponential convergence dynamics in Grover's search algorithm [0.0]
  グロバーの探索アルゴリズムは、量子コンピューティングの多くの応用の基礎となっている。 我々はグロバーのアルゴリズムを修正して振動ダイナミクスを排除し、探索は解状態への指数的減衰として進行する。 基本的な考え方は、初期状態が非反射的に吸収されるようなアンシラ量子ビットを用いて、溶液状態を貯水池に変換することである。
  論文  参考訳（メタデータ） (2025-12-17T05:43:07Z)
• The Quantum Decoding Problem : Tight Achievability Bounds and Application to Regev's Reduction [6.140129238616484]
  我々は、$l_infty$ノルムに対するショート・ソリューション(SIS)問題に対する量子的優位性を示す。 最近の論文で、Chailloux と Tillich はベルヌーイ分布に従えば、量子復号問題はアルゴリズム時間で解くことができることを示した。
  論文  参考訳（メタデータ） (2025-09-29T13:48:05Z)
• Limitations of the decoding-to-LPN reduction via code smoothing [59.90381090395222]
  研究者は、ノイズ問題を伴う学習パリティのアルゴリズム的難しさを実証しようと試みている。 復号化問題とプリミティブ問題のパラメータの観点から,削減の効率を特徴付ける。
  論文  参考訳（メタデータ） (2024-08-07T12:54:43Z)
• A New Approach to Generic Lower Bounds: Classical/Quantum MDL, Quantum Factoring, and More [1.1893324664457547]
  本稿では,古典的および量子的設定における暗号問題の解法における汎用的アプローチの限界について検討する。 両方のモデルにおいて、両方のモデルの量子的下界は、ある種の古典的な前処理を可能にする。
  論文  参考訳（メタデータ） (2024-02-17T13:00:47Z)
• Complexity-Theoretic Limitations on Quantum Algorithms for Topological Data Analysis [59.545114016224254]
  トポロジカルデータ解析のための量子アルゴリズムは、古典的手法よりも指数関数的に有利である。 我々は、量子コンピュータにおいても、TDA(ベッチ数の推定)の中心的なタスクが難解であることを示します。 我々は、入力データが単純さの仕様として与えられると、指数的量子優位性を取り戻すことができると論じる。
  論文  参考訳（メタデータ） (2022-09-28T17:53:25Z)
• Quantum Goemans-Williamson Algorithm with the Hadamard Test and Approximate Amplitude Constraints [62.72309460291971]
  本稿では,n+1$ qubitsしか使用しないGoemans-Williamsonアルゴリズムの変分量子アルゴリズムを提案する。 補助量子ビット上で適切にパラメータ化されたユニタリ条件として目的行列を符号化することにより、効率的な最適化を実現する。 各種NPハード問題に対して,Goemans-Williamsonアルゴリズムの量子的効率的な実装を考案し,提案プロトコルの有効性を実証する。
  論文  参考訳（メタデータ） (2022-06-30T03:15:23Z)
• Finding the disjointness of stabilizer codes is NP-complete [77.34726150561087]
  我々は、$c-不連続性を計算すること、あるいはそれを定数乗算係数の範囲内で近似することの問題はNP完全であることを示す。 CSSコード、$dコード、ハイパーグラフコードなど、さまざまなコードファミリの相違点に関するバウンダリを提供します。 以上の結果から,一般的な量子誤り訂正符号に対するフォールトトレラント論理ゲートの発見は,計算に難題であることが示唆された。
  論文  参考訳（メタデータ） (2021-08-10T15:00:20Z)

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

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