論文の概要: Quantum prime factorization algorithms using binary carry propagation
- arxiv url: http://arxiv.org/abs/2506.16799v1
- Date: Fri, 20 Jun 2025 07:34:16 GMT
- ステータス: 翻訳完了
- システム内更新日: 2025-06-23 19:00:05.368335
- Title: Quantum prime factorization algorithms using binary carry propagation
- Title（参考訳）: バイナリキャンピング伝搬を用いた量子素因数分解アルゴリズム
- Authors: Arim Ryou, Kiwoong Kim, Kyungtaek Jun,
- Abstract要約: RSA暗号系は、素因数分解の計算困難に依存する。
高次非制約二元最適化(HUBO)と制約二次モデル(CQM)の両方を用いた整数分解に対する量子アニール法に基づくアプローチを提案する。
その結果、グローバルな製品制約を適用することで、すべてのテストインスタンスにおける分解精度と一貫性が向上することがわかった。
- 参考スコア（独自算出の注目度）: 0.0
- License: http://creativecommons.org/licenses/by/4.0/
- Abstract: The RSA cryptosystem, which relies on the computational difficulty of prime factorization, faces growing challenges with the advancement of quantum computing. In this study, we propose a quantum annealing based approach to integer factorization using both high order unconstrained binary optimization (HUBO) and constrained quadratic model (CQM) formulations. We begin by modeling binary multiplication with explicit carry propagation, translating this into a HUBO representation and subsequently reducing it to a quadratic unconstrained binary optimization form compatible with current quantum solvers. To address scalability limitations, we implement a CQM approach with constraint relaxation and global product consistency. While the HUBO model successfully factors small semiprimes, it exhibits exponential memory growth, making it impractical for inputs larger than 10 bits. In contrast, the CQM model achieves accurate factorization of semiprimes up to 60 bits including N = 1152921423002469787 demonstrating significantly improved scalability. Experimental results further show that applying global product constraints enhances factorization accuracy and consistency across all tested instances. This work highlights both the promise and current limitations of quantum-assisted factorization and establishes a foundation for evaluating RSA security in the emerging quantum era.
- Abstract（参考訳）: 素因数分解の計算困難に依存するRSA暗号システムでは、量子コンピューティングの進歩に伴う課題が増大している。
本研究では,高次非制約二元最適化 (HUBO) と制約二次モデル (CQM) を用いた整数分解への量子アニール法に基づくアプローチを提案する。
まず、2進乗算を明示的なキャリー伝搬でモデル化し、これをHUBO表現に変換し、その後、現在の量子解法と互換性のある2進最適化形式に還元する。
スケーラビリティの限界に対処するため、制約緩和とグローバルな製品整合性を備えたCQMアプローチを実装した。
HUBOモデルは小さなセミプライムをうまく決定するが、指数的なメモリ成長を示し、10ビット以上の入力には実用的ではない。
対照的に、CQMモデルは、N = 1152921423002469787を含む60ビットまでの半素数の正確な分解を達成する。
さらに、グローバルな製品制約を適用することで、すべてのテストインスタンスにおける分解精度と一貫性が向上することを示す実験結果が得られた。
この研究は、量子支援因数分解の約束と現在の限界の両方を強調し、新興量子時代のRSAセキュリティを評価する基盤を確立する。
関連論文リスト
- VQC-MLPNet: An Unconventional Hybrid Quantum-Classical Architecture for Scalable and Robust Quantum Machine Learning [60.996803677584424]
変分量子回路(VQC)は、量子機械学習のための新しい経路を提供する。
それらの実用的応用は、制約付き線形表現性、最適化課題、量子ハードウェアノイズに対する鋭敏感といった固有の制限によって妨げられている。
この研究は、これらの障害を克服するために設計されたスケーラブルで堅牢なハイブリッド量子古典アーキテクチャであるVQC-MLPNetを導入している。
論文 参考訳（メタデータ） (2025-06-12T01:38:15Z) - Improving adiabatic quantum factorization via chopped random-basis optimization [1.1409483429861258]
我々は、断熱的量子因数分解アルゴリズムを強化するために、チョップランダム基底(CRAB)最適化手法を適用した。
21から2479までの整数を分解するためにCRABを適用することで、CRABの有効性を実証する。
この性能改善は、雑音が劣化している場合のレジリエンスを示し、ノイズの多い量子システムにおけるCRABの実用性を強調している。
論文 参考訳（メタデータ） (2025-05-22T03:06:02Z) - An Efficient Quantum Classifier Based on Hamiltonian Representations [50.467930253994155]
量子機械学習(QML)は、量子コンピューティングの利点をデータ駆動タスクに移行しようとする分野である。
入力をパウリ弦の有限集合にマッピングすることで、データ符号化に伴うコストを回避できる効率的な手法を提案する。
我々は、古典的および量子モデルに対して、テキストおよび画像分類タスクに対する我々のアプローチを評価する。
論文 参考訳（メタデータ） (2025-04-13T11:49:53Z) - Qubit-Efficient Quantum Annealing for Stochastic Unit Commitment [4.2251752131402585]
再生可能エネルギー源の統合によって引き起こされる不確実性を管理するため、ユニットコミット(SUC)が提案されている。
本稿では,スラック変数を不要にするために,パウエル・ヘステネス・ロッカフェラー拡張ラグランジアン乗算器(PHR-ALM)法を提案する。
さらに量子ADMMを適用して、大規模SUCを小さなブロックに分割し、シーケンシャルな解を可能にする。
論文 参考訳（メタデータ） (2025-02-21T20:15:40Z) - QUBO Refinement: Achieving Superior Precision through Iterative Quantum Formulation with Limited Qubits [3.2995359570845912]
量子アルゴリズムは線形方程式と固有値を解くことができ、古典的なコンピュータのペースを超える。
この技術を活用することで、線形システム、固有値問題、RSA暗号システム、CT画像再構成などの応用のための量子最適化モデルが提案されている。
既存のQiskitシミュレーター、D-Waveシステムシミュレーター、ハイブリッドソルバの精度は2つの10箇所に限られている。
本稿では,各数を二項化する際に,最上位から最下位に順次進行する新しい反復アルゴリズムを提案する。
論文 参考訳（メタデータ） (2024-11-25T06:56:00Z) - Early Fault-Tolerant Quantum Computing [0.0]
我々は,早期フォールトトレラント量子コンピューティング(EFTQC)アーキテクチャの性能評価モデルを開発した。
位相推定の標準的なタスクでは、適度なスケーラビリティと100万以上の物理量子ビットを使用すると、量子コンピュータのリーチ'を拡張できることが示される。
論文 参考訳（メタデータ） (2023-11-24T19:12:47Z) - Analyzing Prospects for Quantum Advantage in Topological Data Analysis [35.423446067065576]
我々は、トポロジカルデータ解析のための改良された量子アルゴリズムを解析し、最適化する。
超二次量子スピードアップは乗法誤差近似をターゲットとする場合にのみ可能であることを示す。
数百億のトフォリを持つ量子回路は、古典的に難解なインスタンスを解くことができると我々は主張する。
論文 参考訳（メタデータ） (2022-09-27T17:56:15Z) - Quantum Robustness Verification: A Hybrid Quantum-Classical Neural
Network Certification Algorithm [1.439946676159516]
本研究では、堅牢性多変数混合整数プログラム(MIP)の解法を含むReLUネットワークの検証について検討する。
この問題を軽減するために、ニューラルネットワーク検証にQCを用い、証明可能な証明書を計算するためのハイブリッド量子プロシージャを導入することを提案する。
シミュレーション環境では,我々の証明は健全であり,問題の近似に必要な最小量子ビット数に制限を与える。
論文 参考訳（メタデータ） (2022-05-02T13:23:56Z) - A Hybrid Quantum-Classical Algorithm for Robust Fitting [47.42391857319388]
本稿では,ロバストフィッティングのためのハイブリッド量子古典アルゴリズムを提案する。
私たちのコアコントリビューションは、整数プログラムの列を解く、新しい堅牢な適合式である。
実際の量子コンピュータを用いて得られた結果について述べる。
論文 参考訳（メタデータ） (2022-01-25T05:59:24Z) - Realization of arbitrary doubly-controlled quantum phase gates [62.997667081978825]
本稿では,最適化問題における短期量子優位性の提案に着想を得た高忠実度ゲートセットを提案する。
3つのトランペット四重項のコヒーレントな多レベル制御を編成することにより、自然な3量子ビット計算ベースで作用する決定論的連続角量子位相ゲートの族を合成する。
論文 参考訳（メタデータ） (2021-08-03T17:49:09Z) - Error mitigation and quantum-assisted simulation in the error corrected
regime [77.34726150561087]
量子コンピューティングの標準的なアプローチは、古典的にシミュレート可能なフォールトトレラントな演算セットを促進するという考え方に基づいている。
量子回路の古典的準確率シミュレーションをどのように促進するかを示す。
論文 参考訳（メタデータ） (2021-03-12T20:58:41Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。