論文の概要: 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(参考訳): 格子は量子攻撃に対して安全な暗号プリミティブを構築するために非常に重要なオブジェクトである。
格子の研究における中心的な問題は、格子内の最も短い非零ベクトルを見つけることである。
漸近的に、シービングは最短ベクトル問題を解決する最もよく知られた技法であるが、シービングは格子の次元においてメモリ指数を必要とする。
その結果、列挙アルゴリズムは、超指数的ランタイムにもかかわらず、線形メモリの複雑さのために、しばしばシービングの代わりに使用される。
本研究では,シーブの初期段階におけるサンプルベクトル長の大きさのメモリ複雑性多項式を持つヒューリスティックな量子シービングアルゴリズムを提案する。
言い換えれば、ほとんどのシーブアルゴリズムとは異なり、我々のアルゴリズムのメモリ複雑性は、シーブの初期段階におけるサンプリングされたベクトルの数に依存しない。
関連論文リスト
- 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) - Complexity-Theoretic Limitations on Quantum Algorithms for Topological
Data Analysis [59.545114016224254]
トポロジカルデータ解析のための量子アルゴリズムは、古典的手法よりも指数関数的に有利である。
我々は、量子コンピュータにおいても、TDA(ベッチ数の推定)の中心的なタスクが難解であることを示します。
我々は、入力データが単純さの仕様として与えられると、指数的量子優位性を取り戻すことができると論じる。
論文 参考訳(メタデータ) (2022-09-28T17:53:25Z) - Entanglement and coherence in Bernstein-Vazirani algorithm [58.720142291102135]
Bernstein-Vaziraniアルゴリズムは、オラクルに符号化されたビット文字列を決定できる。
我々はベルンシュタイン・ヴァジラニアルゴリズムの量子資源を詳細に分析する。
絡み合いがない場合、初期状態における量子コヒーレンス量とアルゴリズムの性能が直接関係していることが示される。
論文 参考訳(メタデータ) (2022-05-26T20:32:36Z) - Variational quantum solutions to the Shortest Vector Problem [6.126929553818864]
最短ベクトル問題(SVP)は、最短ベクトル問題(SVP)として知られる問題である。
この問題は量子コンピュータでも難しいと考えられており、量子後暗号において重要な役割を担っている。
本研究では,(効率のよい)ノイズ中間量子(NISQ)デバイスを用いてSVPを解く方法について検討する。
論文 参考訳(メタデータ) (2022-02-14T14:27:38Z) - An efficient quantum algorithm for lattice problems achieving
subexponential approximation factor [2.3351527694849574]
整数格子のクラスに対する指数近似係数を用いて,境界距離復号法(BDD)問題を解く量子アルゴリズムを提案する。
量子アルゴリズムの実行時間は、近似因子の1つの範囲と、第2の範囲の近似因子のサブ指数時間である。
この見解は、有限アーベル群の観点からクリーンな量子アルゴリズムを定め、格子理論から相対的にほとんど使用せず、次元以外のパラメータの格子問題に対する近似アルゴリズムを探求することを提案している。
論文 参考訳(メタデータ) (2022-01-31T18:58:33Z) - Quantum-Inspired Algorithms from Randomized Numerical Linear Algebra [53.46106569419296]
我々は、リコメンダシステムと最小二乗回帰のためのクエリをサポートする古典的な(量子でない)動的データ構造を作成する。
これらの問題に対する以前の量子インスパイアされたアルゴリズムは、レバレッジやリッジレベレッジスコアを偽装してサンプリングしていると我々は主張する。
論文 参考訳(メタデータ) (2020-11-09T01:13:07Z) - Accelerated Message Passing for Entropy-Regularized MAP Inference [89.15658822319928]
離散値のランダムフィールドにおけるMAP推論の最大化は、機械学習の基本的な問題である。
この問題の難しさから、特殊メッセージパッシングアルゴリズムの導出には線形プログラミング(LP)緩和が一般的である。
古典的加速勾配の根底にある手法を活用することにより,これらのアルゴリズムを高速化するランダム化手法を提案する。
論文 参考訳(メタデータ) (2020-07-01T18:43:32Z) - Optimal Randomized First-Order Methods for Least-Squares Problems [56.05635751529922]
このアルゴリズムのクラスは、最小二乗問題に対する最も高速な解法のうち、いくつかのランダム化手法を含んでいる。
我々は2つの古典的埋め込み、すなわちガウス射影とアダマール変換のサブサンプリングに焦点を当てる。
得られたアルゴリズムは条件数に依存しない最小二乗問題の解法として最も複雑である。
論文 参考訳(メタデータ) (2020-02-21T17:45:32Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト(すべての情報・翻訳含む)の品質を保証せず、本サイト(すべての情報・翻訳含む)を使用して発生したあらゆる結果について一切の責任を負いません。