設計によるセレンディピティ

"The most powerful force in the universe is compound interest."

shor's algorithm メモ

shor's algorithm

 N因数分解するにあたり,  a Nに対して素な数とし,
 a mod \ N に関する位数,


min \{ x | a^x = 1 \begin{eqnarray}\pmod{N}\end{eqnarray}\}
つまり,  a^x の周期  r を求める.


N = 15
a = 7
とする.

 7^1 = 7 \begin{eqnarray}\pmod{15}\end{eqnarray}
 7^2 = 4 \begin{eqnarray}\pmod{15}\end{eqnarray}
 7^3 = 13 \begin{eqnarray}\pmod{15}\end{eqnarray}
 7^4 = 1 \begin{eqnarray}\pmod{15}\end{eqnarray}
 7^5 = 7 \begin{eqnarray}\pmod{15}\end{eqnarray}
 7^6 = 4 \begin{eqnarray}\pmod{15}\end{eqnarray}
 7^7 = 13 \begin{eqnarray}\pmod{15}\end{eqnarray}
 7^8 = 1 \begin{eqnarray}\pmod{15}\end{eqnarray}
 7^9 = 7 \begin{eqnarray}\pmod{15}\end{eqnarray}
...

7,4,13,1,7,4,13,1,7... という周期4 の数列が生成される.
よって,周期 r =min \{ x | 7^x = 1 \begin{eqnarray}\pmod{15}\end{eqnarray}\} = 4

離散フーリエ変換??

量子コンピュータとは何か (ハヤカワ文庫NF―数理を愉しむシリーズ)

量子コンピュータとは何か (ハヤカワ文庫NF―数理を愉しむシリーズ)