ショアのアルゴリズム（英: 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. 第一レジスタにアダマールゲート操作を施し、第二レジスタに制御ユニタリゲートUn,xを作用させる。ここで、Un,xとは以下の計算過程集合である。Un,x|α⟩=|αx mod N⟩と変換するようなxとNを引数とするユニタリ演算子Un,xを考え、その固有値を取り出す。(量子位相推定)
  4. 適切な位数rが見つかったら、p=gcd(xr/2 1,N),q=gcd(xr/2-1,N)がNの素因数である。

位数を求める具体例

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

出典

参考文献

  • 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

関連項目

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

ショアのアルゴリズム PPT

ショアのアルゴリズム PPT

ショアのアルゴリズム PPT

【Quantum Challenge2021】ショアのアルゴリズムで35を因数分解する

【Quantum Challenge2021】ショアのアルゴリズムで35を因数分解する