ショアのアルゴリズム（）は、1994年にピーター・ショアによって提案された (ショアのアルゴリズムの論文)]、量子コンピュータ上で整数の素因数分解を多項式時間で実行できる量子アルゴリズムである。素因数分解は古典コンピュータでは効率的な解法が知られておらず、本アルゴリズムは量子計算の優位性を示す代表例とされる。
理論上は古典コンピュータによるシミュレーションも可能であるが、必要な計算資源が指数的に増大するため、大規模な素因数分解を効率的に解くには量子コンピュータが不可欠と考えられており、この性質は素因数分解の困難さに依存する公開鍵暗号方式の安全性にも影響を及ぼしうることから、量子計算および暗号研究において重要な位置を占めている。
実現可能性とその影響 現在の量子コンピューターには、量子ノイズや、量子力学的干渉の破壊といった課題が存在する。しかし、それらの課題を克服し、ある程度の量子ビット数の量子コンピューターを、操作することができるようになったとすると、RSA暗号、ディフィー・ヘルマン鍵共有、楕円曲線ディフィー・ヘルマン鍵共有などの公開鍵暗号の解読ができてしまうと考えられている。なぜなら、例えばRSA暗号は、大きな素数同士の合成数を機械で素因数分解するのは、膨大な時間がかかり困難であるという推定のもとで基づいているからである。
アルゴリズムを少し変更することで離散対数問題（DLP, ElGamal暗号や楕円曲線暗号の安全性の根拠）も多項式時間で解くことができる。このアルゴリズムの基本的なアイデアを拡張したものが、可換隠れ部分群問題についての量子アルゴリズムである。現在は、これをさらに非可換隠れ部分群問題に拡張する研究が進展している。
アルゴリズム ショアのアルゴリズムは、量子コンピュータが離散フーリエ変換を高速に実行できることを用いている。また、アルゴリズム全体は確率的 (BQP) であるので、正しい答えが得られるまで、何度も試行をする必要がある。
素因数分解したいNと互いに素な整数aを用意する。 Nの二進数表記の桁数をLとし、位相推定の精度tは2L+1とする。 第一レジスタにアダマールゲート操作を施し、第二レジスタに制御ユニタリゲートUn,aを作用させる。ここで、Un,aとは以下の計算過程集合である。Un,a|α⟩=|αa mod N⟩と変換するようなaとNを引数とするユニタリ演算子Un,aを考え、その固有値を取り出す。(量子位相推定) 適切な位数rが見つかったら、p=gcd(ar/2+1,N),q=gcd(ar/2-1,N)がNの素因数である。 中央|サムネイル|507x507ピクセル|量子位相測定のサブルーチン
位数を求める具体例 例えば、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
p = gcd(ar/2+1,N) = gcd(74/2+1,15) = gcd( 50, 15) = 5
q = gcd(ar/2-1,N) = gcd(74/2-1,15) = gcd( 48, 15) = 3
よって、最終的に得られる「5, 3」が素因数である。
出典
参考文献
"Explanation for the man in the street" by Scott Aaronson, "approved" by Peter Shor. . 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 , 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.
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, A Step Toward Quantum Computing: Entangling 10 Billion Particles , 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,
関連項目
グローバーのアルゴリズム