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

• arxiv url: http://arxiv.org/abs/2602.19819v2
• Date: Mon, 02 Mar 2026 13:03:43 GMT
• ステータス: 翻訳完了
• システム内更新日: 2026-03-03 15:39:03.815722
• 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)
• Quantum Worst-Case to Average-Case Reductions for All Linear Problems [66.65497337069792]
  量子アルゴリズムにおける最悪のケースと平均ケースの削減を設計する問題について検討する。 量子アルゴリズムの明示的で効率的な変換は、入力のごく一部でのみ正し、全ての入力で正しくなる。
  論文  参考訳（メタデータ） (2022-12-06T22:01:49Z)
• Lattice-Based Methods Surpass Sum-of-Squares in Clustering [98.46302040220395]
  クラスタリングは教師なし学習における基本的なプリミティブである。 最近の研究は、低次手法のクラスに対する低い境界を確立している。 意外なことに、この特定のクラスタリングモデルのtextitdoesは、統計的-計算的ギャップを示さない。
  論文  参考訳（メタデータ） (2021-12-07T18:50:17Z)
• A Unifying Theory of Thompson Sampling for Continuous Risk-Averse Bandits [91.3755431537592]
  本稿では,多腕バンディット問題に対するリスク-逆トンプソンサンプリングアルゴリズムの解析を統一する。 大規模偏差理論における収縮原理を用いることで、連続リスク汎関数に対する新しい濃度境界が証明される。 リスク関数の幅広いクラスと「ニセ」関数が連続性条件を満たすことを示す。
  論文  参考訳（メタデータ） (2021-08-25T17:09:01Z)
• On the Cryptographic Hardness of Learning Single Periodic Neurons [42.86685497609574]
  ノイズの存在下での等方性ガウス分布より単一ニューロンを学習する際の暗号的難易度を簡易に低減することを示す。 提案アルゴリズムは勾配ベースや逆SQ-timeアルゴリズムではなく,LLL(Lenstra-LenstraLov'asz)格子に基づく。
  論文  参考訳（メタデータ） (2021-06-20T20:03:52Z)
• Adaptive Sampling for Best Policy Identification in Markov Decision Processes [79.4957965474334]
  本稿では,学習者が生成モデルにアクセスできる場合の,割引マルコフ決定(MDP)における最良の政治的識別の問題について検討する。 最先端アルゴリズムの利点を論じ、解説する。
  論文  参考訳（メタデータ） (2020-09-28T15:22:24Z)
• 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)

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

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