論文の概要: Grover's oracle for the Shortest Vector Problem and its application in
hybrid classical-quantum solvers
- arxiv url: http://arxiv.org/abs/2402.13895v1
- Date: Wed, 21 Feb 2024 16:05:49 GMT
- ステータス: 処理完了
- システム内更新日: 2024-02-22 14:41:45.158027
- Title: Grover's oracle for the Shortest Vector Problem and its application in
hybrid classical-quantum solvers
- Title（参考訳）: 最短ベクトル問題に対するgroverのoracleとそのハイブリッド古典量子解法への応用
- Authors: Milos Prokop, Petros Wallden, David Joseph
- Abstract要約: 格子内の最短ベクトルを見つけることは、古典コンピュータと量子コンピュータの両方にとって困難であると考えられている問題である。
SVPのための最も優れた古典的、量子的、あるいはハイブリッドな古典量子アルゴリズムを見つけるためには、十分なセキュリティレベルを提供する暗号系パラメータを選択する必要がある。
グロバーの探索量子アルゴリズムは、一般的な二次的なスピードアップを提供する。
我々はGroverの小さなSVPインスタンスの量子探索と最先端の古典的解法を組み合わせる方法について分析する。
- 参考スコア（独自算出の注目度）: 0.38366697175402226
- License: http://creativecommons.org/licenses/by/4.0/
- Abstract: Finding the shortest vector in a lattice is a problem that is believed to be
hard both for classical and quantum computers. Many major post-quantum secure
cryptosystems base their security on the hardness of the Shortest Vector
Problem (SVP). Finding the best classical, quantum or hybrid classical-quantum
algorithms for SVP is necessary to select cryptosystem parameters that offer
sufficient level of security. Grover's search quantum algorithm provides a
generic quadratic speed-up, given access to an oracle implementing some
function which describes when a solution is found. In this paper we provide
concrete implementation of such an oracle for the SVP. We define the circuit,
and evaluate costs in terms of number of qubits, number of gates, depth and
T-quantum cost. We then analyze how to combine Grover's quantum search for
small SVP instances with state-of-the-art classical solvers that use well known
algorithms, such as the BKZ, where the former is used as a subroutine. This
could enable solving larger instances of SVP with higher probability than
classical state-of-the-art records, but still very far from posing any threat
to cryptosystems being considered for standardization. Depending on the
technology available, there is a spectrum of trade-offs in creating this
combination.
- Abstract（参考訳）: 格子内の最短ベクトルを見つけることは、古典的コンピュータと量子コンピュータの両方にとって難しい問題であると考えられている。
量子後セキュリティ暗号の多くは、最短ベクトル問題(SVP)の難しさに基づくセキュリティを基盤としている。
SVPのための古典的、量子的、あるいはハイブリッドな古典量子アルゴリズムを見つけるには、十分なセキュリティレベルを提供する暗号系パラメータを選択する必要がある。
グローバーの探索量子アルゴリズムは、解がいつ見つかるかを記述する関数を実装するオラクルへのアクセスを前提として、一般的な二次的なスピードアップを提供する。
本稿では,svp に対する oracle の具体的な実装について述べる。
回路を定義し、キュービット数、ゲート数、深さおよびT量子コストの観点からコストを評価する。
次に、Groverの小さなSVPインスタンスの量子探索と、BKZのようなよく知られたアルゴリズムを使った最先端の古典的解法を組み合わせる方法を分析する。
これにより、従来の最先端レコードよりも高い確率でSVPのより大きなインスタンスを解決できるが、標準化のために考慮されている暗号システムに対する脅威には程遠い。
利用可能な技術によっては、この組み合わせにはさまざまなトレードオフがある。
関連論文リスト
- On the practicality of quantum sieving algorithms for the shortest vector problem [42.70026220176376]
格子ベースの暗号は、量子後暗号の主要な候補の1つである。
量子攻撃に対する暗号セキュリティは、最短ベクトル問題(SVP)のような格子問題に基づいている
SVPを解くための漸近的な量子スピードアップはGroverの探索に依存している。
論文 参考訳（メタデータ） (2024-10-17T16:54:41Z) - Generalized Hybrid Search and Applications to Blockchain and Hash
Function Security [50.16790546184646]
まず,ハイブリッド量子古典戦略を用いて,様々な探索問題を解くことの難しさについて検討する。
次に、ハイブリッド量子古典探索アルゴリズムを構築し、その成功確率を解析する。
論文 参考訳（メタデータ） (2023-11-07T04:59:02Z) - Quantum Worst-Case to Average-Case Reductions for All Linear Problems [66.65497337069792]
量子アルゴリズムにおける最悪のケースと平均ケースの削減を設計する問題について検討する。
量子アルゴリズムの明示的で効率的な変換は、入力のごく一部でのみ正し、全ての入力で正しくなる。
論文 参考訳（メタデータ） (2022-12-06T22:01:49Z) - The NISQ Complexity of Collision Finding [2.9405711598281536]
現代の暗号における基本的なプリミティブである衝突耐性ハッシュは、同じハッシュ値を生成する入力を効率的に見つける方法がないことを保証している。
現在、量子敵はNISQのパワーを備えたフルスケールのコンピュータを必要とする。
本稿では, NISQアルゴリズムの3つの異なるモデルについて検討する。
論文 参考訳（メタデータ） (2022-11-23T13:55:28Z) - Quantum Depth in the Random Oracle Model [57.663890114335736]
浅量子回路の計算能力と古典計算の組合せを包括的に評価する。
いくつかの問題に対して、1つの浅い量子回路で適応的な測定を行う能力は、適応的な測定をせずに多くの浅い量子回路を実行する能力よりも有用である。
論文 参考訳（メタデータ） (2022-10-12T17:54:02Z) - 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) - A Variational Quantum Attack for AES-like Symmetric Cryptography [69.80357450216633]
古典的AES様対称暗号のための変分量子攻撃アルゴリズム(VQAA)を提案する。
VQAAでは、既知の暗号文は、正規グラフを通して構築されるハミルトンの基底状態として符号化される。
論文 参考訳（メタデータ） (2022-05-07T03:15:15Z) - Hardware Efficient Quantum Search Algorithm [17.74233101199813]
本稿では,この課題を克服するために,ハードウェアの効率的な量子探索アルゴリズムを提案する。
我々の鍵となる考え方は、グローバル拡散操作を低コストな局所拡散に置き換えることである。
回路コストの削減は、システムの成功率を著しく向上させる。
論文 参考訳（メタデータ） (2021-03-26T01:08:50Z) - 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) - Forging quantum data: classically defeating an IQP-based quantum test [0.0]
古典的)証明器が量子であることを検証者に納得させる古典的アルゴリズムについて述べる。
キー抽出アルゴリズムは,実際に数百量子ビットの問題を解くのに有効であることを示す。
論文 参考訳（メタデータ） (2019-12-11T19:00:00Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。