数学
物理
量子コンピュータと量子通信
量子コンピュータ
More than 1 year has passed since last update.


はじめに

 主催者がなかなか記事を書かなくて本当に申し訳ありませんでした1。しかしながら、私がとても怠惰だったため、結局、24日になるまで何を書くか決めておらず(笑)、いろいろ考えた末どっちにしろ1日で勉強して書ける内容を書くしか無いという結論に達しました。実際、この内容は量子コンピュータの勉強している人以外からも少しは気になるのではないでしょうか。ということで、やっていきます(勉強していきます)。何か間違いなどあったら指摘して頂けるととてもありがたいです。


RSA暗号

最初にRSA暗号についておさらいする。


  1. 大きな2つの素数 $p$, $q$ を選び、$n = pq$ を計算する。

  2. $\varphi(n) = (p-1)(q-1)$と互いに素な奇数の自然数 $e$ を選ぶ。


  3. 自然数 $d$ を $de \equiv 1 \ {\rm mod} \ (p-1)(q-1)$ となるように選ぶ。2

このとき、公開鍵 $P = (e, n)$ を使って、以下のようにメッセージ $M$ を暗号化する。メッセージ $M$ は $\lfloor \log n \rfloor$ ビットだけからなると仮定する。3

$$ E(M) = M^e \ ({\rm mod} \ n)$$

復号化するときは、秘密鍵 $S = (d, n)$ を使って、

$$ D(E(M)) = E(M)^d \ ({\rm mod} \ n) $$

となる。これが復号化できるためには、ある整数 $k$ に対して $ed = 1 + k \varphi(n)$ であることが必要である。これらの話は暗号理論の本などで詳しく説明されているため、ここで詳細に立ち入ることはしないが、このように公開鍵でメッセージを暗号化しても、受け取る側が秘密鍵を知らない限りは復号化が出来ない。そして、その安全性は位数計算や素因数分解の難しさによるもので、傍受しても解読することは非常に難しいとされている。


RSA暗号を破るためには


位数を見つける

暗号化されたメッセージを解読しようとしたとき $M^e$ を受け取り、その暗号化に使われた公開鍵 $P=(e, n)$ も一緒に手に入れることができる。$(M^e)^r = 1 \ ({\rm mod} \ n) $ となる最小の正の整数 $r$ を見つけられたとする。このとき $r$ は $\varphi(n)$ を整除することを示すことができ4、$e$ と $\varphi(n)$ は互いに素なので、$\varphi(n)$ と $r$ も互いに素である。そのため、

$$ ed' = 1 + k r $$

となる $d'$ があり、暗号化されたメッセージを、

