論文の概要: Pitfalls of the sublinear QAOA-based factorization algorithm

• arxiv url: http://arxiv.org/abs/2303.04656v2
• Date: Wed, 10 May 2023 11:58:11 GMT
• ステータス: 処理完了
• システム内更新日: 2023-05-11 16:40:55.115310
• Title: Pitfalls of the sublinear QAOA-based factorization algorithm
• Title（参考訳）: 線形QAOAに基づく分解アルゴリズムの落とし穴
• Authors: S.V. Grebnev, M.A. Gavreev, E.O. Kiktenko, A.P. Guglya, K.V. Kuchkin, A.R. Efimov, A.K. Fedorov
• Abstract要約: 量子コンピューティングデバイスは素因数分解問題を解くのに強力であると考えられている。 Shorの量子分解アルゴリズムの実装には、数の大きさと線形にスケールする重要なリソースが必要である。 Yanらによる最近の提案は、部分線型量子資源による分解問題を解く可能性を主張している。
• 参考スコア（独自算出の注目度）: 0.0
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: Quantum computing devices are believed to be powerful in solving the prime factorization problem, which is at the heart of widely deployed public-key cryptographic tools. However, the implementation of Shor's quantum factorization algorithm requires significant resources scaling linearly with the number size; taking into account an overhead that is required for quantum error correction the estimation is that 20 millions of (noisy) physical qubits are required for factoring 2048-bit RSA key in 8 hours. Recent proposal by Yan et. al. claims a possibility of solving the factorization problem with sublinear quantum resources. As we demonstrate in our work, this proposal lacks systematic analysis of the computational complexity of the classical part of the algorithm, which exploits the Schnorr's lattice-based approach. We provide several examples illustrating the need in additional resource analysis for the proposed quantum factorization algorithm.
• Abstract（参考訳）: 量子コンピューティングデバイスは、広く普及している公開鍵暗号ツールの中心である素因数分解問題を解決する上で強力であると考えられている。 しかし、Shorの量子因数分解アルゴリズムの実装には、数値サイズと線形にスケールする重要なリソースが必要であり、量子エラー補正に必要なオーバーヘッドを考慮すると、2048ビットのRSA鍵を8時間で分解するには2000万の物理量子ビットが必要である。 yanらによる最近の提案 al.は、部分線形量子資源を用いて因子分解問題を解決する可能性を主張する。 我々の研究で示すように、この提案はシュノーラーの格子に基づくアプローチを利用するアルゴリズムの古典的な部分の計算複雑性の体系的な解析を欠いている。 提案する量子分解アルゴリズムに対する追加資源分析の必要性を示すいくつかの例を示す。

関連論文リスト

• Maximizing the practical achievability of quantum annealing attacks on factorization-based cryptography [0.0]
  本研究は、整数分解問題と離散対数問題に基づくスキームの暗号解析のための量子的手法に焦点を当てる。 本稿では、量子計算と古典計算を組み合わせたアプローチを改善することにより、分解問題の最大の事例を現実的に解く方法を示す。
  論文  参考訳（メタデータ） (2024-10-07T11:55:23Z)
• Efficient Learning for Linear Properties of Bounded-Gate Quantum Circuits [63.733312560668274]
  d可変RZゲートとG-dクリフォードゲートを含む量子回路を与えられた場合、学習者は純粋に古典的な推論を行い、その線形特性を効率的に予測できるだろうか? 我々は、d で線形にスケーリングするサンプルの複雑さが、小さな予測誤差を達成するのに十分であり、対応する計算の複雑さは d で指数関数的にスケールすることを証明する。 我々は,予測誤差と計算複雑性をトレードオフできるカーネルベースの学習モデルを考案し,多くの実践的な環境で指数関数からスケーリングへ移行した。
  論文  参考訳（メタデータ） (2024-08-22T08:21:28Z)
• Generative AI-enabled Quantum Computing Networks and Intelligent Resource Allocation [80.78352800340032]
  量子コンピューティングネットワークは、大規模な生成AI計算タスクと高度な量子アルゴリズムを実行する。 量子コンピューティングネットワークにおける効率的なリソース割り当ては、量子ビットの可変性とネットワークの複雑さのために重要な課題である。 我々は、生成学習から量子機械学習まで、最先端強化学習(RL)アルゴリズムを導入し、最適な量子リソース割り当てを行う。
  論文  参考訳（メタデータ） (2024-01-13T17:16:38Z)
• A comment on "Factoring integers with sublinear resources on a superconducting quantum processor" [0.0]
  そこで我々はSchnorr's lattice-based integer factorizationアルゴリズムのオープンソース実装について述べる。 我々の実装は、シュノーラーの整数を70ビットまでしか持たないハイブリッド量子+古典版に対する主張された部分線型格子次元が示している。 我々は、我々の実装が、他のハイブリッド量子/古典的整数分解アルゴリズムのアイデアをテストするための、コミュニティの場として機能することを願っている。
  論文  参考訳（メタデータ） (2023-07-18T21:46:54Z)
• Quantum Annealing for Single Image Super-Resolution [86.69338893753886]
  単一画像超解像(SISR)問題を解くために,量子コンピューティングに基づくアルゴリズムを提案する。 提案したAQCアルゴリズムは、SISRの精度を維持しつつ、古典的なアナログよりも向上したスピードアップを実現する。
  論文  参考訳（メタデータ） (2023-04-18T11:57:15Z)
• Factoring integers with sublinear resources on a superconducting quantum processor [11.96383198580683]
  Shorのアルゴリズムは、公開鍵暗号システムに基づく情報セキュリティに深刻な挑戦をしている。 広く使われているRSA-2048スキームを破るためには、数百万の物理量子ビットが必要である。 本稿では,古典的格子削減法と量子近似最適化アルゴリズムを組み合わせることで,整数分解のための普遍量子アルゴリズムについて報告する。
  論文  参考訳（メタデータ） (2022-12-23T14:45:02Z)
• Quantum Worst-Case to Average-Case Reductions for All Linear Problems [66.65497337069792]
  量子アルゴリズムにおける最悪のケースと平均ケースの削減を設計する問題について検討する。 量子アルゴリズムの明示的で効率的な変換は、入力のごく一部でのみ正し、全ての入力で正しくなる。
  論文  参考訳（メタデータ） (2022-12-06T22:01:49Z)
• End-to-end resource analysis for quantum interior point methods and portfolio optimization [63.4863637315163]
  問題入力から問題出力までの完全な量子回路レベルのアルゴリズム記述を提供する。 アルゴリズムの実行に必要な論理量子ビットの数と非クリフォードTゲートの量/深さを報告する。
  論文  参考訳（メタデータ） (2022-11-22T18:54:48Z)
• Polynomial T-depth Quantum Solvability of Noisy Binary Linear Problem: From Quantum-Sample Preparation to Main Computation [0.0]
  雑音二元線形問題(NBLP)の量子可解性について完全解析する。 NBLPの解くコストは、指数関数的に増大する論理量子ビットを犠牲にして、問題の規模で解決できることが示される。
  論文  参考訳（メタデータ） (2021-09-23T07:46:20Z)
• Space-efficient binary optimization for variational computing [68.8204255655161]
  本研究では,トラベリングセールスマン問題に必要なキュービット数を大幅に削減できることを示す。 また、量子ビット効率と回路深さ効率のモデルを円滑に補間する符号化方式を提案する。
  論文  参考訳（メタデータ） (2020-09-15T18:17:27Z)

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

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