論文の概要: Improved Classical and Quantum Algorithms for the Shortest Vector Problem via Bounded Distance Decoding

• arxiv url: http://arxiv.org/abs/2002.07955v6
• Date: Sun, 17 Aug 2025 11:17:31 GMT
• ステータス: 情報取得中
• システム内更新日: 2025-08-20 14:25:10.300919
• Title: Improved Classical and Quantum Algorithms for the Shortest Vector Problem via Bounded Distance Decoding
• Title（参考訳）: 境界距離復号による最短ベクトル問題に対する古典的および量子的アルゴリズムの改良
• Authors: Divesh Aggarwal, Yanlin Chen, Rajendra Kumar, Yixin Shen,
• Abstract要約: 最短ベクトル問題(SVP)に対する証明可能な古典量子アルゴリズムの新しいアルゴリズムを提案する。 SVPの新しいアルゴリズムは、時間複雑性とメモリ要求の間のスムーズなトレードオフを提供する。 20.950n+o(n)$で動作し、20.5n+o(n)$クラシックメモリとポリ(n)量子ビットを必要とするSVPの量子アルゴリズム。
• 参考スコア（独自算出の注目度）: 4.5686700995634055
• License:
• Abstract: The most important computational problem on lattices is the Shortest Vector Problem (SVP). In this paper, we present new algorithms that improve the state-of-the-art for provable classical/quantum algorithms for SVP. We present the following results. $\bullet$ A new algorithm for SVP that provides a smooth tradeoff between time complexity and memory requirement. For any positive integer $4\leq q\leq \sqrt{n}$, our algorithm takes $q^{13n+o(n)}$ time and requires $poly(n)\cdot q^{16n/q^2}$ memory. This tradeoff which ranges from enumeration ($q=\sqrt{n}$) to sieving ($q$ constant), is a consequence of a new time-memory tradeoff for Discrete Gaussian sampling above the smoothing parameter. $\bullet$ A quantum algorithm for SVP that runs in time $2^{0.950n+o(n)}$ and requires $2^{0.5n+o(n)}$ classical memory and poly(n) qubits. In Quantum Random Access Memory (QRAM) model this algorithm takes only $2^{0.835n+o(n)}$ time and requires a QRAM of size $2^{0.293n+o(n)}$, poly(n) qubits and $2^{0.5n}$ classical space. This improves over the previously fastest classical (which is also the fastest quantum) algorithm due to [ADRS15] that has a time and space complexity $2^{n+o(n)}$. $\bullet$ A classical algorithm for SVP that runs in time $2^{1.669n+o(n)}$ time and $2^{0.5n+o(n)}$ space. This improves over an algorithm of [CCL18] that has the same space complexity. The time complexity of our classical and quantum algorithms are obtained using a known upper bound on a quantity related to the lattice kissing number which is $2^{0.402n}$. We conjecture that for most lattices this quantity is a $2^{o(n)}$. Assuming that this is the case, our classical algorithm runs in time $2^{1.292n+o(n)}$, our quantum algorithm runs in time $2^{0.750n+o(n)}$ and our quantum algorithm in QRAM model runs in time $2^{0.667n+o(n)}$.
• Abstract（参考訳）: 格子上の最も重要な計算問題は、最短ベクトル問題(SVP)である。 本稿では,SVPのための証明可能な古典/量子アルゴリズムの最先端性を改善する新しいアルゴリズムを提案する。 以下の結果を示す。 $\bullet$SVPの新しいアルゴリズムは、時間複雑性とメモリ要求の間のスムーズなトレードオフを提供する。 任意の正の整数 4\leq q\leq \sqrt{n}$ に対して、我々のアルゴリズムは$q^{13n+o(n)}$時間を必要とし、$poly(n)\cdot q^{16n/q^2}$メモリを必要とする。 このトレードオフは列挙 (q=\sqrt{n}$) から sieving (q$ constant) まで様々であるが、これは円滑化パラメータ上の離散ガウスサンプリングのための新しい時間メモリトレードオフの結果である。 $\bullet$ SVP の量子アルゴリズムは、時間 2^{0.950n+o(n)}$ で、古典的メモリとポリ(n)量子ビットを必要とする。 量子ランダムアクセスメモリ(QRAM)モデルでは、このアルゴリズムは2^{0.835n+o(n)} の時間しかかからず、2^{0.293n+o(n)$, poly(n) qubits と 2^{0.5n}$古典空間のQRAMを必要とする。 これは、時間と空間の複雑さが 2^{n+o(n)}$ である[ADRS15] のため、それまでの最速の古典的アルゴリズムよりも改善される。 $\bullet$ 2^{1.669n+o(n)}$時間と2^{0.5n+o(n)$空間で動作するSVPの古典的アルゴリズム。 これにより、[CCL18]と同じ空間の複雑さを持つアルゴリズムよりも改善される。 古典的および量子的アルゴリズムの時間複雑性は、格子キス数(22.402n}$)に関連する量の既知の上限を用いて得られる。 ほとんどの格子に対して、この量は 2^{o(n)}$ であると予想する。 この場合、我々の古典的アルゴリズムは時間2.1.292n+o(n)}$で、量子アルゴリズムは時間2.0.750n+o(n)$で、QRAMモデルの量子アルゴリズムは時間2.0.667n+o(n)$で動く。

