量子計算機の応用 一覧

因数分解を行いたい正の整数を$N$とする。
この数を$N=mn$と、二つの1より大きい整数$m, n$の積でかけることを見つけたい。

まず$N$と互いに素である正の整数$x$を探す。$x$を見つけるには次のようにする。


  1. 適当な整数$x(x < N)$をとってくる。

  2. もとの数$N$と新しくとった$x$の最大公約数を計算する。
    (最大公約数を効率よく計算するユークリッドの互除法という名のアルゴリズムが存在するので、これはすばやく行える。)

  3. それが$1$なら目的の$x$である。(もし$1$でないなら、その公約数は$N$の因数であるので、因数分解ができたことになる。)


このように決めた$x$を用いて、
\begin{align}
x^r-1 \equiv 0 \bmod N \label{eq:xr}
\end{align}
となる整数$r$を探す。

この$r$を探す部分が、古典的には効率よく計算できず、量子計算によって
効率よく計算できる部分である。
これについては次の節で述べる。

$r$が計算できたとして、次にこの$r$について
以下の条件が満たされているかどうかをチェックする。


  1. $r$は偶数である。

  2. 1の条件のもとで、さらに次の二式が成立する。
    \begin{align}
    x^{\frac{r}{2}} \neq 1 \bmod N \label{eq:+1} \\
    x^{\frac{r}{2}} \neq -1 \bmod N \label{eq:-1}
    \end{align}


この条件が成り立つかどうかは、効率的に計算することができることが知られている。

この条件が満たされなかったときには、
別の整数$x$を探して、再び$r$を計算し、条件を満たす$x$が見つかるまで繰り返す。

ある$x$を選んだとき、条件を満たす確率は$1/2$以上であることが、
ある定理によって示されているので、この試行はすぐに終えることができる。

このようにして条件を満たす$x$を探し出したとすると、
式(\ref{eq:xr})は、$r$が偶数であることより
\begin{align}
& (x^{\frac{r}{2}}-1)(x^{\frac{r}{2}}+1) \equiv 0 \bmod N \\
& (x^{\frac{r}{2}}-1)(x^{\frac{r}{2}}+1) = kN \qquad (kは整数) \label{eq:kN}
\end{align}
と変形することができる。一方、上の(\ref{eq:+1})(\ref{eq:-1})から
\begin{align}
& (x^{\frac{r}{2}}-1) \neq k'N \label{eq:k'N} \\
& (x^{\frac{r}{2}}+1) \neq K''N \label{eq:k''N}
\end{align}
となる。よって、$(x^{\frac{r}{2}}-1)=p,(x^{\frac{r}{2}}+1)=q$とおくと、
$p,q$は$N$の整数倍ではないことがわかる。

$(x^{\frac{r}{2}}-1)=p,(x^{\frac{r}{2}}+1)=q$を(\ref{eq:kN})に代入すると、
\begin{align}
pq=kN
\end{align}
これより、$p,q/k$、あるいは$p/k,q$が$N$の因数であることがわかる。

以上より、(\ref{eq:xr})を満たす$r$を効率よく見つけることができれば、
因数分解が行えることがわかった。

続いて、これが量子計算を用いて計算できることを示し、
さらにそれが効率よく行えることを示す。

古典計算機で大きな整数を因数分解しようとすると、
効率よく解くことができない。

効率よく解けないということは、整数$N$が大きくなると、
計算に時間がかかって、事実上解けなくなることを意味する。

簡単な例としては、$N$の因数を発見するために小さい数からはじめて
$N$が割り切れるかどうか調べて、ちょうど真ん中の
$\sqrt{N}$まで調べればよいことが知られていて、$\sqrt{N}$回程度の計算を要する。

現在まで知られている一番速いアルゴリズムでも、
$\exp \left[ c \log N \left( \frac{\log \log N}{\log N} \right) ^\frac{2}{3} \right]$ステップ程度かかり、
指数時間よりは速いが多項式時間よりは遅い。

このことを逆手に取ったものが素数を鍵に用いる公開鍵方式の暗号システムである。

量子計算機を用いれば、因数分解を圧倒的に速く実行できることをショアが示した。
以下でその概要を説明する。

フーリエ変換を、上で述べた量子論理回路で実行することを考える。
これを量子フーリエ変換と呼ぶ。

有限個の量子ビットを用いるので、離散的なフーリエ変換となる。
$2^n$項の離散的なフーリエ変換を実行するのに、逐次的にわずか$n$回程度の制御Uで
実現できるところがポイントである。

$n=3$の場合を図2.1に示す。始状態は$|0\rangle|0\rangle|0\rangle$とし、
まずそれぞれのビットにアダマール変換を施す。
\begin{align}
|0\rangle|0\rangle|0\rangle \longrightarrow \left( \frac{1}{\sqrt{2}} \right)^3
( |0\rangle +|1\rangle )^3
\end{align}
8個の状態を$|0)=|0\rangle|0\rangle|0\rangle,|1)=|0\rangle|0\rangle|1\rangle,\cdots,|7)=|1\rangle|1\rangle|1\rangle$
とラベルすると、入力は$\sum_{a=0}^7 |a)$と書ける。

