量子アルゴリズム、ドイチのアルゴリズム - やさしくて平和な技術ぶろぐ

この前の続きです。

今回は制御の様子とアルゴリズム的な話です。
ドイチ・ジョザアルゴリズム(Deutsch-Jozsa algorithm)を1ビットで考えるドイチュのアルゴリズムです。入力 x = {0, 1} に対する関数 f(x) の出力が x に依存するか依存しないかを、関数への問い合わせ回数一回で確かめることが出来ます。
f:id:castlejou:20151113231436j:plain
簡単に言うと、この f(x) の表の4タイプのうち、青いタイプか赤いタイプかが f(x)を一度確かめるだけで分かりますよーってこと。

前回の話では磁場をかけることでスピンを制御することが出来るとこまで行きました。その磁場のかけ方(時間や強度)を調整することで、量子コンピュータで必要な演算(例えば状態|0>を重ね合わせ状態|0>+|1>に変換する演算とか)を実行できます。そういった演算子と処理の流れを電気回路に置き換えて表現できます。

先にドイチのアルゴリズム全体の量子ゲートを見てみましょう。左側が入力で右側が出力です。

f:id:castlejou:20151113232813j:plain

図のHの箱で表されてるゲートはアダマール変換という1キュービット用のゲートです。そもそものスピンの状態がベクトルで表されているため、演算子は行列表記です。

${ H = \left( \begin{array}{cc} 1 & 1 \\ 1 & -1 \end{array} \right) }$

例えば状態|0>や|1>をアダマール変換すると

${ H \left | 0 \right \rangle = \dfrac{\left | 0 \right \rangle + \left | 1 \right \rangle}{\sqrt{2}},　 H \left | 1 \right \rangle = \dfrac{\left | 0 \right \rangle - \left | 1 \right \rangle}{\sqrt{2}} }$

となり、重ね合わせ状態を作ることが出来、入力状態は

${ \left | \phi \right \rangle = \dfrac{1}{2}(\left | 0 \right \rangle \left | 0 \right \rangle - \left | 0 \right \rangle \left | 1 \right \rangle + \left | 1 \right \rangle \left | 0 \right \rangle - \left | 1 \right \rangle \left | 1 \right \rangle ) }$
となります。

次はUfっていう箱ですが少しややこしいです。まず制御NOTゲートという2キュービット以上用のゲートを説明します。これは第一キュービットが0なら第二キュービットはそのまま、第一キュービットが1なら第二キュービットは反転させます。(のでmod計算記号⊕を使って|x>|y> → |x>|y⊕x>と書けます)

制御NOTゲートは以下の演算子で表されます。

${ CNOT = \left( \begin{array}{cccc} 1 & 0 & 0 & 0 \\ 0 & 1 & 0 & 0 \\ 0 & 0 & 0 & 1 \\ 0 & 0 & 1 & 0 \end{array} \right) }$

Ufの話に戻ります。例えば状態|00>(|0>|0>のこと)で f(x) がタイプ(1)の時、|0>|0> → |0>|0⊕f(0)> = |0>|0⊕1> = |0>|1>という計算をUfが行っています。|00>から|11>まで各入力状態に対して同様にUfを計算してしまいます。

そしてこの出力を第一、第二ごとのキュービットで再度アダマール変換すると第一キュービットが f(x) が青いタイプの時に|0>、 f(x) が赤いタイプの時に|1>、となります。詳しいとこは自分で解いてみてくださいｗ因数分解は必須です。

こうして、問い合わせが一回で分かるという目的が果たせます。

でもこのままでは連続的に時間発展出来ないので難しいですが時間発展演算子を考えていきます。(すみません書くのめんどくさくて画像です)
f:id:castlejou:20160218155417j:plain f:id:castlejou:20160218155633j:plain f:id:castlejou:20160218155630j:plain