論文の概要: Quantum algorithm for Discrete Gaussian Sampling

• arxiv url: http://arxiv.org/abs/2605.20133v1
• Date: Tue, 19 May 2026 17:17:29 GMT
• ステータス: 翻訳完了
• システム内更新日: 2026-05-20 15:03:09.551591
• Title: Quantum algorithm for Discrete Gaussian Sampling
• Title（参考訳）: 離散ガウスサンプリングのための量子アルゴリズム
• Authors: Clémence Chevignard, Yixin Shen, André Schrottenloher,
• Abstract要約: 本稿では,量子リジェクションサンプリング法に基づく量子アルゴリズムについて述べる。 量子二重攻撃の2つのバージョンを導出し、以前の2つを改善した。 また, 短解問題の解法におけるアルゴリズムの高速化にも有効である。
• 参考スコア（独自算出の注目度）: 4.092694803833864
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: Discrete Gaussian Sampling on lattices is a fundamental problem in lattice-based cryptography. It appears both in basic cryptographic primitives such as digital signatures and as an important cryptanalysis building block for solving hard lattice problems. In this paper, we show a quantum algorithm based on the quantum rejection sampling technique whose complexity is asymptotically quadratically faster than its classical counterpart in [Wang & Ling, IEEE Trans. Inf. Theory 2019]. Our sampler outputs a quantum state which can either be measured to get the desired distribution or be used directly as such in other quantum algorithms. By doing so, we derive two versions of quantum dual attacks that improve upon the previous ones in [Pouly & Shen, EUROCRYPT 2024]. The two versions are incomparable, each having distinct advantages (speed vs memory requirement). The second version is particularly interesting as it requires only polynomial classical and quantum memory, excluding the classical memory used in the preprocessing step of the Discrete Gaussian sampler. Our quantum Discrete Gaussian sampler can also be used to speed up the algorithm for solving the Short Integer Solution problem, in any norm, of [Bollauf, Pouly & Shen, ePrint 2026/225].
• Abstract（参考訳）: 格子上での離散ガウスサンプリングは格子ベースの暗号における根本的な問題である。 デジタル署名のような基本的な暗号プリミティブと、ハード格子問題を解決するための重要な暗号解析ビルディングブロックの両方に現れる。 本稿では,量子リジェクションサンプリング法に基づく量子アルゴリズムについて述べる。その複雑性は,[Wang & Ling, IEEE Trans. Inf. Theory 2019]の古典的手法よりも漸近的に2次的に高速である。 我々のサンプルは、所望の分布を得るために測定できる量子状態を出力するか、他の量子アルゴリズムのように直接使用することができる。 これにより、[Pouly & Shen, EUROCRYPT 2024]の以前の2つの量子二重攻撃をより良くする2つのバージョンの量子二重攻撃を導出する。 2つのバージョンは互換性がなく、それぞれが異なる利点(スピードとメモリの要求)を持っている。 第2版は、離散ガウスサンプリング器の前処理ステップで使用される古典的メモリを除いて、多項式古典的メモリと量子的メモリのみを必要とするため、特に興味深い。 我々の量子離散型ガウスサンプリングは、[Bollauf, Pouly & Shen, ePrint 2026/225]の任意のノルムにおいて、ショート・インテガー・ソリューション問題を解決するアルゴリズムの高速化にも利用できる。

関連論文リスト

• Generalized Hybrid Search and Applications to Blockchain and Hash Function Security [50.16790546184646]
  まず,ハイブリッド量子古典戦略を用いて,様々な探索問題を解くことの難しさについて検討する。 次に、ハイブリッド量子古典探索アルゴリズムを構築し、その成功確率を解析する。
  論文  参考訳（メタデータ） (2023-11-07T04:59:02Z)
• A comment on "Factoring integers with sublinear resources on a superconducting quantum processor" [0.0]
  そこで我々はSchnorr's lattice-based integer factorizationアルゴリズムのオープンソース実装について述べる。 我々の実装は、シュノーラーの整数を70ビットまでしか持たないハイブリッド量子+古典版に対する主張された部分線型格子次元が示している。 我々は、我々の実装が、他のハイブリッド量子/古典的整数分解アルゴリズムのアイデアをテストするための、コミュニティの場として機能することを願っている。
  論文  参考訳（メタデータ） (2023-07-18T21:46:54Z)
• Quantum Worst-Case to Average-Case Reductions for All Linear Problems [66.65497337069792]
  量子アルゴリズムにおける最悪のケースと平均ケースの削減を設計する問題について検討する。 量子アルゴリズムの明示的で効率的な変換は、入力のごく一部でのみ正し、全ての入力で正しくなる。
  論文  参考訳（メタデータ） (2022-12-06T22:01:49Z)
• Quantum Speedup for Higher-Order Unconstrained Binary Optimization and MIMO Maximum Likelihood Detection [2.5272389610447856]
  実数値の高次非制約二項最適化問題をサポートする量子アルゴリズムを提案する。 提案アルゴリズムは,古典的領域におけるクエリの複雑さを低減し,量子領域における2次高速化を実現する。
  論文  参考訳（メタデータ） (2022-05-31T00:14:49Z)
• Entanglement and coherence in Bernstein-Vazirani algorithm [58.720142291102135]
  Bernstein-Vaziraniアルゴリズムは、オラクルに符号化されたビット文字列を決定できる。 我々はベルンシュタイン・ヴァジラニアルゴリズムの量子資源を詳細に分析する。 絡み合いがない場合、初期状態における量子コヒーレンス量とアルゴリズムの性能が直接関係していることが示される。
  論文  参考訳（メタデータ） (2022-05-26T20:32:36Z)
• Quantum algorithms for grid-based variational time evolution [36.136619420474766]
  本稿では,第1量子化における量子力学の実行のための変分量子アルゴリズムを提案する。 シミュレーションでは,従来観測されていた変動時間伝播手法の数値不安定性を示す。
  論文  参考訳（メタデータ） (2022-03-04T19:00:45Z)
• Automatic quantum circuit encoding of a given arbitrary quantum state [0.0]
  任意の量子状態を最適量子回路に符号化する量子古典ハイブリッドアルゴリズムを提案する。 提案アルゴリズムは、目的関数として、F = langle 0 vert hatmathcalCdagger vert Psi rangle$ の絶対値を用いる。 我々は、AQCEアルゴリズムによって生成された量子回路が、実際にノイズの多い実量子デバイス上で元の量子状態を合理的に表現できることを実験的に実証した。
  論文  参考訳（メタデータ） (2021-12-29T12:33:41Z)
• Depth-efficient proofs of quantumness [77.34726150561087]
  量子性の証明は、古典的検証器が信頼できない証明器の量子的利点を効率的に証明できる挑戦応答プロトコルの一種である。 本稿では、証明者が量子回路を一定深度でしか実行できない量子性構成の証明を2つ与える。
  論文  参考訳（メタデータ） (2021-07-05T17:45:41Z)
• 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)

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

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