ショアのアルゴリズム

ウィキペディア小見出し辞書

ショアのアルゴリズム

出典: フリー百科事典『ウィキペディア（Wikipedia）』 (2022/05/19 00:40 UTC 版)

「量子コンピュータ」の記事における「ショアのアルゴリズム」の解説

ショアのアルゴリズム（英語版）（英: Shor's factorizationとも）とは、素因数分解問題を高速に（多項式時間で）解くことができるアルゴリズムのことである。古典コンピュータでは非現実的な時間（準指数時間）で解くアルゴリズムしか知られていない。1994年にピーター・ショアによって発見された。ショアは本件で、ネヴァンリンナ賞とゲーデル賞を受賞した。 2001年12月にIBMアルマデン研究所にて7量子ビットの量子コンピュータで15 (= 3×5) の素因数分解に成功した（Nature, 12月20日発行号）。 少し改造することで離散対数問題（DLP, ElGamal暗号や楕円曲線暗号の安全性の根拠）も多項式時間で解くことができる。このアルゴリズムの基本的なアイデアを拡張したものが、可換隠れ部分群問題についての量子アルゴリズムである。現在は、これをさらに非可換隠れ部分群問題に拡張する研究が進展している。 ショアのアルゴリズムは、量子コンピュータが離散フーリエ変換を高速に実行できることによる。また、アルゴリズム全体は確率的 (BQP) であり、正しい答えが得られるまで、何度も試行する。 N を素因数分解するにあたり、a は N に対して素な数とし、a の mod N に関する位数、min{x > 0|ax = 1 (mod N)} を求める。つまり、ax の周期 r を求める。位数が高速に求められれば、因数分解は高速に行える。 例えば、N = 15, a = 7 とする。 70 = 1 (mod 15) 71 = 7 (mod 15) 72 = 4 (mod 15) 73 = 13 (mod 15) 74 = 1 (mod 15) 75 = 7 (mod 15) 76 = 4 (mod 15) 77 = 13 (mod 15) 78 = 1 (mod 15) 79 = 7 (mod 15) ⋮ 1,7,4,13,1,7,4,13,1,7,…という周期 4 の数列が生成される。 よって、周期 r = min{x > 0|7x = 1 (mod 15)} = 4 手順の概略は以下の2つ。 全ての x に対して、均等な確率となるように初期化する。そして、それを ax mod N のみ確率を持ち、それらは均等になるように変換する。この計算は量子コンピュータ的であるものの、基本的な考えは古典コンピュータと変わらない。そのために、2進数の足し算・引き算や、ビットによる条件分岐などを用意する。 ax mod N は周期 r を持つ。この周期が求める位数である。従って、1で得られた結果を離散フーリエ変換する。すると、周波数 1/r のところの確率が大きくなるので、観測すると、高い確率で r が得られる。失敗した場合は、成功するまで繰り返す。

ショアのアルゴリズム

出典: フリー百科事典『ウィキペディア（Wikipedia）』 (2022/03/02 07:32 UTC 版)

「量子超越性」の記事における「ショアのアルゴリズム」の解説

ショアのアルゴリズムは、 nビット整数の素因数分解を O ~ ( n 3 ) 時間で行う。これに対して、知られている最善の古典アルゴリズムは 2 O ( n 1 / 3 ) 時間必要である。また、この問題の複雑さの最良の上界は O ( 2 n / 3 + o ( 1 ) ) である。このアルゴリズムは整数因数分解に帰着される全ての問題を高速化する。その中には奇数オーダーの可換体上の行列群のメンバーシップ問題が含まれる。 このアルゴリズムは、 量子コンピューティングにとって実用的にも歴史的にも重要である。古典コンピュータでは解くことの出来ないと信じられている現実の問題に対して提案された、最初の多項式時間量子アルゴリズムである。つまり、今日合理的に信じられている暗号化プロトコルであるRSAが安全であるという仮定の下で、このアルゴリズムは超多項式の高速化を実現する。 例え非常に大きな数の場合でも、因数分解は乗算するだけで従来のコンピューターですばやくチェックできるため、因数分解は他の量子優位性の提案よりも利点がある。ただし、Shorのアルゴリズムを大きな数に対して実装することは、現在の技術では不可能なため、優位性を実証するための戦略として追求されていない。