ショアのアルゴリズム

ウィキペディア

ショアのアルゴリズム

出典: フリー百科事典『ウィキペディア（Wikipedia）』 (2024/11/02 23:30 UTC 版)

ショアのアルゴリズム（英: Shor's algorithm）は、1994年にアメリカの数学者ピーター・ショアによって考案された、素因数分解問題を高速に（多項式時間で）解くことができるアルゴリズムのことである。いまのところ古典コンピュータでは非現実的な時間（分解したい整数の桁数についての準指数時間）で解くアルゴリズムしか知られていない。一方で、実用的に使用されるような素因数分解が解けるようになるには、将来的にさらなる量子ビットが必要である。ショアは本件で、ネヴァンリンナ賞とゲーデル賞を受賞した。また、2001年12月にIBMアルマデン研究所にて7量子ビットの量子コンピュータで15 (= 3×5) の素因数分解に成功した。

実現可能性とその影響

現在の量子コンピューターには、量子ノイズや、量子力学的干渉の破壊といった課題が存在する。しかし、それらの課題を克服し、ある程度の量子ビット数の量子コンピューターを、操作することができるようになったとすると、RSA暗号、ディフィー・ヘルマン鍵共有、楕円曲線ディフィー・ヘルマン鍵共有などの公開鍵暗号の解読ができてしまうと考えられている。なぜなら、例えばRSA暗号は、大きな素数同士の合成数を機械で素因数分解するのは、膨大な時間がかかり困難であるという推定のもとで基づいているからである。

アルゴリズムを少し変更することで離散対数問題（DLP, ElGamal暗号や楕円曲線暗号の安全性の根拠）も多項式時間で解くことができる。このアルゴリズムの基本的なアイデアを拡張したものが、可換隠れ部分群問題についての量子アルゴリズムである。現在は、これをさらに非可換隠れ部分群問題に拡張する研究が進展している。

アルゴリズム

ショアのアルゴリズムは、量子コンピュータが離散フーリエ変換を高速に実行できることを用いている。また、アルゴリズム全体は確率的 (BQP) であるので、正しい答えが得られるまで、何度も試行をする必要がある。

1. 素因数分解したいNと互いに素な整数xを用意する。
2. Nの二進数表記の桁数をLとし、位相推定の精度tは2L+1とする。
3. 第一レジスタにアダマールゲート操作を施し、第二レジスタに制御ユニタリゲートU_n,xを作用させる。ここで、U_n,xとは以下の計算過程集合である。U_n,x|α⟩=|αx mod N⟩と変換するようなxとNを引数とするユニタリ演算子U_n,xを考え、その固有値を取り出す。(量子位相推定)
4. 適切な位数rが見つかったら、p=gcd(x^r/2+1,N),q=gcd(x^r/2-1,N)がNの素因数である。

量子位相測定のサブルーチン

位数を求める具体例

例えば、N = 15, a = 7 とする。

7⁰ = 1 (mod 15)

7¹ = 7 (mod 15)

7² = 4 (mod 15)

7³ = 13 (mod 15)

7⁴ = 1 (mod 15)

7⁵ = 7 (mod 15)

7⁶ = 4 (mod 15)

7⁷ = 13 (mod 15)

7⁸ = 1 (mod 15)

7⁹ = 7 (mod 15)

⋮

1,7,4,13,1,7,4,13,1,7,…という周期 4 の数列が生成される。

よって、周期 r = min{x > 0|7^x = 1 (mod 15)} = 4

参考文献

• Nielsen, Michael A.; Chuang, Isaac L. (2010). Quantum Computation and Quantum Information: 10th Anniversary Edition. Cambridge University Press. ISBN 978-1-107-00217-3 
• Kaye, Phillip; Laflamme, Raymond; Mosca, Michele (2006). An Introduction to Quantum Computing. doi:10.1093/oso/9780198570004.001.0001. ISBN 978-0-19-857000-4 
• "Explanation for the man in the street" by Scott Aaronson, "approved" by Peter Shor.
• Shor, Peter W. (1997), “Polynomial-Time Algorithms for Prime Factorization and Discrete Logarithms on a Quantum Computer”, SIAM J. Comput. 26 (5): 1484–1509, arXiv:quant-ph/9508027v2, Bibcode: 1999SIAMR..41..303S, doi:10.1137/S0036144598347011 .
• Quantum Computing and Shor's Algorithm, Matthew Hayward's Quantum Algorithms Page, 2005-02-17, imsa.edu, LaTeX2HTML version of the original LaTeX document, also available as PDF or postscript document.
• Quantum Computation and Shor's Factoring Algorithm, Ronald de Wolf, CWI and University of Amsterdam, January 12, 1999, 9 page postscript document.
• Shor's Factoring Algorithm, Notes from Lecture 9 of Berkeley CS 294–2, dated 4 Oct 2004, 7 page postscript document.
• Chapter 6 Quantum Computation Archived 2020-04-30 at the Wayback Machine., 91 page postscript document, Caltech, Preskill, PH229.
• Quantum computation: a tutorial by Samuel L. Braunstein.
• The Quantum States of Shor's Algorithm, by Neal Young, Last modified: Tue May 21 11:47:38 1996.
• III. Breaking RSA Encryption with a Quantum Computer: Shor's Factoring Algorithm, Lecture notes on Quantum computation, Cornell University, Physics 481–681, CS 483; Spring, 2006 by N. David Mermin. Last revised 2006-03-28, 30 page PDF document.
• Lavor, C.; Manssur, L. R. U.; Portugal, R. (2003). "Shor's Algorithm for Factoring Large Integers". arXiv:quant-ph/0303175。
• Lomonaco, Jr (2000). "Shor's Quantum Factoring Algorithm". arXiv:quant-ph/0010034。 This paper is a written version of a one-hour lecture given on Peter Shor's quantum factoring algorithm. 22 pages.
• Chapter 20 Quantum Computation, from Computational Complexity: A Modern Approach, Draft of a book: Dated January 2007, Sanjeev Arora and Boaz Barak, Princeton University. Published as Chapter 10 Quantum Computation of Sanjeev Arora, Boaz Barak, "Computational Complexity: A Modern Approach", Cambridge University Press, 2009, ISBN 978-0-521-42426-4
• A Step Toward Quantum Computing: Entangling 10 Billion Particles Archived 2011-01-20 at the Wayback Machine., from "Discover Magazine", Dated January 19, 2011.
• Josef Gruska - Quantum Computing Challenges also in Mathematics unlimited: 2001 and beyond, Editors Björn Engquist, Wilfried Schmid, Springer, 2001, ISBN 978-3-540-66913-5

関連項目

• グローバーのアルゴリズム

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

ショアのアルゴリズム

出典: フリー百科事典『ウィキペディア（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 が得られる。失敗した場合は、成功するまで繰り返す。