さらに補助ビット$|0\rangle$を書き加えて、以下のようになる。
\begin{align}
\left( \frac{1}{\sqrt{2}} \right)^3 \sum_{a=0}^7 |a) |0\rangle
\end{align}
続いて図のように、$|a)$の各ビットを制御ビットとし、
補助ビット$|0\rangle$を標的ビットとした制御U演算がかかる。

補助ビットにかかる演算は
\begin{align}
U(m)|0\rangle = \exp \left(\frac{2\pi i}{2^3}m \right) |0\rangle \\
U(m)|1\rangle = |1\rangle \label{eq:muimi}
\end{align}
この演算は補助ビットの前の係数を変えるだけなので、
補助ビットをはじめ$|0\rangle$にしておけば、ずっと$|0\rangle$のままとなる。
よって(\ref{eq:muimi})は実質意味を持たない。

この制御Uは8個の重ね合わせの状態にかかるので、8個の状態すべてに演算される。
例として$|5)=|1\rangle|0\rangle|1\rangle$について考えてみる。

それぞれのビットが制御ビットとなっているから、
第1ビットと第3ビットのU演算$U(1),U(4)$のみが補助ビット$|0\rangle$にかかり、
$U(2)$は演算されない。

よって、
\begin{align}
|5)|0\rangle = |1\rangle|0\rangle|1\rangle \cdot |0\rangle \longrightarrow & |1\rangle|0\rangle|1\rangle U(1)U(4)|0\rangle \\
=& |1\rangle|0\rangle|1\rangle \exp \left(\frac{2\pi i}{2^3}1 \right) \exp \left(\frac{2\pi i}{2^3}4 \right) |0\rangle \\
=& \exp \left(\frac{2\pi i}{2^3}5 \right) |1\rangle|0\rangle|1\rangle \cdot |0\rangle \\
=& \exp \left(\frac{2\pi i}{2^3}5 \right) |5)|0\rangle
\end{align}
となる。他の項も同様にして変換され、全体としては
\begin{align}
\left( \frac{1}{\sqrt{2}} \right)^3 \sum_{a=0}^7 |a) |0\rangle \longrightarrow
\left( \frac{1}{\sqrt{2}} \right)^3 \sum_{a=0}^7 \exp \left(\frac{2\pi i}{2^3}a \right) |a)|0\rangle
\end{align}
変換される。

この変換に必要なステップ数は、並列して行っているので、
アダマール変換で1ステップ、制御U演算で3ステップで、$1+3\sim 3$ステップ程度で済む。

clip009.jpg

図2.1:量子フーリエ変換(n=3のとき)

一般の$n$ビットの場合のフーリエ変換も同じようにして作ることができて、
補助ビット$|0\rangle$を省いて書けば
\begin{align}
\left( \frac{1}{\sqrt{2}} \right)^n \sum_{a=0}^{2^n-1} \exp \left(\frac{2\pi i}{2^n}a \right) |a)
\end{align}
と書ける。
量子回路も図\ref{fig:fou}を拡張すればよい。

必要なステップ数は、$n=3$の例からわかるように
$\sim n$ステップ程度である。

さらに上の量子フーリエ変換の拡張として、
絡み合った量子フーリエ変換を構成することができる。

$n=3$の場合を図\ref{fig:en}に示す。
重ね合わせ状態をつくっているビット群$|a)$のほかに、
第2ビット群$|c)$を用意する。

この第2ビット群のビット数は$|a)$の方のビット数とそろえておく。
つまり、3ビットの場合には、$|a),|c)$ともに
$|0\rangle|0\rangle|0\rangle$から$|1\rangle|1\rangle|1\rangle$までの8とおりの状態を表す。
この回路によって、
\begin{align}
\left( \frac{1}{2} \right)^3 \sum_{a=0}^7 \sum_{c=0}^7 \exp \left(\frac{2\pi i}{2^3}ac \right) |a)|c\rangle
\end{align}
という状態を作ることができる。
これは、上の量子フーリエ変換の議論と同様に確かめることができる。

この絡み合ったフーリエ変換の構成にかかるステップ数は、
アダマール変換は1ステップ、制御制御U演算が$9=3^2$ステップで、$1+3^2\sim 3^2$程度である。

一般に$n$ビットの場合は
\begin{align}
\left( \frac{1}{2} \right)^n \sum_{a=0}^{2^n-1} \sum_{c=0}^{2^n-1} \exp \left(\frac{2\pi i}{2^n}ac \right) |a)|c\rangle
\end{align}
である。必要なステップ数は$\sim n^2$程度である。

この絡んだ量子フーリエ変換は、
後述するショアによる因数分解のアルゴリズムにおいて重要な役割を果たす。

clip010.jpg

図2.2:絡んだ量子フーリエ変換(n=3のとき)

このページの上部へ