ショアのアルゴリズム
 |
ショアのアルゴリズム（英: 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とする。
- 第一レジスタにアダマールゲート操作を施し、第二レジスタに制御ユニタリゲートUn,xを作用させる。ここで、Un,xとは以下の計算過程集合である。Un,x|α⟩=|αx mod N⟩と変換するようなxとNを引数とするユニタリ演算子Un,xを考え、その固有値を取り出す。(量子位相推定)
- 適切な位数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
出典
[編集]- ^ 竹内薫『量子コンピューターが本当にすごい: 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。
 | この項目は、数理論理学に関連した書きかけの項目です。この項目を加筆・訂正などしてくださる協力者を求めています。 |