講演抄録/キーワード |
講演名 |
2019-11-19 16:00
効率的な量子剰余加算回路の提案とその実装 ○大西健斗(東大/慶大)・田中智樹(三菱UFJフィナンシャル・グループ/三菱UFJ銀行/慶大)・宇野隼平(みずほ情報総研/慶大)・山本直樹(慶大)・國廣 昇(筑波大) |
抄録 |
(和) |
本稿では,Shorアルゴリズムを構成する量子加算回路および量子剰余加算について,従来よりも効率的な実装を行ったうえで,量子ゲート数の見積もりを行う.Shorアルゴリズムは,現在広く利用されているRSA暗号方式や楕円曲線暗号方式への脅威となる量子アルゴリズムである.現在まで,Shorアルゴリズムの計算コストを見積もる研究が多数行われており,Shorアルゴリズムの最小単位である加算に基づいて行われている.したがって,効率的な量子加算回路の構成は,Shorアルゴリズムの計算コストの見積もりに必要不可欠である.本稿では,まず,MarkovとSaeediの量子加算回路と比較して,制御NOTゲートの数を約$54$%に削減した量子加算回路の提案を行う.さらに,従来よりも効率的な量子剰余加算回路の提案を行うとともに,IBM~Qを用いた$2$ビットの剰余加算を行う. |
(英) |
In this paper, we propose more efficient quantum addition and modular addition circuits and estimate the number of quantum gates, that are used in Shor's algorithm. Shor's algorithm is major threat on the widely cryptosystem such as RSA and elliptic curve. There are many researches of estimating the efficiency of Shor's algorithm, and they decompose Shor's algorithm into additions. Thus, constructing efficient quantum addition circuit is important for estimating threat of Shor's algorithm. In this paper, we propose the new quantum addition circuit that the number of quantum gates is about $54$% compared to the original Markov and Saeedi's adder. Moreover, we propose the more efficient quantum modular addition circuit, and implement $2$-bit modular addition on IBM~Q. |
キーワード |
(和) |
量子アルゴリズム / 位数発見問題 / Shorアルゴリズム / 剰余加算 / IBM Q / / / |
(英) |
Quantum Algorithm / Order Finding Problem / Shor's Algorithm / Modular Addition / IBM Q / / / |
文献情報 |
信学技報 |
資料番号 |
|
発行日 |
|
ISSN |
|
PDFダウンロード |
|