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

• arxiv url: http://arxiv.org/abs/2303.04656v6
• Date: Thu, 14 Dec 2023 10:23:38 GMT
• ステータス: 処理完了
• システム内更新日: 2023-12-16 05:05:59.265298
• Title: Pitfalls of the sublinear QAOA-based factorization algorithm
• Title（参考訳）: 線形QAOAに基づく分解アルゴリズムの落とし穴
• Authors: Sergey V. Grebnev, Maxim A. Gavreev, Evgeniy O. Kiktenko, Anton P. Guglya, Albert R. Efimov, Aleksey K. Fedorov
• Abstract要約: 主要な分解問題は、広くデプロイされた公開鍵暗号ツールの中心にある。 Shorの量子分解アルゴリズムの実装には、数の大きさと線形にスケールする重要なリソースが必要である。 Yanらによる最近の提案は、部分線型量子資源による分解問題を解く可能性を主張している。
• 参考スコア（独自算出の注目度）: 0.8987776881291144
• 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らによる最近の提案は、線形量子資源による分解問題を解く可能性を主張している。 我々の研究で示すように、この提案はシュノーラーの格子に基づくアプローチを利用するアルゴリズムの古典的な部分の計算複雑性の体系的な解析を欠いている。 提案する量子分解アルゴリズムに対する追加資源分析の必要性を示すいくつかの例を示す。

関連論文リスト

• Quantum Subroutine for Variance Estimation: Algorithmic Design and Applications [80.04533958880862]
  量子コンピューティングは、アルゴリズムを設計する新しい方法の基礎となる。 どの場の量子スピードアップが達成できるかという新たな課題が生じる。 量子サブルーチンの設計は、従来のサブルーチンよりも効率的で、新しい強力な量子アルゴリズムに固い柱を向ける。
  論文  参考訳（メタデータ） (2024-02-26T09:32:07Z)
• 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)
• Resource-efficient encoding algorithm for variational bosonic quantum simulations [0.0]
  量子コンピューティングのノイズ中間スケール量子(NISQ)時代には、量子資源は限られている。 ボゾン基底と励起状態計算のための資源効率のよい量子アルゴリズムを提案する。
  論文  参考訳（メタデータ） (2021-02-23T19:00:05Z)
• Space-efficient binary optimization for variational computing [68.8204255655161]
  本研究では,トラベリングセールスマン問題に必要なキュービット数を大幅に削減できることを示す。 また、量子ビット効率と回路深さ効率のモデルを円滑に補間する符号化方式を提案する。
  論文  参考訳（メタデータ） (2020-09-15T18:17:27Z)

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

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