Shorの素因数分解アルゴリズム
現在，千葉大学大学院で符号暗号を研究しているM1です．
月１ぐらいのペースで，研究関連？の分野を勉強したことをまとめていこうと思います．
理論と実装どっちもやりますが，基本的には実装メインで書いたQiitaの記事の理論部分の補強をメインで書いていきます．たまに自分の研究分野の理論を簡単に実装を詳細に紹介するスタイルをとると思います．
＊そんなこんなでガバとかあったら指摘お願いします・・・
今回は，Shorの素因数分解アルゴリズムについてです．
下記のQiitaの記事の理論部分を詳しくしたって感じです．
（アルゴリズムの正当性とか上で書かんくても良かったな…）
追記
原論文をより深く理解したい方はこちらを
概要
Shor, Peter W. "Algorithms for quantum computation: discrete logarithms and factoring." Proceedings 35th annual symposium on foundations of computer science. Ieee, 1994.
こちらは，現状の公開鍵暗号系でよく用いられるRSA暗号やElgamal暗号に基づくNP困難問題（素因数分解・離散対数問題）は，量子コンピュータによって多項式時間で解読されることを解説した論文です．
今回は素因数分解のみに絞ります．
記号など
＊は知っている方向けの補足です
＊
＊
＊
Shorの素因数分解アルゴリズム
Input :
Output :
i). ランダムに
ii).
iii).
iv).
then
else i). に戻る
i) は
iii) が量子アルゴリズムを用いる箇所になります，それ以外の例えば
ちなみにですが，このアルゴリズムの正当性は次のように示されます．
まず，
以上よりOKです．
停止性は，特に任意の
例
ここでは
(1)
また，
(2)
(3)
しかし，
※厳密には，例えば，(1)で「
実は，Nielsen-Chunang で，
＊RSA暗号では，大きい素数
モジュールを用いた実装
実装がめんどくさい方は，実は次のコード（ここでは
from qiskit import BasicAer
from qiskit.aqua import QuantumInstance
from qiskit.aqua.algorithms import Shor
N = 21
shor = Shor(N)
backend = BasicAer.get_backend('qasm_simulator')
quantum_instance = QuantumInstance(backend, shots=1024)
result = shor.run(quantum_instance)
print(f"The list of factors of {N} as computed by the Shor's algorithm is {result['factors'][0]}.")
出力
The list of factors of 21 as computed by the Shor's algorithm is [3, 7].
実験とかするときに用いられることを想定しているようです．→参考
ただ，
iii)の方針
実装はpythonのqiskitというモジュールを使います
Qiskit Textbook を参考にしています．
＊和訳
また，以下では，「上手くいく」
目標は以下のUnitary演算子で量子位相推定を行い，
方針
-
U | y \rangle \equiv | 8y \ \mathrm{mod} \ 35 \rangle y = 1 U - 固有状態を得るために，量子Fourier変換を作用させる
- 上記で得られた値を測定することで位数を得る
って感じです．それでは順にコードを見ていきます．
初めに以下をインポートしています．
from qiskit import QuantumCircuit, Aer, transpile, assemble
# from numpy.random import randint
from math import gcd
import math
import numpy as np
from fractions import Fraction
print("Imports Successful")
出力
Imports Successful
1.U | y \rangle \equiv | 8y \ \mathrm{mod} \ 35 \rangle y = 1 U
理論
まず，
＊
今回なら，
このとき，
なる状態を考えます．
＊
次に，
を考えます．
そして，上記の状態の合成を考えると，
となります．
実装
def c_xmod35(x: int, N: int, power: int) -> list:
"""Controlled multiplication by a mod 35"""
gate_number = int(math.log2(N))
U = QuantumCircuit(gate_number)
for iteration in range(power):
U.swap(0, 1)
U.swap(1, 2)
U.swap(2, 3)
U.cx(0, 1)
U.cx(2, 0)
U.cx(2, 3)
U.cx(2, 4)
U.cx(1, 0)
U.cx(1, 4)
U = U.to_gate()
U.name = "%i^%i mod 35" % (x, power)
c_U = U.control()
return c_U
2.固有状態を得るために，量子Fourier変換を作用させる
理論
状態
になります．
実装
def qft_dagger(n: int) -> list:
qc = QuantumCircuit(n)
for qubit in range(n//2):
qc.swap(qubit, n-qubit-1)
for j in range(n):
for m in range(j):
qc.cp(-np.pi/float(2**(j-m)), m, j)
qc.h(j)
qc.name = "QFT†"
return qc
3.上記で得られた値を測定することで位数を得る
理論
状態
そして，
＊上２つの詳細は論文に書かれています（行間もある上に細々とした議論ですが）
実は
であることが知られています．ここで，
よって，
実装
def qpe_xmod35(x: int, N: int) -> int:
n_count = 3
gate_number = int(math.log2(N))
qc = QuantumCircuit(gate_number+n_count, n_count)
for q in range(n_count):
qc.h(q)
qc.x(3+n_count)
for q in range(n_count):
qc.append(c_xmod35(x, N, 2**q),
[q] + [i+n_count for i in range(gate_number)])
qc.append(qft_dagger(n_count), range(n_count))
qc.measure(range(n_count), range(n_count))
qasm_sim = Aer.get_backend('qasm_simulator')
t_qc = transpile(qc, qasm_sim)
obj = assemble(t_qc, shots=1)
result = qasm_sim.run(assemble(t_qc), memory=True).result()
readings = result.get_memory()
print("Register Reading: " + readings[0])
phase = int(readings[0],2)/(2**n_count)
print("Corresponding Phase: %f" % phase)
return phase
今までのを全てまとめると次のようになります．
N = 35
factor_found = False
attempt = 0
while not factor_found:
x = 8 # 本当は x = randint(2, N - 1)
if gcd(x, N) == 1:
attempt += 1
print("\nAttempt %i:" % attempt)
phase = qpe_xmod35(x, N) # Phase = s/r
frac = Fraction(phase).limit_denominator(N)
r = frac.denominator
if phase != 0 :
guesses = [gcd(x**(r//2)-1, N), gcd(x**(r//2)+1, N)]
print("Guessed Factors: %i and %i" % (guesses[0], guesses[1]))
for guess in guesses:
if guess not in [1,N] and (N % guess) == 0:
print("*** Non-trivial factor found: %i ***" % guess)
factor_found = True
出力（↓がそのまま出力されるとは限りません）
Attempt 1:
Register Reading: 011
Corresponding Phase: 0.375000
Guessed Factors: 35 and 1
Attempt 2:
Register Reading: 110
Corresponding Phase: 0.750000
Guessed Factors: 7 and 5
*** Non-trivial factor found: 7 ***
*** Non-trivial factor found: 5 ***
まとめ
符号暗号（っていうか耐量子暗号）をやるなら，ある程度は敵（量子計算機）のことも知っておかないとな〜と思い，勉強してまとめてみました．ちなみに，今やっている研究にSimonのアルゴリズムなどが関係してくるっぽいので，そちらも勉強したらまとめると思います（どこに？）．
今回は実装が先にあったので，そこに合わない原論文の理論的な部分（と議論が面倒な部分）は省略してしまいましたが，興味のある方はぜひ論文を読んでみてください．
Discussion