ショアのアルゴリズム

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

実現可能性とその影響

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

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

アルゴリズム

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

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

位数を求める具体例

例えば、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

出典

^ 竹内薫『量子コンピューターが本当にすごい: Google、NASAで実用が始まった“夢の計算機”』PHP研究所、2015年6月、241頁。ISBN 978-4-569-82498-7。
^ Shor, P.W. (1994). “Algorithms for quantum computation: Discrete logarithms and factoring”. Proceedings 35th Annual Symposium on Foundations of Computer Science. pp. 124–134. doi:10.1109/sfcs.1994.365700. ISBN 978-0-8186-6580-6
^ Shor, P.W. (1994). Algorithms for quantum computation: discrete logarithms and factoring (Report). Proceedings 35th Annual Symposium on Foundations of Computer Science. IEEE. pp. 124–134. doi:10.1109/SFCS.1994.365700. ISBN 0-8186-6580-7。 (ショアのアルゴリズムの論文)]
^ Shor, Peter W. (1997-10). “Polynomial-Time Algorithms for Prime Factorization and Discrete Logarithms on a Quantum Computer”. SIAM Journal on Computing (Society for Industrial & Applied Mathematics (SIAM)) 26 (5): 1484-1509. doi:10.1137/s0097539795293172. ISSN 1095-7111.
^ 長橋賢吾『図解入門よくわかる最新量子ｺﾝﾋﾟｭｰﾀの基本と仕組み』秀和システム、2018年9月、82頁。ISBN 978-4-7980-5455-1。
^ Gidney, Craig; Ekerå, Martin (2021). “How to factor 2048 bit RSA integers in 8 hours using 20 million noisy qubits”. Quantum 5: 433. arXiv:1905.09749. Bibcode: 2021Quant...5..433G. doi:10.22331/q-2021-04-15-433.
^ “Experimental realization of Shor's quantum factoring algorithm using nuclear magnetic resonance”. 2016年6月17日閲覧。
^ Roetteler, Martin; Naehrig, Michael; Svore, Krysta M.; Lauter, Kristin E. (2017). "Quantum resource estimates for computing elliptic curve discrete logarithms". In Takagi, Tsuyoshi; Peyrin, Thomas (eds.). Advances in Cryptology – ASIACRYPT 2017 – 23rd International Conference on the Theory and Applications of Cryptology and Information Security, Hong Kong, China, December 3–7, 2017, Proceedings, Part II. Lecture Notes in Computer Science. Vol. 10625. Springer. pp. 241–270. arXiv:1706.06752. doi:10.1007/978-3-319-70697-9_9. ISBN 978-3-319-70696-2。
^ 嶋田義皓『量子コンピューティング　基本アルゴリズムから量子機械学習まで』オーム社、2020年11月、80頁。ISBN 978-4-274-22621-2。

参考文献

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

実現可能性とその影響

アルゴリズム

位数を求める具体例

出典

参考文献

関連項目