QUBOモデルを用いる素因数分解のための解析的およびパターンベース変数削減手法

• Item type: Symposium(1)
• 公開日: 2024-08-21
• タイトル: QUBOモデルを用いる素因数分解のための解析的およびパターンベース変数削減手法
• タイトル / 言語: en
• タイトル: Analytical and Pattern-based Variable Reduction Methods for Prime Factorization Using the QUBO Model
• 言語: jpn
• キーワード / 主題Scheme: Other
• キーワード / 主題: 量子コンピュータ
• 資源タイプ / 資源タイプ識別子: http://purl.org/coar/resource_type/c_5794
• 資源タイプ: conference paper
• 著者所属: 京都大学
• 著者所属: 早稲田大学
• 著者所属: 早稲田大学
• 著者所属: 早稲田大学
• 著者所属: 京都大学
• 著者所属(英): en
• 著者所属(英): Graduate School of Informatics, Kyoto University
• 著者所属(英): en
• 著者所属(英): Graduate School of Information, Production and Systems, Waseda University
• 著者所属(英): en
• 著者所属(英): Graduate School of Information, Production and Systems, Waseda University
• 著者所属(英): en
• 著者所属(英): Graduate School of Information, Production and Systems, Waseda University
• 著者所属(英): en
• 著者所属(英): Graduate School of Informatics, Kyoto University
• 著者名: Xinyi, Guo; Geguang, Miao; 西澤, 真一; 木村, 晋二; 佐藤, 高史
• 著者名(英): Xinyi, Guo; Geguang, Miao; Shinichi, Nishizawa; Shinji, Kimura; Takashi, Sato
• 論文抄録 / 内容記述タイプ: Other
• 論文抄録 / 内容記述: 大きな半素数の素因数分解は，古典コンピュータにとって最も難しい問題の一つである．素因数分解問題は，二次制約なしバイナリ最適化 (Quadratic unconstrained binary optimization; QUBO) モデルに変換することで，量子アニーリング等を用いて解けることが知られている．この素因数分解の効率を向上するために部分積をブロック分割して解く方法が提案されているが，分解可能な半素数の最大の桁数は 26 ビットに留まっている．本論文では，QUBO モデルを用いる素因数分解のための 4 つの変数削減手法を提案する．第一の方法では，解くべき問題を制約を緩めた複数の小問題に分割し，それらを独立に解く．第二および第三の方法では，最下位ビット(LSB) および最上位ビット (MSB) 近傍の変数を解析的に削減する．第四の方法では，ビット幅が奇数であり MSB に連続したゼロが続く特別な半素数について，解析的に変数を削減する．量子アニーリング計算機上の実験により，提案する方法が効果的に変数を削減でき，最大 47 ビットまでの半素数の因数分解を 20 秒以内で行えることを示す．また，第四の方法を用いることで，最大 101ビットの半素数を因数分解できることを示す．
• 論文抄録(英) / 内容記述タイプ: Other
• 論文抄録(英) / 内容記述: Factorization of large semiprimes poses a significant challenge for classical computing. It is known that the prime factorization problem can be solved using quantum annealing and other methods by transforming it into a quadratic unconstrained binary optimization (QUBO) model. Although conversion methods utilize blockwise sums of partial products, the largest factorizable subprimes are currently limited up to 26 bits. This paper introduces four approaches for factorizing large semiprimes using quantum annealing. The first approach decomposes the original problem into multiple sub-problems with partial constraints, each solved through independent annealing processes. The second and third approaches analytically reduce the number of variables by focusing on regions near the least significant bit (LSB) and the most significant bit (MSB), respectively. The fourth approach takes advantage of special patterns in semiprimes―such as those with odd bit widths and contiguous zeros near the MSB―to further reduce the number of variables required. When integrated into a QUBO model, these four approaches significantly reduce the number of variables, facilitating reliable factorization of semiprimes up to 47 bits within 20 seconds. By applying all four techniques synergistically, the proposed approaches are capable of factorizing semiprimes up to 101 bits.
• 書誌情報: DAシンポジウム2024論文集; 巻 2024, p. 264-271, 発行日 2024-08-21
• 出版者 / 言語: ja
• 出版者: 情報処理学会