中国剰余定理と量子フーリエ加算を用いたショアの素因数分解回路の簡略化

• Item type: SIG Technical Reports(1)
• 公開日: 2023-03-06
• タイトル: 中国剰余定理と量子フーリエ加算を用いたショアの素因数分解回路の簡略化
• タイトル / 言語: en
• タイトル: Simplifying Shor's factoring circuit using the Chinese Remainder Theorem and quantum Fourier addition
• 言語: jpn
• 資源タイプ / 資源タイプ識別子: http://purl.org/coar/resource_type/c_18gh
• 資源タイプ: technical report
• 著者所属: 筑波大学／慶應義塾大学
• 著者所属: 慶應義塾大学
• 著者所属: 慶應義塾大学／株式会社三菱UFJフィナンシャル・グループ／株式会社三菱UFJ銀行
• 著者所属: 慶應義塾大学／みずほリサーチ&テクノロジーズ株式会社
• 著者所属: 筑波大学／慶應義塾大学
• 著者所属(英): en
• 著者所属(英): University of Tsukuba / Keio University
• 著者所属(英): en
• 著者所属(英): Keio University
• 著者所属(英): en
• 著者所属(英): Keio University / Mitsubishi UFJ Financial Group, Inc. / MUFG Bank, Ltd.
• 著者所属(英): en
• 著者所属(英): Keio University / Mizuho Research & Technologies, Ltd.
• 著者所属(英): en
• 著者所属(英): University of Tsukuba / Keio University
• 著者名: 桂, 潔成; 佐藤, 貴彦; 田中, 智樹; 大塩, 耕平; 國廣, 昇
• 論文抄録 / 内容記述タイプ: Other
• 論文抄録 / 内容記述: RSA 暗号などは，ショアのアルゴリズムを用いることで大規模な量子コンピュータによって多項式時間で解読可能である．そのため，安全に暗号を使う上では実機で解読可能となる時期を正確に見積もることが重要である．従来の，簡略化された回路を用いた NISQ デバイスによる素因数分解の実験では，成功確率の下限を理論保証するために，十分な数の制御ビットを用いていない．これは制御ビットの数の増加に伴い，回路の量子ゲート数が増加し，実験が困難になるためである．したがって，制御ビット数を増やすためには，回路の更なる効率化が求められる．本研究では，簡略化された回路を効率的に実装するために，中国剰余定理による剰余加算回路の分解，量子フーリエ変換を用いた剰余加算回路，複数の静的回路を用いた動的回路の疑似実装手法の三つを提案する．また，これらを採用した素因数分解回路を実機上で実行し，素因数分解の実験を行う．
• 論文抄録(英) / 内容記述タイプ: Other
• 論文抄録(英) / 内容記述: The RSA cipher can be decrypted in polynomial time by a large-scale quantum computer using the Shor algorithm. Therefore, a research challenge for secure cryptography is to accurately estimate the time when it can be cracked by a real device. Previous work on prime factorisation with NISQ devices using simplified circuits did not use a sufficient number of measurement qubits to provide a theoretical guarantee for a lower bound on the probability of success. This is because the number of gates in the circuit increases as the number of measurement qubits increases. Therefore, to increase the number of measurement qubits, a further improvement in the efficiency of the circuit is required. In this study, three methods are proposed: a modular adder using the quantum Fourier transform, a simplification using the Chinese remainder theorem, and a pseudo-implementation method for dynamic circuits using multiple static circuits. In addition, a factorisation circuit using these methods is actually implemented on a real device.
• 書誌レコードID / 収録物識別子タイプ: NCID
• 書誌レコードID / 収録物識別子: AA12894105
• 書誌情報: 研究報告量子ソフトウェア（QS）; 巻 2023-QS-8, 号 27, p. 1-8, 発行日 2023-03-06
• ISSN / 収録物識別子タイプ: ISSN
• ISSN / 収録物識別子: 2435-6492
• Notice: SIG Technical Reports are nonrefereed and hence may later appear in any journals, conferences, symposia, etc.
• 出版者 / 言語: ja
• 出版者: 情報処理学会