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

ぶっちゃけすべてわかった気もするし、何もわかっていない気もする。

第二章の内容

第一章では量子情報でよく使われるブラケット記法の練習や基本的な量子ビット系の計算を学んだ。第二章では一章をふまえて量子計算と量子回路を学んでいく。

計算量

どの分野でも嫌というほど見る気がする。ある問題に対する大雑把な計算回数を示したものであり、 $O(n)$ などで表記する。 $O$ と $Ω$ の違いに注意する。

古典回路モデル

古典回路モデルはよく知られているデジタル回路の一番基礎に当たるものである。具体的にはAND,OR,NOT演算子の組み合わせによって関数を実現することを目的とする。この時できる限り少ない演算子の組み合わせで関数を作りたいと考える。例えば、与えられたビット列の立っているビットの数の偶奇を判定する関数は $O(n)$ で作成可能だ。ここではあまり古典回路モデルを注視することはなかったが、いくつかの定理を紹介している。「nビット入力1ビット出力関数の回路計算量の最大は $5・2^{n-1}-4$ 」、「前述の関数に関して、ある関数の回路計算量は少なくとも $2^n/2n$ 」などの定理の紹介の紹介がなされているが、むしろ証明のほうが興味深かった。本証明中で使用されたnビット入力1ビット出力関数の数と素子数s以下で構成可能な回路の数を比較する考え方は頑張って慣れていきたい。

量子回路モデル

本章の主題である量子モデルをやっていく。基本的に古典回路モデルと同じように「素子」を組み合わせて作っていくのだが、使うビットが量子ビットであること、量子ビットの変換は「測定」と「ユニタリ変換」でしか行えないことに注意しなくてはならない。ここで一章で紹介されたユニタリ行列を実際に使っていくようになる。例えば $σ_x$ は $σ_x|0\rangle=|1\rangle$ となることからNOT演算子のように使えるようになる。またHadamard変換は量子計算において重要な意味を持つ。このように入出力長が決められてあたかも演算子のようにふるまうユニタリ行列を量子素子と呼ぶ。

f:id:zekehamp:20210218011534p:plain — Hadamard変換後、制御NOT素子を加えた量子回路

このように量子回路を記述することもできる。個人的には数式をたどるよりもこういった図を介した説明のほうがわかりやすいと思う。また量子計算を行う上で注意しなければいけないことが二つある。

ユニタリ行列は可逆であり逆演算が存在する。
$(U\otimes V)|\phi,\psi\rangle=U|\phi\rangle \otimes V|\psi\rangle$

一つ目はユニタリ行列を示していて、これはたとえユニタリ変換後の量子ビットが必要なくても可逆性を満たすために残さなくてはならないことを示唆する。二つ目は二種類のユニタリ変換を量子ビット列に適用した場合、ユニタリ行列同士のテンソル積抜きで計算する手法を提案したものである。

さてここまで量子計算の基礎が説明されたが、量子回路中でよく使われる量子素子が存在する。それが制御NOT素子(CNOT素子である)とHadamard素子である。

$CNOT=\left( \begin{array}{ccc} 1,0,0,0\\0,1,0,0\\0,0,0,1\\0,0,1,0\end {array}\right)$

f:id:zekehamp:20210218020308p:plain — CNOT演算子

この演算子は1-量子ビットが $|1\rangle$ の時2-量子ビットを反転させる性質を持つ。一方Hadamard素子は $H|0\rangle=1/\sqrt{2}(|0\rangle+|1\rangle)$ 、 $H|1\rangle=1/\sqrt{2}(|0\rangle-|1\rangle)$ を満たす。すなわち等振幅の重ね合わせを実現することができる。

Z-Y分解

任意のユニタリ行列は $R_x,R_y,R_z$ のうち二つを利用して表現することができる。これらのユニタリ行列はBloch球上のX軸、Y軸、Z軸回転で使用されていた。極座標を考えると定性的に成り立つことがわかる。

量子回路の定式化

先ほどよく使う素子としてCNOT素子が紹介されたが、制御ビットを2つに増やしたCCNOT素子というのが存在する。これは二つの制御ビットが両方 $|1\rangle$ の場合のみ3ビット目が反転する性質を持つ。

f:id:zekehamp:20210218030226p:plain — CCNOT素子

これをうまく使うと古典回路モデルにおける大体の論理演算子を模倣することができる。具体的には

$CCNOT(x_1,x_2,x_3)=(x_1,x_2,(x_1 \land x_2)\oplus x_3)$ と書ける。
$CCNOT(1,1,x_3)=(1,1,\lnot x_3)$ はNOTの模倣。
$CCNOT(x_1,x_2,0)=(x_1,x_2,x_1 \land x_2)$ はANDの模倣。
ドモルガンの法則よりNOTとANDからORを作ることができる。

となる。

またCCNOTを使用した量子回路として以下のように書ける。

ビット入力1ビット出力関数fを回路サイズs(n)の論理回路で計算可能な任意の関数としたとき、

$U_f|x\rangle|0\rangle|011\rangle|0^{l(n)}\rangle=|x\rangle|f(x)\rangle|011\rangle|G(x)\rangle$ を満たすCCNOT素子からのみからなる量子回路 $U_f$ が存在する。ただし $G:\{0,1\}^n\rightarrow\{0,1\}^{l(n)}$ 、 $l(n)=O(s(n)+n)$ 。

ここでケットを連続しているのはテンソル積を示している？本文中に言及を見つけられなかった…

これを量子回路として書くと

f:id:zekehamp:20210218032335p:plain

こんな感じ(手書き)。この時にユニタリ行列が可逆であったことを思い出さなくてはならない。ゆえに、G(x)が必要のない量子ビット列として出てくるのにもかかわらず、中身がわからないので分離することができない。ここで知りたいのはf(x)なので、どうにかしてG(x)を別のビット列に変えたい。

そこで、以下のような回路を考える。

f:id:zekehamp:20210218032626p:plain

これをまとめると、

$U_f'|x\rangle|0\rangle|0\rangle|011\rangle|0^{l(n)}\rangle=|x\rangle|f(x)\rangle|0\rangle|011\rangle|0^{l(n)}\rangle$ となる。なお、 $U_f'$ は $U_f$ を二つとCCNOTを二つ含んでいる。これでf(x)以外がわかっている状態となるので、測定によって分離することができる。

この章を終えて

この章で量子回路の基礎を学んだ。個人的には最後の論理回路の理解に手間取った。しかし、どこか古典回路に似通った部分があって若干安心感がある。それでも新しい概念がポンポン出てきて、それらの概念をベースに理論が展開しているので奇妙なSF小説を読んでいるかのような印象を受ける。古典回路はトランジスタを最小単位としているため、トランジスタを実際に見ることができるという面では古典回路は現実に即しているのだと納得することができるのだが、こっちはつい最近まで存在すら明らかになっていなかった量子ビットを考えなくてはならない。あまりにも常識を逸脱しているのと実際に実験できないのも相まって、巷の似非量子科学者と大差ないような理解をしているのではないかと不安になってしまう。それでも量子世界を少しでも解き明かしてみたい。三章もこの調子でやっていきたい。