論文の概要: Maximizing the practical achievability of quantum annealing attacks on factorization-based cryptography

• arxiv url: http://arxiv.org/abs/2410.04956v1
• Date: Mon, 7 Oct 2024 11:55:23 GMT
• ステータス: 処理完了
• システム内更新日: 2024-11-02 01:07:35.192065
• Title: Maximizing the practical achievability of quantum annealing attacks on factorization-based cryptography
• Title（参考訳）: 分解型暗号における量子アニール攻撃の実用的達成可能性の最大化
• Authors: Olgierd Żołnierczyk,
• Abstract要約: 本研究は、整数分解問題と離散対数問題に基づくスキームの暗号解析のための量子的手法に焦点を当てる。 本稿では、量子計算と古典計算を組み合わせたアプローチを改善することにより、分解問題の最大の事例を現実的に解く方法を示す。
• 参考スコア（独自算出の注目度）: 0.0
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: This work focuses on quantum methods for cryptanalysis of schemes based on the integer factorization problem and the discrete logarithm problem. We demonstrate how to practically solve the largest instances of the factorization problem by improving an approach that combines quantum and classical computations, assuming the use of the best publicly available special-class quantum computer: the quantum annealer. We achieve new computational experiment results by solving the largest instance of the factorization problem ever announced as solved using quantum annealing, with a size of 29 bits. The core idea of the improved approach is to leverage known sub-exponential classical method to break the problem down into many smaller computations and perform the most critical ones on a quantum computer. This approach does not reduce the complexity class, but it assesses the pragmatic capabilities of an attacker. It also marks a step forward in the development of hybrid methods, which in practice may surpass classical methods in terms of efficiency sooner than purely quantum computations will.
• Abstract（参考訳）: 本研究は、整数分解問題と離散対数問題に基づくスキームの暗号解析のための量子的手法に焦点を当てる。 我々は、量子計算と古典計算を組み合わせたアプローチを改良し、最も一般に公開されている特殊級量子コンピュータである量子アニールを用いて、分解問題の最大の事例を現実的に解決する方法を実証する。 我々は、29ビットの量子アニールを用いて、これまでに発表された因子化問題の最大の事例を解くことで、新しい計算実験を行った。 改良されたアプローチの中核となる考え方は、既知のサブ指数古典的手法を利用して、問題を多くの小さな計算に分解し、量子コンピュータ上で最も重要な計算を実行することである。 このアプローチは複雑性クラスを減らすのではなく、攻撃者の実用能力を評価する。 これはまた、実際には純粋に量子計算よりも早く効率の点で古典的手法を超越するかもしれないハイブリッド手法の開発における一歩である。

関連論文リスト

• Efficient Learning for Linear Properties of Bounded-Gate Quantum Circuits [63.733312560668274]
  d可変RZゲートとG-dクリフォードゲートを含む量子回路を与えられた場合、学習者は純粋に古典的な推論を行い、その線形特性を効率的に予測できるだろうか? 我々は、d で線形にスケーリングするサンプルの複雑さが、小さな予測誤差を達成するのに十分であり、対応する計算の複雑さは d で指数関数的にスケールすることを証明する。 我々は,予測誤差と計算複雑性をトレードオフできるカーネルベースの学習モデルを考案し,多くの実践的な環境で指数関数からスケーリングへ移行した。
  論文  参考訳（メタデータ） (2024-08-22T08:21:28Z)
• Realistic Runtime Analysis for Quantum Simplex Computation [0.4407851469168588]
  重要な最適化問題の現実のインスタンスを解く際に,古典的ランタイム解析のための量子アナログを提案する。 現実的な問題サイズに対する現実的な量子的優位性は、現在の物理的な制限よりもかなり低い量子ゲート演算時間を必要とすることを示します。
  論文  参考訳（メタデータ） (2023-11-16T16:11:44Z)
• Quantum Annealing for Single Image Super-Resolution [86.69338893753886]
  単一画像超解像(SISR)問題を解くために,量子コンピューティングに基づくアルゴリズムを提案する。 提案したAQCアルゴリズムは、SISRの精度を維持しつつ、古典的なアナログよりも向上したスピードアップを実現する。
  論文  参考訳（メタデータ） (2023-04-18T11:57:15Z)
• An in-principle super-polynomial quantum advantage for approximating combinatorial optimization problems via computational learning theory [5.907281242647458]
  量子コンピュータは、最適化問題に対する近似解法において、古典的コンピュータよりも高次超多項式的優位性を有することを証明している。 量子アドバンテージのコアは、究極的にはShorの量子アルゴリズムからファクタリングのために借用されている。
  論文  参考訳（メタデータ） (2022-12-16T19:01:04Z)
• Quantum Clustering with k-Means: a Hybrid Approach [117.4705494502186]
  我々は3つのハイブリッド量子k-Meansアルゴリズムを設計、実装、評価する。 我々は距離の計算を高速化するために量子現象を利用する。 我々は、我々のハイブリッド量子k-平均アルゴリズムが古典的バージョンよりも効率的であることを示す。
  論文  参考訳（メタデータ） (2022-12-13T16:04:16Z)
• 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 mean value approximator for hard integer value problems [19.4417702222583]
  正確な予想よりも近似を用いることで、最適化を大幅に改善できることを示す。 効率的な古典的サンプリングアルゴリズムとともに、極小ゲート数を持つ量子アルゴリズムは、一般的な整数値問題の効率を向上させることができる。
  論文  参考訳（メタデータ） (2021-05-27T13:03:52Z)
• Electronic structure with direct diagonalization on a D-Wave quantum annealer [62.997667081978825]
  本研究は、D-Wave 2000Q量子アニール上の分子電子ハミルトニアン固有値-固有ベクトル問題を解くために、一般量子アニール固有解法(QAE)アルゴリズムを実装した。 そこで本研究では,D-Waveハードウェアを用いた各種分子系における基底および電子励起状態の取得について述べる。
  論文  参考訳（メタデータ） (2020-09-02T22:46:47Z)
• Quadratic Sieve Factorization Quantum Algorithm and its Simulation [16.296638292223843]
  我々は、"Quadratic Sieve"という2番目の高速な古典的分解アルゴリズムの量子変種を設計した。 我々は,高レベルプログラミング言語Mathematicaを用いた量子化二次シーブアルゴリズムのシミュレーションフレームワークを構築した。
  論文  参考訳（メタデータ） (2020-05-24T07:14:19Z)
• Towards quantum advantage via topological data analysis [0.0]
  ロイズ,ガーネロン,ザナルディのトポロジカルデータ解析のためのアルゴリズムの背後にある量子アルゴリズムについて検討する。 ランク推定や複雑なネットワーク解析などの問題に対して,多数の新しい量子アルゴリズムを提供する。
  論文  参考訳（メタデータ） (2020-05-06T06:31:24Z)

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

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