量子情報科学入門　読書記録　~第三章~

第三章の内容

第三章では第二章までの内容を踏まえて量子アルゴリズムを導入する。古典的に考えれば指数時間になるような計算を、多項式時間で解いたりすることが可能になるかもしれない可能性がある。

Deutsch-Jozsaのアルゴリズム

Deutsch-Jozsaのアルゴリズムが扱う問題は以下のとおりである。

バランス関数判定問題
入力: $f: \{ 0,1\}^n→\{0,1\}$ ただし、 $f$ はバランス関数か定数関数であることが保証されている

出力: $f$ が定数関数ならば0,バランス関数なら1

バランス関数というのは $2^n$ 個のありうる入力のうち $2^{n-1}$ 個の入力に対して0を $2^{n-1}$ 個の入力に対して1を出力をする関数である。前提としてこの関数はオラクルといって中身はブラックボックスであり、この関数への質問回数を全体の計算量とする。古典的に考えるならば、この問題を解くには最悪 $2^{n-1}+1$ 回質問しなくてはならない。しかし、Deutsch-Jozsaのアルゴリズムは1回の質問だけで確率1で正しい出力をする。

f:id:zekehamp:20210315040237p:plain

なんとも不思議な話だ。ユニタリ変換とアダマール変換をすることで、定数関数だった場合確実に0...0を得るのだ。これについては計算をするとちゃんとできていることが証明できるのだが、筆者は以下のような説明をしている。

f:id:zekehamp:20210315040241p:plain

ユニタリ作用後の状態は、定数関数とバランス関数とで直交の関係を満たす。この時、ユニタリ行列は基底変換をすることができるので、片方を0...0にするように変換すれば、もう片方は0...0と直交した状態、つまりは0...0以外の状態に変換されるのだ。このことから、一般的に入力状態を区別したいもの同士で直交した状態に変換することができれば効率よく正答を得ることができることがわかる。すげえ(小並感)。

Groverのアルゴリズム

先ほどのバランス関数判定問題は量子アルゴリズムの優位性を証明する、悪くいってしまえば都合のいい問題提起であった。対してGroverのアルゴリズムが扱う問題はより汎用的なものとなる。

Groverの探索問題

入力: $f: \{ 0,1\}^n→\{0,1\}$ 、ただし $f(x_0)=1$ となる解 $x_0\in \{0,1\}^n$ がただ一つ存在する。

出力: $f(x_0)=1$ を満たす解 $x_0$

古典的に考えると、最悪 $2^n-1$ 回の質問をしないといけないことがわかる。ラン宅アルゴリズムでも $O(2^n)$ かかるらしい(Yaoの原理)のだがよくわからかったので飛ばす。とにかくGroverのアルゴリズムでは $O( \sqrt{2^n} )$ で済むらしい。しかしこれは $1-1/{2^n}$ の確率で正しく $x_0$ を出力するという制約がつく。※ $N=2^n$ と表記することがある。

f:id:zekehamp:20210315042850p:plain

よく見ると、Deutsch-Jazsaのアルゴリズムと最初の部分は似ているが途中で $D_N$ という変換が加えられている。これは拡散行列といって対角成分が $-1+2/N$ で他が $2/N$ の行列である。この行列は $-1$ 成分のみを増幅するという特徴があり、これを用いて[x_0]の成分だけを増幅することができる。ここでも、入力状態を注目したいものとそれ以外で直交化とまではいかないが、差別化することに成功している。これを適切な回数を繰り返すことで、目的の値を高確率で得ることが可能になる。

これをベクトルとして可視化する解説されていたのがわかりやすかったので紹介する。

f:id:zekehamp:20210315053858p:plain

f:id:zekehamp:20210315053903p:plain

$|φ_0\rangle$ よりも $|φ_1\rangle$ のほうが $|x_0\rangle$ 基底ベクトルに近づいていることがわかる。

Shorのアルゴリズム

Shorのアルゴリズムは一定の衝撃を社会に与えた。というのも、Shorのアルゴリズムは素因数分解の計算困難性をひっくり返すアイデアであり、既存の暗号技術の破れにつながる可能性があったのである。しかし、今現在は多量子bit系を再現する実験段階だそうで実践段階ではない。

Shorのアルゴリズムの前に導入前に周期発見問題を導入しなくてはならない。

周期発見問題

入力: $f(a)=f(a+s mod N)=f(a+2s mod N)...$ を満たす $f$ 。ただし $N\in\mathbb{N}$ はある値 $s\in \mathbb{N}$ で割り切れる。

出力: $s$ 。

言ってみればfは周期関数だから、その周期を求めてほしいというものである。

f:id:zekehamp:20210315060519p:plain

このようなアルゴリズムで求めることができる。ここで大事になってくるのが量子フーリエ変換である。 $F|a\rangle=1/\sqrt{N}\sum_{k=0}^{N-1}exp(2ak\pi i/N)|k\rangle$ を満たす変換であり、ユニタリ行列でもある。

この量子フーリエ変換の役割を具体例を用いて説明すると、

f:id:zekehamp:20210315202639p:plain

となる。こうして $N/s$ の倍数に当たる状態を得ることができるのだ。これも所詮ユニタリ行列なので、基底変換したに過ぎない結果であることに注意しなくてはならない。さあ、これで $N/s$ の倍数がランダムで得られるので何回か試行して、そのGCDをとってあげれば $N/s$ を求めることができそうである。

さて素因数分解をやっていく。

素因数分解問題

入力: $n$ ビット長の $N$ ,ただし $N=pq(p,qは素数)$

出力: $p,q$

一つ確認しないといけないことがある。それは、 $N$ と互いに素な整数 $x$ について $x^r\equiv 1 \, mod \, N$ を満たす最小の $r$ を見つけることができれば素因数分解することが簡単にできるという事実である。

以下のような手法で解ける。

f:id:zekehamp:20210315205202p:plain

意外と簡単にできるもんなんだなと思ったり。

この章を終えて

この章では3つのアルゴリズムを学習した。少しだけ知っていたShorのアルゴリズムの正体を知ることができて少し満足した。この章は結構計算が多く理解するのに時間がかかった印象がある。特に周期発見アルゴリズムの理解が大変だった。記事執筆時は第四章に取り掛かっているのだが、本格的に理論体系を学ぶことになっており、いかに一回生のころに線形代数をさぼっていたかを身をもって体感している状態だったりする。最近、量子情報理論で日本最先端を行く藤井研究室にお邪魔しました。将来的には、こういった研究室で研究したいなとか思ったり。