$$ (M^e)^{d'} \ ({\rm mod} \ n) = M^{1+kr} \ ({\rm mod} \ n) = M \ ({\rm mod} \ n) $$

のように復号化することが出来てしまう。実際に秘密鍵 $S = (d, n)$ を知らなくても、$(d', n)$ を知ることができればよく、$d'$ は $ed' = 1 \ ({\rm mod} \ r) $ を満たす整数で、$d$ は $ed = 1 \ ({\rm mod} \ \varphi(n))$ を満たす整数で、$ \varphi(n) $ は $r$ で割り切れるという関係になっている。しかし、これは位数発見の効率的な方法を知っている場合に使える方法であり、現在、古典アルゴリズムでそのような方法は知られていない。


素因数分解を行う

この方法は愚直に $n = pq $ を素因数分解して $p, q$ を調べて、$ \varphi(n) = (p-1)(q-1)$ を計算する。この場合、$ed = 1 \ ({\rm mod} \ n)$ となる $d$ を計算することが出来るので、秘密鍵 $S = (d, n)$ を完全に見つけることが出来る。しかし、大きな数の素因数分解を効率的に行える古典アルゴリズムは知られていない。

このようにRSA暗号を破るためには、位数を発見するか素因数分解を効率的に行わなければならない。実際、位数を計算することと素因数分解は密接に関係しており、効率的に位数を見つけることが出来れば素因数分解を行うことも可能である。


位相推定問題

$U$をユニタリ演算子として、

$$ U \left | u \right \rangle = e^{2 \pi \phi} \left | u \right \rangle $$

のとき、$\phi$ $(0 \le \phi < 1)$ を求める。また、$\phi$ を2進数で表したものを $0.\phi_1 \phi_1 \cdots \phi_n$ と書くことにする。

この問題を解くために以下のような量子回路を考える。$H$ はアダマールゲートを表す。この量子回路を使うと出力としてqubitで表現された位相$\phi$の値を量子離散フーリエ変換されたものが得られる。そのため、それを逆フーリエ変換してやることで求めたい位相$\phi$の値を得ることが出来る。下の図で $FT^{-1}$ は逆フーリエ変換を表す。

Screen Shot 2017-12-24 at 20.58.54.png

まず、$\left | 0 \right \rangle $ が $n$ 個並んだ状態がアダマールゲートに通るので、

$$ \frac{1}{\sqrt{2^n}} \left ( \left | 0 \right \rangle + \left | 1 \right \rangle \right ) \otimes \left ( \left | 0 \right \rangle + \left | 1 \right \rangle \right ) \otimes \cdots \otimes \left ( \left | 0 \right \rangle + \left | 1 \right \rangle \right ) \otimes \left | u \right \rangle $$

となる。また、$U_k = U^{2^k}$ と定義すると、

$$ U_k \left | u \right \rangle = e^{i 2 \pi 2^k \phi} \left | u \right \rangle $$

となるので、$U_0$ から $U_{n-1}$ までを通過したあとは、

$$ \frac{1}{\sqrt{2^n}} \left ( \left | 0 \right \rangle + e^{i 2 \pi 2^{n-1}} \left | 1 \right \rangle \right ) \otimes \left ( \left | 0 \right \rangle + e^{i 2 \pi 2^{n-2}} \left | 1 \right \rangle \right ) \otimes \cdots \otimes \left ( \left | 0 \right \rangle + e^{i 2 \pi 2^{0}} \left | 1 \right \rangle \right ) \otimes \left | u \right \rangle $$

となるが、ここで $\phi$ を2進数にすると、

$$ \frac{1}{\sqrt{2^n}} \left ( \left | 0 \right \rangle + e^{i 2 \pi 0.\phi_n} \left | 1 \right \rangle \right ) \otimes \left ( \left | 0 \right \rangle + e^{i 2 \pi 0.\phi_{n-1} \phi_n} \left | 1 \right \rangle \right ) \otimes \cdots \otimes \left ( \left | 0 \right \rangle + e^{i 2 \pi 0.\phi_1 \phi_2 \cdots \phi_n} \left | 1 \right \rangle \right ) \otimes \left | u \right \rangle $$

のように書くことができる。

 ここで量子離散的フーリエ変換について思い出してみる。量子フーリエ変換については他の方が記事にしてくださっているので詳細はそちらを参照して頂くとよいと思う。

n-qubitを今、$ \left | j \right \rangle = \left | j_1 j_2 \cdots j_n \right \rangle $ と表すと、これに対する量子離散フーリエ変換は、

$$ \left | j \right \rangle \to \frac{1}{\sqrt{2^n}} \sum_{k=0}^{2^n-1} e^{i 2\pi j k / 2^n} \left | k \right \rangle $$

という変換として書けるので、これを計算することで、

\begin{eqnarray}

\frac{1}{\sqrt{2^n}} \sum_{k=0}^{2^n-1} e^{i 2\pi j k / 2^n} \left | k \right \rangle
&=& \frac{1}{\sqrt{2^n}} \sum_{k_1=0}^1 \sum_{k_2=0}^1 \cdots \sum_{k_n=0}^1 e^{i 2 \pi j (2^{n-1}k_1 + 2^{n-2}k_2 + \cdots + 2^0 k_n) / 2^n} \left | k_1 k_2 \cdots k_n \right \rangle \\
&=& \frac{1}{\sqrt{2^n}} \left ( \left | 0 \right \rangle + e^{i 2 \pi 0.j_n} \left | 1 \right \rangle \right ) \otimes \left ( \left | 0 \right \rangle + e^{i 2 \pi 0.j_{n-1} j_n} \left | 1 \right \rangle \right ) \otimes \cdots \otimes \left ( \left | 0 \right \rangle + e^{i 2 \pi 0.j_1 j_2 \cdots j_n} \left | 1 \right \rangle \right )
\end{eqnarray}

となる。これは上でやった $\phi$ での結果と同じなので、$ \left | \phi_1 \phi_2 \cdots \phi_n \right \rangle $ をフーリエ変換したものが、

$$ \frac{1}{\sqrt{2^n}} \left ( \left | 0 \right \rangle + e^{i 2 \pi 0.\phi_n} \left | 1 \right \rangle \right ) \otimes \left ( \left | 0 \right \rangle + e^{i 2 \pi 0.\phi_{n-1} \phi_n} \left | 1 \right \rangle \right ) \otimes \cdots \otimes \left ( \left | 0 \right \rangle + e^{i 2 \pi 0.\phi_1 \phi_2 \cdots \phi_n} \left | 1 \right \rangle \right ) \otimes \left | u \right \rangle $$

となる。そのため、逆量子離散的フーリエ変換ゲートに通して得られた、$\phi_1 \phi_2 \cdots \phi_n$ を $2^n$ で割れば位相の値を得ることが出来る。

ここではqubitで表現できるように2進数表記をしたが、あとのために10進数表記も示しておく。

 最初のアダマールゲートを通った結果は、

\begin{eqnarray}

&& \frac{1}{\sqrt{2^n}} \left ( \left | 0 \right \rangle + \left | 1 \right \rangle \right ) \otimes \left ( \left | 0 \right \rangle + \left | 1 \right \rangle \right ) \otimes \cdots \otimes \left ( \left | 0 \right \rangle + \left | 1 \right \rangle \right ) \\
&=& \frac{1}{\sqrt{2^n}} \left ( \left |00...00 \right \rangle + \left |00...01 \right \rangle + \cdots + \left |11...11 \right \rangle \right ) \\
&=& \frac{1}{\sqrt{2^n}} \left ( \left | 0 \right \rangle + \left | 1 \right \rangle + \cdots + \left | 2^n - 1 \right \rangle \right ) \\
&=& \frac{1}{\sqrt{2^n}} \sum_{k=0}^{2^n-1} \left | k \right \rangle
\end{eqnarray}

となる。$k$ は10進数である。また、その後通る制御$U_k$ゲートを通ったあとは、

\begin{eqnarray}

&& \frac{1}{\sqrt{2^n}} \sum_{k=0}^{2^n-1} \left | k \right \rangle \otimes e^{i 2 \pi k \phi} \left | u \right \rangle \\
&=& \frac{1}{\sqrt{2^n}} \sum_{k=0}^{2^n-1} e^{i 2 \pi k \tilde{\phi} / 2^n} \left | k \right \rangle \otimes \left | u \right \rangle \\
\end{eqnarray}

のようになる。$ {\tilde \phi} = 2^n \phi$ と定義した。


位数計算

互いに素の$x$, $M (x < M)$ が与えられたとき、$x^r \ {\rm mod} \ M = 1$ を満たす最小の自然数 $r$ を位数という。

位数を計算するために、下のような $U$ と固有状態 $ \left | u_s \right \rangle$ を用意する。

$$ U \left | y \right \rangle = \left | xy \ {\rm mod} \ M \right \rangle $$

$$ U \left | u_s \right \rangle = e^{i 2 \pi j \frac{s}{r}} \left | u_s \right \rangle $$

ここで、

$$ \left | u_s \right \rangle = \frac{1}{\sqrt{r}} \sum_{j=0}^{r-1} e^{-i 2 \pi j \frac{s}{r}} \left | x_j \ {\rm mod} \ M \right \rangle $$

である。これが $U$ の固有状態になっていることを示すためには、$x^r \ {\rm mod} \ M = 1$ が必要である。これはふつうに計算すれば示すことができるので、ここでは認めて進めることにする。このような設定のもと、位相推定問題で見た量子回路を通せば位相 $ \frac{s}{r} $ を知ることが出来るのではないかと思うかもしれない。しかし、我々が求めたいのは$r$ の値が量子回路に入力する状態にも含まれているため、そもそも状態 $ \left | u_s \right \rangle $ をつくることが出来ない。そこで、以下の性質を使う、

$$

\frac{1}{\sqrt{r}} \sum_{s=0}^{r-1} \left | u_s \right \rangle = \left | 1 \right \rangle

$$

$ \left | u \right \rangle $ の代わりに、$ \left | 1 \right \rangle $ を使い、上の性質を使って適当な状態で測定することで状態を収縮させて欲しい値を得ることにする。

Screen Shot 2017-12-25 at 01.08.18.png

この量子回路に通した結果は、

\begin{eqnarray}

&& \frac{1}{\sqrt{2^n}} \sum_{k=0}^{2^n-1} \left | k \right \rangle \otimes U^k \left | 1 \right \rangle \\
&=&\frac{1}{\sqrt{r}} \sum_{s=0}^{r-1} \frac{1}{\sqrt{2^n}} \sum_{k=0}^{2^n-1} \left | k \right \rangle \otimes e^{i 2 \pi k \frac{s}{r}} \left | u_s \right \rangle \\
&=& \frac{1}{\sqrt{r}} \sum_{s=0}^{r-1} \left ( \frac{1}{N} \sum_{k=0}^{N-1} e^{i 2 \pi k \frac{\tilde s}{r} / N} \left | k \right \rangle \right) \otimes \left | u_s \right \rangle
\end{eqnarray}

となる。$\tilde{s} = 2^n s$, $2^n = N$ と定義した。

 このあと、$ \left | u_s \right \rangle $ の重ね合わせの状態のどれかを観測することで、エンタングルメントしている特定の状態が選び出される。したがって、上記の量子回路の上半分では、$ \frac{\tilde s}{r} $ を量子離散フーリエ変換された表す状態が得られるため、それを逆フーリエ変換することで $ \frac{s}{r} $ を求めることが出来る。ここから $r$ を得ることは容易であるため位数を求めることができる。また、この計算のステップ数は量子離散的フーリエ変換と同じオーダーであるため、古典アルゴリズムに比べて効率的であると言える。


素因数分解

最後に量子コンピュータを用いた素因数分解のアルゴリズムであるShorのアルゴリズムに触れておく。

耐えられた数 $M$ に対して、


  1. もし、$M$ が偶数であるならば素因数2を出力する。

  2. $M = a^b \ (a \ge 1, b \ge 2)$ かどうか確かめる。

    もし、そうであれば素因数 $a$ を出力。

  3. 1から $M-1$ の間で任意に $x$ を選ぶ

  4. $x, M \ (x < M)$ の位数 $r$ を計算する

  5. もし、$r$ が偶数であり、$x^{r/2} \ {\rm mod} M \neq -1 $ ならば、$x^{r/2}-1$ と $M$ の最大公約数と $x^{r/2}+1$ と $M$ の最大公約数を計算する。

    もし、これらのひとつが $M$ の因数なら、それを出力。そうでなければ、3に戻る。

という手続きを行うことで素因数分解を行うことが出来るのだが、4の位数の計算が古典アルゴリズムで効率的な計算方法が知られていない。前に説明したように量子離散的フーリエ変換を使った効率的な位数計算の方法があるため、素因数分解も効率的に行うことが出来る。

このように量子離散的フーリエ変換を用いて、位数計算、素因数分解(Shorのアルゴリズム)を実行することが出来るため、効率的にRSA暗号を破ることが出来てしまうのである。

というわけで、残念ながらここらへんで時間切れである。


終わりに

 本当は量子暗号や量子鍵輸送あたりの話までいきたかったのですが、時間がないのでまた機会があれば勉強したいと思います。

 量子コンピュータアドベントカレンダーを作って、最初は誰も参加してくれなかったらどうしようかと思ってましたが皆さんのおかげで無事全枠埋まりました。本当にありがとうございました。

 それでは、お休みなさい。けっこう展開が雑なので、時間があったらもう少し丁寧に書きたいと思います。


参考文献





  1. 言い訳をすると、体調崩して熱を出したりしておりました。 



  2. $d$ は拡張ユークリッドアルゴリズムで計算される。 



  3. 超える場合は $\lfloor \log x \rfloor$ を超えないブロックに分割する。