論文の概要: Quantum Lattice Sieving

• arxiv url: http://arxiv.org/abs/2110.13352v2
• Date: Thu, 1 Sep 2022 19:14:28 GMT
• ステータス: 処理完了
• システム内更新日: 2023-03-10 05:50:24.151863
• Title: Quantum Lattice Sieving
• Title（参考訳）: 量子格子シービング
• Authors: Nishant Rodrigues, Brad Lackey
• Abstract要約: 格子の研究における中心的な問題は、格子の中で最短の非ゼロベクトルを見つけることである。 本稿では, サンプルベクトル長のメモリ複雑性を主成分とする量子シービングアルゴリズムを提案する。
• 参考スコア（独自算出の注目度）: 0.0
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: Lattices are very important objects in the effort to construct cryptographic primitives that are secure against quantum attacks. A central problem in the study of lattices is that of finding the shortest non-zero vector in the lattice. Asymptotically, sieving is the best known technique for solving the shortest vector problem, however, sieving requires memory exponential in the dimension of the lattice. As a consequence, enumeration algorithms are often used in place of sieving due to their linear memory complexity, despite their super-exponential runtime. In this work, we present a heuristic quantum sieving algorithm that has memory complexity polynomial in the size of the length of the sampled vectors at the initial step of the sieve. In other words, unlike most sieving algorithms, the memory complexity of our algorithm does not depend on the number of sampled vectors at the initial step of the sieve.
• Abstract（参考訳）: 格子は量子攻撃に対して安全な暗号プリミティブを構築するために非常に重要なオブジェクトである。 格子の研究における中心的な問題は、格子内の最も短い非零ベクトルを見つけることである。 漸近的に、シービングは最短ベクトル問題を解決する最もよく知られた技法であるが、シービングは格子の次元においてメモリ指数を必要とする。 その結果、列挙アルゴリズムは、超指数的ランタイムにもかかわらず、線形メモリの複雑さのために、しばしばシービングの代わりに使用される。 本研究では,シーブの初期段階におけるサンプルベクトル長の大きさのメモリ複雑性多項式を持つヒューリスティックな量子シービングアルゴリズムを提案する。 言い換えれば、ほとんどのシーブアルゴリズムとは異なり、我々のアルゴリズムのメモリ複雑性は、シーブの初期段階におけるサンプリングされたベクトルの数に依存しない。

関連論文リスト

• Space-Efficient Quantum Error Reduction without log Factors [50.10645865330582]
  本稿では,多数決のランダムウォーク解釈に類似したライン上の重み付けウォークとして理解可能な,新たに単純化された浄化器の構成を提案する。 我々の浄化器は、前者よりも指数関数的に空間の複雑さが良く、精製されるアルゴリズムの音質-完全性ギャップに四分法的に依存している。
  論文  参考訳（メタデータ） (2025-02-13T12:04:39Z)
• 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)
• Tensor Decompositions and Adiabatic Quantum Computing for Discovering Practical Matrix Multiplication Algorithms [1.5540058359482858]
  本稿では,実用的な行列乗算アルゴリズムの発見と,量子コンピュータ上での分解計算のための2つのアルゴリズムの開発に焦点をあてる。 アルゴリズムは高次非制約バイナリ最適化(HUBO)問題として表現される。 最大分解長よりも短い長さを固定することにより、全体最適化問題の解がより高速な行列乗算アルゴリズムが得られることを示す。
  論文  参考訳（メタデータ） (2024-06-19T10:05:57Z)
• Tensor networks based quantum optimization algorithm [0.0]
  最適化において、よく知られた古典的アルゴリズムの1つは電力反復である。 我々はこの落とし穴を回避するために量子化を提案する。 我々の手法はインスタンス非依存となり、量子コンピューティングの枠組みの中でブラックボックス最適化に対処することができる。
  論文  参考訳（メタデータ） (2024-04-23T13:49:11Z)
• A simple quantum algorithm to efficiently prepare sparse states [0.0]
  ゲートの複雑性は状態の非零振幅数において線形であり、キュービット数では2次であることを示す。 これは、スパース状態の準備のための最もよく知られたアルゴリズムと競合する。
  論文  参考訳（メタデータ） (2023-10-30T07:05:15Z)
• Quantum speedup of leverage score sampling and its application [0.0]
  本稿では,レバレッジスコアの計算を高速化する量子アルゴリズムを提案する。 応用として,ベクトル解出力を用いた剛性回帰問題に対する新しい量子アルゴリズムを提案する。
  論文  参考訳（メタデータ） (2023-01-15T14:40:18Z)
• Cumulative Memory Lower Bounds for Randomized and Quantum Computation [1.52292571922932]
  累積記憶は時間空間の複雑さの尺度である。 逐次古典計算と量子回路の両方において、累積メモリの複雑さに関する最初の下位境界を証明した。
  論文  参考訳（メタデータ） (2023-01-13T17:57:02Z)
• Quantum Worst-Case to Average-Case Reductions for All Linear Problems [66.65497337069792]
  量子アルゴリズムにおける最悪のケースと平均ケースの削減を設計する問題について検討する。 量子アルゴリズムの明示的で効率的な変換は、入力のごく一部でのみ正し、全ての入力で正しくなる。
  論文  参考訳（メタデータ） (2022-12-06T22:01:49Z)
• Entanglement and coherence in Bernstein-Vazirani algorithm [58.720142291102135]
  Bernstein-Vaziraniアルゴリズムは、オラクルに符号化されたビット文字列を決定できる。 我々はベルンシュタイン・ヴァジラニアルゴリズムの量子資源を詳細に分析する。 絡み合いがない場合、初期状態における量子コヒーレンス量とアルゴリズムの性能が直接関係していることが示される。
  論文  参考訳（メタデータ） (2022-05-26T20:32:36Z)
• Quantum-Inspired Algorithms from Randomized Numerical Linear Algebra [53.46106569419296]
  我々は、リコメンダシステムと最小二乗回帰のためのクエリをサポートする古典的な(量子でない)動的データ構造を作成する。 これらの問題に対する以前の量子インスパイアされたアルゴリズムは、レバレッジやリッジレベレッジスコアを偽装してサンプリングしていると我々は主張する。
  論文  参考訳（メタデータ） (2020-11-09T01:13:07Z)
• Optimal Randomized First-Order Methods for Least-Squares Problems [56.05635751529922]
  このアルゴリズムのクラスは、最小二乗問題に対する最も高速な解法のうち、いくつかのランダム化手法を含んでいる。 我々は2つの古典的埋め込み、すなわちガウス射影とアダマール変換のサブサンプリングに焦点を当てる。 得られたアルゴリズムは条件数に依存しない最小二乗問題の解法として最も複雑である。
  論文  参考訳（メタデータ） (2020-02-21T17:45:32Z)

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

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