.svg)
量子アルゴリズムShorのアルゴリズム
それは何か
ショールのアルゴリズムは、大きな数の素因数を多項式時間で求めるアルゴリズムである。サイバーセキュリティでは、一般的な暗号化技術にRSA（Rivest-Shamir-Adleman）がある。RSAは、秘密にされている2つの大きな素数の積である公開鍵に基づいている。RSAは、コンピュータが非常に大きな数をその素数成分に因数分解できないという仮定に基づいている。因数分解は、足し算や掛け算とはまったく異なる種類の問題解決だからだ。ショールのアルゴリズムは、量子力学的な重ね合わせと干渉の性質を利用して、可能性のある解を素早く探索する。
For example, according to Thorsten Kleinjung of the University of Bonn, it would take 1 or 2 years to factor N = 13506641086599522334960321627880596993888147560566702752448514385152651060485953383394028715057190944179820728216447155137368041970396491743046496589274256239341020864383202110372958725762358509643110564073501508187510676594629205563685529475213500852879416377328533906109750544334999811150056977236890927563 on a 2.2 GHz Athlon 64 CPU PC with ≤ 2 GB memory.
ショールのアルゴリズムは、あらゆる素数を因数分解する可能性を秘めた強力なツールであり、その使い手は現在の暗号の多くを破ることができる。現在のNISQ量子コンピュータでは、RSA暗号を破るにはまだ不十分だが、専門家は数年以内に可能になると見積もっている。実際、ショールのアルゴリズムは量子コンピューターへの大きな関心を呼び起こした。
ショールのアルゴリズムは、10年以内に量子アニーリングデバイス（最適化用途に特化した非普遍的な量子コンピューター）上で実行できるようになるだろうという予測もあるが、この計算には多くの要素が含まれている。これは、1年おきにアニーリング量子ビットの数が、過去に起こったように倍増すると仮定したものだが、この計算に全面的に頼ってはいけない。アニーリング量子ビットの進歩は、この時間枠を遅らせる様々な障害によって妨げられる可能性がある。あるいは、アニーリングやユニバーサル量子コンピューティングの継続的な研究によって、このプロセスを加速させるより優れたアルゴリズムや技術を明らかにするブレークスルーがもたらされる可能性もある。
RSA暗号が使い物にならなくなるという深刻さだけでなく、この時間軸の不確実性は、隣接する分野や政府からも注目を集めている。最近、ポスト量子暗号（PQC）の標準と枠組みを作り、量子耐性アルゴリズムを開発するスケジュールを定めた米国の大統領令は、このセキュリティ侵害がいかに深刻かを示している。データがあるところには、セキュリティの必要性がある。世界中の企業のCIO/CTOは、ショーのアルゴリズムの影響を学んだ後、量子に投資しており、多くの場合、他のアプリケーションで量子の能力を強化し、量子の旅を始めるのを待っている企業よりも優位に立っている。例えば、ユナイテッドヘルス・グループは3大陸に量子チームを持ち、量子暗号からスタートした後、量子機械学習による人工知能アプリケーションの調査を始めている。
仕組み
ショールのアルゴリズムの本質は、RSA鍵を含む関数の周期を見つけることによって、誤った因子の推測をより良いものに変えることにある。
因数分解する大きな数$N$と、最初の推測$g$から始める。g$は$N$の因数であるか、$N$と共通の因数である。この場合、ユークリッドのアルゴリズム、またはより高速なユークリッド・アルゴリズム（それぞれ、引き算やモジュロを使って、共通因数を調べたり見つけたりする方法）のおかげで解決する。N$の因数を求めるには、厳密に因数を当てる必要はなく、$N$と因数を共有するものでもよい。
もし $g$ が $N$ の因数でも共通因数でもなければ、この推測をよりよいものに変換することに移る。A$ と $B$ の2つの整数について、$A^p = m*B +1$ となるべき乗 $p$ と倍数 $m$ が存在する。これをいくつかの素数、例えば3と7で示すことができる。
$3^2 = 9 = 1*7 + 2$
$3^3 = 27 = 3*7 + 6$
$3^4 = 81 = 11*7 + 4$
$3^5 = 243 = 34*7 + 5$
$3^6 = 729 = 104*7 + 1$
この関係は、私たちが問題を違った角度から見る助けとなる。
We can write our relationship with our terms: $g^p = m*N +1$. Once we subtract 1 from both sides, getting $g^p-1 = m*N$, we can rewrite this as $(g^{\frac{p}{2}} + 1)(g^{\frac{p}{2}} - 1) = m*N$, as this is a difference of two squares. This looks more like two factors of $N$, for which we are searching, so instead of searching for a better guess $g$, we will now search for a power $p$.
そこで量子コンピューターが活躍する。可能性のある力の重ね合わせを巧みに構築し、すべての不正確な推測が互いに破壊的に干渉し合う。
繰り返しになるが、最初の悪い推測を引き上げるべき乗を探しているのである。この指数化された項$g^p$から大数の項$m*N$を引くとき、余りが1、つまり$g^p - m*N = 1$が必要である。つまり、我々のシステムは次のようになる。
べき乗の重ね合わせを指数に入力する：
x, g^xrangle .$$$.
指数の重ね合わせを大数の項の差に入力し、余りを求める：
x, g^xrangle ￤ライトアロー [>m*N] ￤ライトアロー ￤x, +rrangle .$$.
そして、この余りが1になるようにする。
ここでは、指数とモジュラー算術の構造的な関係を利用する。
g^x = m*N + r ⅳrightarrow g^{x+p} = m_1*N + r ⅳrightarrow g^{x+2p} = m_2*N + r$$.
余りは指数の線形変化に関係なく同じままであり、これはある周期で繰り返される性質があることを意味する。この例では、異なる累乗が異なる余りを作り、同じ余りを持つように組み合わされている。
g^{p+10} = g^pg^{10}$$ である。
$$ = (mN + 2)(m_1N + 4)$$ である。
mm_1N^2+4mN+2m_1N+8$$ である。
N + 4 $$ = (mm_1frac{N}{2}+2m+m_1)N + 4Rightarrow text{something}.N + 4 $$
$$ = (mm_1frac{N}{4}+m+frac{m_1}{2})N + 2RightarrowN + 2.$$
ある重ね合わせをシステムに入力し、その余りを測定すると、その余りだけをもたらすすべての可能なべき乗の重ね合わせが得られる。そして、この残りの重ね合わせは、$p$乗の周期で繰り返されるか、$f=frac{1}{p}$の周波数を持つ。
古典的なフーリエ変換が、時間の関数としての波を周波数の関数に変換するように、量子フーリエ変換（QFT）も、入力の周波数を持つ出力としての重ね合わせを行う。
つまり、QFTに単一の状態を入力すると、出力は重みや確率の異なる状態の重ね合わせとなり、入力状態を周波数とする波を形成する。また、QFTに複数の状態を入力すると、出力は重ね合わせの重ね合わせになり、破壊的干渉と建設的干渉によって重ね合わせが1つの波になる。そして、QFTへの入力が周期$p$の重ね合わせであれば、破壊的干渉は$frac{1}{p}$しか残さない。
ここから、より良い推測値$g^{frac{p}{2}}を計算する。± 1$ を計算し、必要に応じて反復する。
今日の量子コンピューターは、15や21のような小さな数の因数分解しかできない。断熱的量子計算（AQC）のようなより洗練された技術では、RSAに使われる最小の数の因数分解に5900量子ビットを必要とする。
それは何か
ショールのアルゴリズムは、大きな数の素因数を多項式時間で求めるアルゴリズムである。サイバーセキュリティでは、一般的な暗号化技術にRSA（Rivest-Shamir-Adleman）がある。RSAは、秘密にされている2つの大きな素数の積である公開鍵に基づいている。RSAは、コンピュータが非常に大きな数をその素数成分に因数分解できないという仮定に基づいている。因数分解は、足し算や掛け算とはまったく異なる種類の問題解決だからだ。ショールのアルゴリズムは、量子力学的な重ね合わせと干渉の性質を利用して、可能性のある解を素早く探索する。
For example, according to Thorsten Kleinjung of the University of Bonn, it would take 1 or 2 years to factor N = 13506641086599522334960321627880596993888147560566702752448514385152651060485953383394028715057190944179820728216447155137368041970396491743046496589274256239341020864383202110372958725762358509643110564073501508187510676594629205563685529475213500852879416377328533906109750544334999811150056977236890927563 on a 2.2 GHz Athlon 64 CPU PC with ≤ 2 GB memory.
ショールのアルゴリズムは、あらゆる素数を因数分解する可能性を秘めた強力なツールであり、その使い手は現在の暗号の多くを破ることができる。現在のNISQ量子コンピュータでは、RSA暗号を破るにはまだ不十分だが、専門家は数年以内に可能になると見積もっている。実際、ショールのアルゴリズムは量子コンピューターへの大きな関心を呼び起こした。
ショールのアルゴリズムは、10年以内に量子アニーリングデバイス（最適化用途に特化した非普遍的な量子コンピューター）上で実行できるようになるだろうという予測もあるが、この計算には多くの要素が含まれている。これは、1年おきにアニーリング量子ビットの数が、過去に起こったように倍増すると仮定したものだが、この計算に全面的に頼ってはいけない。アニーリング量子ビットの進歩は、この時間枠を遅らせる様々な障害によって妨げられる可能性がある。あるいは、アニーリングやユニバーサル量子コンピューティングの継続的な研究によって、このプロセスを加速させるより優れたアルゴリズムや技術を明らかにするブレークスルーがもたらされる可能性もある。
RSA暗号が使い物にならなくなるという深刻さだけでなく、この時間軸の不確実性は、隣接する分野や政府からも注目を集めている。最近、ポスト量子暗号（PQC）の標準と枠組みを作り、量子耐性アルゴリズムを開発するスケジュールを定めた米国の大統領令は、このセキュリティ侵害がいかに深刻かを示している。データがあるところには、セキュリティの必要性がある。世界中の企業のCIO/CTOは、ショーのアルゴリズムの影響を学んだ後、量子に投資しており、多くの場合、他のアプリケーションで量子の能力を強化し、量子の旅を始めるのを待っている企業よりも優位に立っている。例えば、ユナイテッドヘルス・グループは3大陸に量子チームを持ち、量子暗号からスタートした後、量子機械学習による人工知能アプリケーションの調査を始めている。
仕組み
ショールのアルゴリズムの本質は、RSA鍵を含む関数の周期を見つけることによって、誤った因子の推測をより良いものに変えることにある。
因数分解する大きな数$N$と、最初の推測$g$から始める。g$は$N$の因数であるか、$N$と共通の因数である。この場合、ユークリッドのアルゴリズム、またはより高速なユークリッド・アルゴリズム（それぞれ、引き算やモジュロを使って、共通因数を調べたり見つけたりする方法）のおかげで解決する。N$の因数を求めるには、厳密に因数を当てる必要はなく、$N$と因数を共有するものでもよい。
もし $g$ が $N$ の因数でも共通因数でもなければ、この推測をよりよいものに変換することに移る。A$ と $B$ の2つの整数について、$A^p = m*B +1$ となるべき乗 $p$ と倍数 $m$ が存在する。これをいくつかの素数、例えば3と7で示すことができる。
$3^2 = 9 = 1*7 + 2$
$3^3 = 27 = 3*7 + 6$
$3^4 = 81 = 11*7 + 4$
$3^5 = 243 = 34*7 + 5$
$3^6 = 729 = 104*7 + 1$
この関係は、私たちが問題を違った角度から見る助けとなる。
We can write our relationship with our terms: $g^p = m*N +1$. Once we subtract 1 from both sides, getting $g^p-1 = m*N$, we can rewrite this as $(g^{\frac{p}{2}} + 1)(g^{\frac{p}{2}} - 1) = m*N$, as this is a difference of two squares. This looks more like two factors of $N$, for which we are searching, so instead of searching for a better guess $g$, we will now search for a power $p$.
そこで量子コンピューターが活躍する。可能性のある力の重ね合わせを巧みに構築し、すべての不正確な推測が互いに破壊的に干渉し合う。
繰り返しになるが、最初の悪い推測を引き上げるべき乗を探しているのである。この指数化された項$g^p$から大数の項$m*N$を引くとき、余りが1、つまり$g^p - m*N = 1$が必要である。つまり、我々のシステムは次のようになる。
べき乗の重ね合わせを指数に入力する：
x, g^xrangle .$$$.
指数の重ね合わせを大数の項の差に入力し、余りを求める：
x, g^xrangle ￤ライトアロー [>m*N] ￤ライトアロー ￤x, +rrangle .$$.
そして、この余りが1になるようにする。
ここでは、指数とモジュラー算術の構造的な関係を利用する。
g^x = m*N + r ⅳrightarrow g^{x+p} = m_1*N + r ⅳrightarrow g^{x+2p} = m_2*N + r$$.
余りは指数の線形変化に関係なく同じままであり、これはある周期で繰り返される性質があることを意味する。この例では、異なる累乗が異なる余りを作り、同じ余りを持つように組み合わされている。
g^{p+10} = g^pg^{10}$$ である。
$$ = (mN + 2)(m_1N + 4)$$ である。
mm_1N^2+4mN+2m_1N+8$$ である。
N + 4 $$ = (mm_1frac{N}{2}+2m+m_1)N + 4Rightarrow text{something}.N + 4 $$
$$ = (mm_1frac{N}{4}+m+frac{m_1}{2})N + 2RightarrowN + 2.$$
ある重ね合わせをシステムに入力し、その余りを測定すると、その余りだけをもたらすすべての可能なべき乗の重ね合わせが得られる。そして、この残りの重ね合わせは、$p$乗の周期で繰り返されるか、$f=frac{1}{p}$の周波数を持つ。
古典的なフーリエ変換が、時間の関数としての波を周波数の関数に変換するように、量子フーリエ変換（QFT）も、入力の周波数を持つ出力としての重ね合わせを行う。
つまり、QFTに単一の状態を入力すると、出力は重みや確率の異なる状態の重ね合わせとなり、入力状態を周波数とする波を形成する。また、QFTに複数の状態を入力すると、出力は重ね合わせの重ね合わせになり、破壊的干渉と建設的干渉によって重ね合わせが1つの波になる。そして、QFTへの入力が周期$p$の重ね合わせであれば、破壊的干渉は$frac{1}{p}$しか残さない。
ここから、より良い推測値$g^{frac{p}{2}}を計算する。± 1$ を計算し、必要に応じて反復する。
今日の量子コンピューターは、15や21のような小さな数の因数分解しかできない。断熱的量子計算（AQC）のようなより洗練された技術では、RSAに使われる最小の数の因数分解に5900量子ビットを必要とする。
