論文の概要: An Improved Quantum Algorithm for 3-Tuple Lattice Sieving

• arxiv url: http://arxiv.org/abs/2510.08473v1
• Date: Thu, 09 Oct 2025 17:13:07 GMT
• ステータス: 翻訳完了
• システム内更新日: 2025-10-10 17:54:15.23592
• Title: An Improved Quantum Algorithm for 3-Tuple Lattice Sieving
• Title（参考訳）: 3管格子シービングのための量子アルゴリズムの改良
• Authors: Lynn Engelberts, Yanlin Chen, Amin Shiraz Gilani, Maya-Iggy van Hoof, Stacey Jeffery, Ronald de Wolf,
• Abstract要約: 最短ベクトル問題はポスト量子暗号の基盤の1つである。 SVPに対する最も高速な攻撃はいわゆる Sieving メソッドである。 本稿では,3タプルシービングの量子時間複雑性を20.3098d$から20.2846d$に改善する。
• 参考スコア（独自算出の注目度）: 1.5327973773729056
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: The assumed hardness of the Shortest Vector Problem in high-dimensional lattices is one of the cornerstones of post-quantum cryptography. The fastest known heuristic attacks on SVP are via so-called sieving methods. While these still take exponential time in the dimension $d$, they are significantly faster than non-heuristic approaches and their heuristic assumptions are verified by extensive experiments. $k$-Tuple sieving is an iterative method where each iteration takes as input a large number of lattice vectors of a certain norm, and produces an equal number of lattice vectors of slightly smaller norm, by taking sums and differences of $k$ of the input vectors. Iterating these ''sieving steps'' sufficiently many times produces a short lattice vector. The fastest attacks (both classical and quantum) are for $k=2$, but taking larger $k$ reduces the amount of memory required for the attack. In this paper we improve the quantum time complexity of 3-tuple sieving from $2^{0.3098 d}$ to $2^{0.2846 d}$, using a two-level amplitude amplification aided by a preprocessing step that associates the given lattice vectors with nearby ''center points'' to focus the search on the neighborhoods of these center points. Our algorithm uses $2^{0.1887d}$ classical bits and QCRAM bits, and $2^{o(d)}$ qubits. This is the fastest known quantum algorithm for SVP when total memory is limited to $2^{0.1887d}$.
• Abstract（参考訳）: 高次元格子における最短ベクトル問題の仮定困難さは、ポスト量子暗号の基盤の1つである。 SVPに対する最も早く知られているヒューリスティックな攻撃は、いわゆる Sieving 手法である。 これらは次元$d$で指数時間を要するが、非ヒューリスティックなアプローチよりもはるかに高速であり、そのヒューリスティックな仮定は広範な実験によって検証される。 $k$-Tuple sieving は反復的な方法であり、各反復は特定のノルムの多くの格子ベクトルを入力として取り、入力ベクトルの$k$の和と差を取ることにより、わずかに小さいノルムの格子ベクトルの等しい数を生成する。 これらの 'sieving steps' を十分に何度も繰り返すと、短い格子ベクトルが生成される。 最も高速な攻撃(古典的攻撃と量子的攻撃の両方)は$k=2$だが、より大きい$kは攻撃に必要なメモリ量を減らす。 本稿では、与えられた格子ベクトルを「中心点」に関連付け、これらの中心点近傍の探索に焦点を合わせる前処理ステップによって支援された2段階の振幅増幅を用いて、3タプルシービングの量子時間複雑性を2^{0.3098 d}$から2^{0.2846 d}$に改善する。 提案アルゴリズムでは,古典ビットとQCRAMビット,および2^{o(d)}$ qubitsを用いる。 これは、総メモリが$2^{0.1887d}$に制限されているとき、SVPにとって最も早く知られている量子アルゴリズムである。

関連論文リスト

• Space-Efficient Quantum Error Reduction without log Factors [50.10645865330582]
  本稿では,多数決のランダムウォーク解釈に類似したライン上の重み付けウォークとして理解可能な,新たに単純化された浄化器の構成を提案する。 我々の浄化器は、前者よりも指数関数的に空間の複雑さが良く、精製されるアルゴリズムの音質-完全性ギャップに四分法的に依存している。
  論文  参考訳（メタデータ） (2025-02-13T12:04:39Z)
• 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 Hopcroft's problem [45.45456673484445]
  計算幾何学の基本的な問題であるホップクロフト問題に対する量子アルゴリズムについて検討する。 この問題の古典的な複雑さはよく研究されており、最もよく知られているアルゴリズムは$O(n4/3)の時間で動作する。 我々の結果は、時間複雑性が$widetilde O(n5/6)$の2つの異なる量子アルゴリズムである。
  論文  参考訳（メタデータ） (2024-05-02T10:29:06Z)
• Do you know what q-means? [42.96240569413475]
  古典的な$varepsilon$-$k$-meansアルゴリズムは、ロイドのアルゴリズムの1つの反復の近似バージョンを時間的複雑さで実行する。 また,時間的複雑さを考慮した$q$-means量子アルゴリズムも提案する。
  論文  参考訳（メタデータ） (2023-08-18T17:52:12Z)
• Quantum Lattice Sieving [0.0]
  格子の研究における中心的な問題は、格子の中で最短の非ゼロベクトルを見つけることである。 本稿では, サンプルベクトル長のメモリ複雑性を主成分とする量子シービングアルゴリズムを提案する。
  論文  参考訳（メタデータ） (2021-10-26T01:50:48Z)
• Lattice sieving via quantum random walks [0.0]
  格子ベースの暗号は、量子後暗号の主要な提案の一つである。 最短ベクトル問題(SVP)は、格子ベースの暗号の暗号解析において最も重要な問題である。 我々は、$d$が格子次元であるような20.2570 d + o(d)$のランニング時間を持つアルゴリズムを提案する。
  論文  参考訳（メタデータ） (2021-05-12T11:59:30Z)
• 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)
• Improved Classical and Quantum Algorithms for the Shortest Vector Problem via Bounded Distance Decoding [4.5686700995634055]
  最短ベクトル問題(SVP)に対する証明可能な古典量子アルゴリズムの新しいアルゴリズムを提案する。 SVPの新しいアルゴリズムは、時間複雑性とメモリ要求の間のスムーズなトレードオフを提供する。 20.950n+o(n)$で動作し、20.5n+o(n)$クラシックメモリとポリ(n)量子ビットを必要とするSVPの量子アルゴリズム。
  論文  参考訳（メタデータ） (2020-02-19T01:38:34Z)

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

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