論文の概要: Quantum approaches to learning parity with noise

• arxiv url: http://arxiv.org/abs/2602.19819v1
• Date: Mon, 23 Feb 2026 13:20:24 GMT
• ステータス: 翻訳完了
• システム内更新日: 2026-02-24 17:42:02.825093
• Title: Quantum approaches to learning parity with noise
• Title（参考訳）: 雑音によるパリティ学習への量子的アプローチ
• Authors: Daniel Shiu,
• Abstract要約: ノイズ問題に対するパリティに対して,量子的手法が代替的なアプローチを提供するかどうかを考察する。 Simonのアルゴリズムを実行すると、基本的に新しい学習サンプルが生成される。 これにより、1つ以上の変数を無視し、問題を反復的に減らすのに十分な新しいサンプルを作成できるのではないか、という期待が得られます。
• 参考スコア（独自算出の注目度）: 0.0
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: The learning parity with noise (LPN) problem is a well-established computational challenge whose difficulty is critical to the security of several post-quantum cryptographic primitives such as HQC and Classic McEliece. Classically, the best-known attacks involve information set decoding methods which are exponential in complexity for parameterisations of interest. In this paper we investigate whether quantum methods might offer alternative approaches. The line of inquiry is inspired by Regev's relating of certain lattice problems to the hidden dihedral subgroup problem. We use neighbourhoods of binary fields to produce a function close to fulfilling Simon's promise with difference equal to the secret parity vector. Although unlikely to recover the secret parity vector directly, running Simon's algorithm essentially produces new LPN samples. This gives the hope that we might be able to produce enough new samples to ignore one or more variables and iteratively reduce the problem. We make no claim that these methods will necessarily be competitive with existing approaches, merely that they warrant deeper investigation.
• Abstract（参考訳）: LPN問題(Learning parity with noise)は、HQCやClassic McElieceのようなポスト量子暗号プリミティブのセキュリティにとって、難易度が重要な、確立された計算課題である。 古典的には、最もよく知られている攻撃は、関心のパラメータ化の複雑さが指数関数的な情報集合復号法である。 本稿では,量子法が代替手法を提供するかどうかを考察する。 調査の行は、ある格子問題と隠れた二面体部分群問題との関連性から着想を得ている。 我々は二項体の近傍を使って、シークレットパリティベクトルに等しい差でサイモンの約束を満たすような函数を生成する。 シークレットパリティベクトルを直接回収する可能性は低いが、サイモンのアルゴリズムを実行すると、本質的に新しいLPNサンプルが生成される。 これにより、1つ以上の変数を無視し、問題を反復的に減らすのに十分な新しいサンプルを作成できるのではないか、という期待が得られます。 これらの手法が既存のアプローチと必ずしも競合すると主張してはいない。

関連論文リスト

• The Learning Stabilizers with Noise problem [46.623273455512106]
  雑音のある学習パリティ(Learning Parity with Noise, LPN)問題は、雑音の存在下でランダムな線形コードを復号するタスクとみなすことができる。 LSNは特殊なケースとして含まれており、これは古典的なケースと同程度に難しいことを示唆している。 我々は、量子ビットスキームの構築から量子データからの学習の計算限界まで、LSN仮定のいくつかの応用を同定する。
  論文  参考訳（メタデータ） (2024-10-24T17:53:02Z)
• Quantum One-Wayness of the Single-Round Sponge with Invertible Permutations [49.1574468325115]
  スポンジハッシュは、広く使われている暗号ハッシュアルゴリズムのクラスである。 これまでのところ、不規則な置換は根本的なオープンな問題のままである。 ランダムな2n$-bit置換でゼロペアを見つけるには、少なくとも$Omega(2n/2)$多くのクエリが必要である。
  論文  参考訳（メタデータ） (2024-03-07T18:46:58Z)
• Making the cut: two methods for breaking down a quantum algorithm [0.0]
  現在、ノイズの多い小規模量子ハードウェアの時代において、計算上の優位性に達する可能性のある量子アルゴリズムを見つけることは、依然として大きな課題である。 我々は、量子アルゴリズムを低い(クエリ)深さのラウンドに分解する2つの方法を特定し、特徴付ける。 最初の問題では並列化が最高のパフォーマンスを提供するのに対し、2番目はより良い選択であることを示す。
  論文  参考訳（メタデータ） (2023-05-17T18:00:06Z)
• Scalable noisy quantum circuits for biased-noise qubits [37.69303106863453]
  安定猫量子ビットの既存システムに動機づけられたビットフリップ誤差のみに影響されるバイアスノイズ量子ビットを考察する。 現実的なノイズモデルでは、位相フリップは無視できないが、Pauli-Twirling近似では、ベンチマークが最大106ドルのゲートを含む回路の正しさを確認できる。
  論文  参考訳（メタデータ） (2023-05-03T11:27:50Z)
• Agnostic Multi-Robust Learning Using ERM [19.313739782029185]
  頑健な学習における根本的な問題は非対称性である: 学習者は指数関数的に多くの摂動の全てを正しく分類する必要がある。 これとは対照的に、攻撃者は1つの摂動を成功させる必要がある。 本稿では,新しいマルチグループ設定を導入し,新しいマルチロバスト学習問題を提案する。
  論文  参考訳（メタデータ） (2023-03-15T21:30:14Z)
• Lattice-Based Methods Surpass Sum-of-Squares in Clustering [98.46302040220395]
  クラスタリングは教師なし学習における基本的なプリミティブである。 最近の研究は、低次手法のクラスに対する低い境界を確立している。 意外なことに、この特定のクラスタリングモデルのtextitdoesは、統計的-計算的ギャップを示さない。
  論文  参考訳（メタデータ） (2021-12-07T18:50:17Z)
• Quantum Attacks without Superposition Queries: the Offline Simon's Algorithm [7.819565615098435]
  我々はサイモンのサブルーチンを新しい方法で利用する新しい量子アルゴリズムを導入する。 現状の文献に関して量子時間/古典データのトレードオフを改善した。 我々はデータの複雑さを減らし、過去の重ね合わせ攻撃を改善した。
  論文  参考訳（メタデータ） (2020-02-27T21:05:54Z)
• The Simulator: Understanding Adaptive Sampling in the Moderate-Confidence Regime [52.38455827779212]
  エミュレータと呼ばれる適応サンプリングを解析するための新しい手法を提案する。 適切なログファクタを組み込んだトップk問題の最初のインスタンスベースの下位境界を証明します。 我々の新しい分析は、後者の問題に対するこの種の最初のエミュレータであるベストアームとトップkの識別に、シンプルでほぼ最適であることを示した。
  論文  参考訳（メタデータ） (2017-02-16T23:42:02Z)

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

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