関連論文リスト

• Sum-of-Squares inspired Quantum Metaheuristic for Polynomial Optimization with the Hadamard Test and Approximate Amplitude Constraints [76.53316706600717]
  最近提案された量子アルゴリズムarXiv:2206.14999は半定値プログラミング(SDP)に基づいている SDPにインスパイアされた量子アルゴリズムを2乗和に一般化する。 この結果から,本アルゴリズムは大きな問題に適応し,最もよく知られた古典学に近似することが示唆された。
  論文  参考訳（メタデータ） (2024-08-14T19:04:13Z)
• Quantum spectral method for gradient and Hessian estimation [4.193480001271463]
  勾配降下は連続最適化問題を解くための最も基本的なアルゴリズムの1つである。 本稿では、クエリの複雑さを$widetildeO (1/varepsilon)$とすることで、その勾配の$varepsilon$-approximationを返す量子アルゴリズムを提案する。 また、ニュートン法の量子アナログを改善することを目的としたヘッセン推定のための2つの量子アルゴリズムを提案する。
  論文  参考訳（メタデータ） (2024-07-04T11:03:48Z)
• 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 Speedups for Bayesian Network Structure Learning [12.02309220445177]
  ノードが$n$のネットワークの場合、最も高速な既知のアルゴリズムは、最悪の場合は$O(2nn2)$で実行され、20年で改善はない。 量子コンピューティングの最近の進歩に触発されて、ある定数$c$が2ドル以下であれば、時間$O(cn)$で量子アルゴリズムによって解けるかどうかを問う。
  論文  参考訳（メタデータ） (2023-05-31T09:15:28Z)
• Mind the gap: Achieving a super-Grover quantum speedup by jumping to the end [114.3957763744719]
  本稿では,数種類のバイナリ最適化問題に対して,厳密な実行保証を有する量子アルゴリズムを提案する。 このアルゴリズムは、$n$非依存定数$c$に対して、時間で$O*(2(0.5-c)n)$の最適解を求める。 また、$k$-spinモデルからのランダムなインスタンスの多数と、完全に満足あるいはわずかにフラストレーションされた$k$-CSP式に対して、文 (a) がそうであることを示す。
  論文  参考訳（メタデータ） (2022-12-03T02:45:23Z)
• Finding many Collisions via Reusable Quantum Walks [1.376408511310322]
  衝突発見は暗号解析におけるユビキタスな問題である。 本稿では,この問題に対するアルゴリズムを改良し,特に許容可能なパラメータの範囲を広げる。 応用として、最短ベクトル問題に対する量子シービングアルゴリズムを改善する。
  論文  参考訳（メタデータ） (2022-05-27T14:50:45Z)
• Quantum speedups for treewidth [0.06445605125467573]
  グラフのツリー幅の正確な値を計算するための3つの量子アルゴリズムを示す。 木幅に対する最も高速な古典的アルゴリズムは時間と空間でO (1.755n) である。 O*(2n)$時間と$O*(sqrt2n)$空間でツリー幅を計算するための古典的な時間空間のトレードオフも与えている。
  論文  参考訳（メタデータ） (2022-02-16T16:47:47Z)

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

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