$$
\def\bra#1{\mathinner{\left\langle{#1}\right|}}
\def\ket#1{\mathinner{\left|{#1}\right\rangle}}
\def\braket#1#2{\mathinner{\left\langle{#1}\middle|#2\right\rangle}}
$$
はじめに
前々回の記事で、Multi-Controlled NOTゲートをグレイコードを使って構成する方法について示しましたが、なぜこれでうまくいくのか、十分に理解していなかったので、勉強しました。いろいろ自分なりに考えてみたのですが、やはり最後に頼るべきは先人の知恵ですね。以下の書籍に詳しく書いてありました。
また、これには、グレイコードを使った構成法以外にも、補助量子ビットを1つだけ使って、全体のゲート数を削減できる方法なども解説されていました。こちらも興味深いので、これも含めて説明したいのですが、長くなってしまうので、２回に分けます。今回の記事（その１）では、グレイコードによる補助量子ビット無しの構成法を説明し、次回の記事（その２）では、それ以外の方法について説明するようにします。というわけで、今回と次回はお勉強メモです。
ここで、最初に用語の定義をさせてください。「Multi-Controlled NOT」とこれまで言っていましたが、上の書籍では「Toffoliゲート」と呼んでいました(制御ビットが2ビットのものだけでなく、3ビット以上のものもひっくるめて)。また、標的側がNOTゲート(Xゲート)ではない、一般のユニタリゲートになっているものを「一般Toffoliゲート」と呼んでいました。いろいろ言い方はあるのだと思いますが、以後、こちらの用語を使うことにします。
制御ユニタリゲート
「一般Toffoliゲート」の説明に行く前に、制御ユニタリゲートの基本事項について確認しておきます。現在、便利なシミュレータが沢山あって、制御付きの回転ゲートとかを無邪気にひょいひょい使って、量子プログラミングしているかもしれませんが(はい、自分のことです、汗)、ハードウェア上にマッピングする際には、1量子ビットゲートとCNOTゲートに展開して、さらに最適化なんかやったりして、実行するはずです。当然、ゲート数が少ない回路設計の方が幸せになれますので、制御ユニタリゲートがどのくらいのゲートを消費するのかに、時折意識を向けておくのも悪くはない心がけです。それから、あとでnビットの一般Toffoliゲートが、nに対してどの程度のオーダーで量子ゲートを消費するのかを見ていきますので、そのための前準備という位置づけでもあります。
2量子ビット(制御:1,標的:1)
まず、ユニタリ行列の基本的な性質の確認です。$2 \times 2$のユニタリ行列$U$は、$ABC=I$となる、あるユニタリ行列$A,B,C$とパウリ行列$X$、および全体にかかる位相$\Phi(\delta)$を使って、
U = \Phi(\delta) A X B X C \tag{1}
と書くことができます。ここで、
\Phi(\delta) =
\begin{pmatrix}
e^{i\delta} & 0 \\
0 & e^{i\delta}
\end{pmatrix}
です。
なぜこれが成り立つかと言うと、任意のユニタリ行列$U$は、オイラー角を使って、
U = e^{i \delta} R_z(\alpha) R_y(\gamma) R_z(\beta) \tag{2}
のように書けて、
\begin{align}
A &= R_z(\alpha) R_y(\frac{\gamma}{2}) \\
B &= R_y(-\frac{\gamma}{2}) R_z(-\frac{\alpha + \beta}{2}) \\
C &= R_z(-\frac{\alpha - \beta}{2}) \tag{3}
\end{align}
とおくと(天下りですが)、$ABC = I$が成り立ち、かつ、
\begin{align}
AXBXC &= R_z(\alpha)R_y(\frac{\gamma}{2}) X R_y(-\frac{\gamma}{2}) R_z(-\frac{\alpha + \beta}{2}) X R_z(-\frac{\alpha - \beta}{2}) \\
&= R_z(\alpha)R_y(\frac{\gamma}{2}) (X R_y(-\frac{\gamma}{2}) X) (X R_z(-\frac{\alpha + \beta}{2}) X) R_z(-\frac{\alpha - \beta}{2}) \\
&= R_z(\alpha) R_y(\frac{\gamma}{2}) R_y(\frac{\gamma}{2}) R_z(\frac{\alpha + \beta}{2}) R_z(-\frac{\alpha - \beta}{2}) \\
&= R_z(\alpha) R_y(\gamma) R_z(\beta) \tag{4}
\end{align}
と計算できますので、これで式(1)が成り立つことがわかります。ここで、公式、
\begin{align}
X R_y(\theta) X = R_y(-\theta) \\
X R_z(\theta) X = R_z(-\theta) \tag{5}
\end{align}
を使いました。量子回路で書くと、
--U-- = --C--X--B--X--A--Phi(delta)--
ですね。
さて、それでは、もっとも簡単な2量子ビットの制御ユニタリゲートについて考えます。回路図で書くと、
--*--
--U--
です。これを1量子ビットゲートとCNOTでどのように展開されるかと言うと、上の$A,B,C$と$X$を使って、
--*-- = -----*-----*------*----------
--U-- --C--X--B--X--A--Phi(delta)--
と書くことができます。これは、0番目の量子ビットが0の場合と1の場合を頭の中で想像してみれば、すぐにわかると思います。が、まだ、$\Phi(\delta)$のところに制御ユニタリが残っていました。
---*----------
--Phi(delta)--
の部分です。いま、制御ビットがn-1量子ビットで全体がn量子ビットの制御$U$演算子を、$\Lambda_{n-1} U$と書くことにすると、今の場合、
\begin{align}
\Lambda_{1} \Phi(\delta) &= \ket{0} \bra{0} \otimes I + \ket{1} \bra{1} \otimes \Phi(\delta) \\
&= (\ket{0} \bra{0} \otimes + e^{i\delta} \ket{1} \bra{1}) \otimes I \\
&=
\begin{pmatrix}
1 & 0 \\
0 & e^{i\delta}
\end{pmatrix} \otimes I = P(\delta) \otimes I \tag{6}
\end{align}
となりますので、
---*---------- = --P(delta)--
--Phi(delta)-- ------------
と書き直すことができます。
つまり、任意の制御ユニタリゲートは、$ABC = I$を満たす$A,B,C$と位相ゲート$P(\delta)$、およびCNOTゲートを使って、
--*-- = -----*-----*-----P(delta)--
--U-- --C--X--B--X--A------------
のように書くことができます。また、これより、1つの制御ユニタリ行列は、4つの1量子ビットゲートと2つのCNOTゲートに展開できるということもわかります。この数、覚えときましょう。
n量子ビット(制御:1,標的:n-1)
制御1(量子ビット)、標的1(量子ビット)の制御ユニタリゲートの構成法がわかったので、その拡張として、標的側のユニタリが複数量子ビットの場合について触れておきます。自分でつくった適当なユニタリ演算子(量子回路)があって、例えば、それに対してアダマールテストをしたくなったとき、というのが1つの応用かと思います(レアすぎ？)。演算子$BA$に対する制御ユニタリ演算子は、$A,B$各々を制御化して並べたものに等しいことに注意しておきましょう。つまり、
---*---- = --*--*--
--[BA]-- --A--B--
です(ここで、[BA]は、AをやってからBをやる演算子だと思ってください)。これを一般化すれば良いです。すなわち、いま考えているユニタリ演算子に含まれる1量子ビットゲートを制御化して、さらにCNOTゲットを制御化して(つまり3量子ビットのToffoliゲートにして)並べます。制御ユニタリの部分は、シミュレータによっては標準機能として定義されているかもしれませんが、そうでない場合は、上で説明したような$A,B,C$を見出す必要があります。さらに、3量子ビットのToffoliゲートの部分を1量子ビットゲートとCNOTゲートに展開します。量子回路で表現された任意のユニタリ演算子は、このようにして基本量子ゲートだけで制御ユニタリ化することができます。
一般Toffoliゲート(グレイコード利用、補助量子ビットなし)
さて、それでは、本題の「一般Toffoliゲート」についてです。いきなり、n量子ビットを相手にするのは大変なので、小さい量子ビット数の場合から順に見ていきます。
3量子ビット(制御:2,標的:1)
まず、やりたいことは、
|x1> --*--
|x2> --*--
|x3> --U--
を基本量子ゲートで展開することです。式で書くと、
\Lambda_{2} U \ket{x_1, x_2, x_3} = \ket{x_1,x_2} \otimes U^{x_1 \land x_2} \ket{x_3} \tag{7}
の右辺を基本量子ゲートで展開します。
ここで、ちょっと唐突ですが、以下の議論で繰り返し使う、大事な等式(のもっとも簡単なバージョン)を掲載しておきます。
\begin{align}
2(x_1 \land x_2) &= x_1 + x_2- (x_1 \oplus x_2) \\
&= - \sum_{r_1,r_2=0}^{1} (-1)^{r_1 + r_2} (r_1 x_1 + r_2 x_2) \tag{8}
\end{align}
これは、
\begin{align}
x_1 \oplus x_2 &= (x_1 - x_2)^2 \\
&= x_{1}^2 - 2 x_1 x_2 + x_{2}^2 \\
&= x_1 + x_2 - 2 x_1 x_2 \tag{9}
\end{align}
と計算できることから証明できます。
さて、式(7)を基本量子ゲートで展開できるようにするため、式(8)の$\sum$をグレイコードの順番で足していくことを考えます。2ビットのグレイコードは$(00),(01),(11),(10)$です。$(r_2 r_1) = (00)$の場合はゼロなので、$(r_2 r_1) = (01),(11),(10)$の順番で足しあげればよいです。つまり、
2(x_1 \land x_2) = x_2 - (x_1 \oplus x_2) + x_1 \tag{10}
ですね(後の都合により逆順に並べています)。これを式(7)に代入して、さらに$U=V^2$となるユニタリ演算子$V$を導入すると、
\begin{align}
\Lambda_{2} U \ket{x_1, x_2, x_3} &= \ket{x_1,x_2} \otimes U^{x_1 \land x_2} \ket{x_3} \\
&= \ket{x_1,x_2} \otimes V^{2(x_1 \land x_2)} \ket{x_3} \\
&= \ket{x_1, x_2} \otimes (V^{x_2} V^{-(x_1 \oplus x_2)} V^{x_1}) \ket{x_3} \\
&= (I \otimes I \otimes V^{x_2}) (I \otimes I \otimes V^{-(x_1 \oplus x_2)}) (I \otimes I \otimes V^{x_1}) \ket{x_1, x_2, x_3} \tag{11}
\end{align}
となります。ここで、$i$番目の量子ビットを制御ビット、$j$番目の量子ビットを標的ビットにするCNOT演算子を、
CX(i,j) \ket{x_i, x_j} = \ket{x_i, x_i \oplus x_j} \tag{12}
のように定義すると、式(11)は、さらに、
\begin{align}
\Lambda_{2} U \ket{x_1, x_2, x_3}
&= \cdots \\
&= (I \otimes I \otimes V^{x_2}) (I \otimes I \otimes V^{-(x_1 \oplus x_2)}) (I \otimes I \otimes V^{x_1}) \ket{x_1, x_2, x_3} \\
&= (I \otimes I \otimes V^{x_2}) CX(1,2) (I \otimes I \otimes V^{-x_2}) CX(1,2) (I \otimes I \otimes V^{x_1}) \ket{x_1, x_2, x_3} \tag{13}
\end{align}
となります。量子回路で表現すると、
|x1> --*--*-------*------
|x2> -----CX--*---CX--*--
|x3> --V------V+------V--
です。
ここで、グレイコードを使うことの意味をしっかり吟味しておきましょう。隣り合ったグレイコードは1ビットしか変化しない(ハミング距離が1)という性質をもっています。式(7)の右辺の$U$の肩にかかっている論理積を式(10)のように足しあげることで、各々の項に対応した制御$V$ゲート(または制御$V^{\dagger}$)を回路図上で並べていけば良いという見通しは立つのですが、各々のVの肩にかかっている指数をうまく矛盾なく設定していく必要があります。グレイコードを使って指数部分を展開したことが、ここで効いてきます。隣り合った演算同士はたかだか1ビットしか変化しないので、2量子ビットのCNOTをもってくれば十分に矛盾なくつないでやることができる、というわけです(詳しい規則は、次の4量子ビットのところで説明します)。
あとは、$U$の平方根ゲートである$V$(または$V^{\dagger}$)を使った制御ユニタリを、1量子ビット(4個)とCNOT(2個)で展開すれば良いです。
4量子ビット(制御:3,標的:1)
制御側の量子ビットを1つ増やしてみましょう。すなわち、
|x1> --*--
|x2> --*--
|x3> --*--
|x4> --U--
を基本量子ゲートで展開してみます。式で書くと、
\Lambda_{3} U \ket{x_1, x_2, x_3, x_4} = \ket{x_1,x_2,x_3} \otimes U^{x_1 \land x_2 \land x_3} \ket{x_4} \tag{14}
です。まず、先程示した式(8)を拡張します。
4(x_1 \land x_2 \land x_3) = - \sum_{r_1,r_2,r_3=0}^{1} (-1)^{r_1 + r_2 + r_3} (r_1 x_1 + r_2 x_2 + r_3 x_3) \tag{15}
ん？という感じかもしれないので証明します。式(8)の両辺を2倍して、$x_3$との論理積をとります。すると、
\begin{align}
2(2(x_1 \land x_2)) \land x_3
&= 2 \{ x_1 + x_2 -(x_1 \oplus x_2) \} \land x_3 \\
&= 2(x_1 \land x_3) + 2(x_2 \land x_3) - 2 (x_1 \oplus x_2) \land x_3 \\
&= x_1 + x_3 - (x_1 \oplus x_3) + x_2 + x_3 - (x_2 \oplus x_3) - \{ (x_1 \oplus x_2) + x_3 - (x_1 \oplus x_2 \oplus x_3) \} \\
&= x_1 + x_2 + x_3 - (x_1 \oplus x_2) - (x_1 \oplus x_3) - (x_2 \oplus x_3) + (x_1 \oplus x_2 \oplus x_3) \\
&= - \sum_{r_1,r_2,r_3=0}^{1} (-1)^{r_1 + r_2 + r_3} (r_1 x_1 + r_2 x_2 + r_3 x_3)
\end{align}
ですね。この和をグレイコードの順番で行います。グレイコードは$(000), (001), (011), (010), (110), (111), (101), (100)$なので、
4 (x_1 \land x_2 \land x_3) = x_3 - (x_1 \oplus x_3) + (x_1 \oplus x_2 \oplus x_3) - (x_2 \oplus x_3) + x_2 - (x_1 \oplus x_2) + x_1 \tag{16}
です(先程と同様逆順に記載しています)。$U=V^4$となるユニタリ演算子$V$を導入し、式(16)を式(14)に代入します。
\begin{align}
\Lambda_{3} U \ket{x_1, x_2, x_3, x_4}
&= \ket{x_1,x_2,x_3} \otimes U^{x_1 \land x_2 \land x_3} \ket{x_4} \\
&= \ket{x_1,x_2,x_3} \otimes V^{x_3} V^{-(x_1 \oplus x_3)} V^{x_1 \oplus x_2 \oplus x_3} V^{-(x_2 \oplus x_3)} V^{x_2} V^{-(x_1 \oplus x_2)} V^{x_1} \ket{x_4} \\
&= (I \otimes I \otimes I \otimes V^{x_3}) (I \otimes I \otimes I \otimes V^{-(x_1 \oplus x_3)}) (I \otimes I \otimes I \otimes V^{x_1 \oplus x_2 \oplus x_3}) (I \otimes I \otimes I \otimes V^{-(x_2 \oplus x_3)}) (I \otimes I \otimes I \otimes V^{x_2}) (I \otimes I \otimes I \otimes V^{-(x_1 \oplus x_2)}) (I \otimes I \otimes I \otimes V^{x_1}) \ket{x_1,x_2,x_3,x_4} \\
&= (I \otimes I \otimes I \otimes V^{x_3}) CX(1,3)
(I \otimes I \otimes I \otimes V^{-x_3}) CX(2,3)
(I \otimes I \otimes I \otimes V^{x_3}) CX(1,3)
(I \otimes I \otimes I \otimes V^{-x_3}) CX(2,3)
(I \otimes I \otimes I \otimes V^{x_2}) CX(1,2)
(I \otimes I \otimes I \otimes V^{-x_2}) CX(1,2)
(I \otimes I \otimes I \otimes V^{x_1}) \ket{x_1,x_2,x_3,x_4}
\end{align}
これを、量子回路で表現すると、
|x1> --*--*-------*--------------*--------------*------
|x2> -----CX--*---CX--*--*--------------*--------------
|x3> --------------------CX--*---CX--*--CX--*---CX--*--
|x4> --V------V+------V------V+------V------V+------V--
となります。
というわけで、制御ユニタリとCNOTの置き方に規則が見えてきそうな感じがしてきます。すなわち、、
まず、最初のグレイコード(000)を1つ進めて(001)にします。変化したビット番号は1番目なので、これを制御ビットにした制御$V$をかけます。次に、グレイコードを1つ進めて(011)にします。ここでCNOTをかけるのですが、ルールは、変化したビット番号を制御ビットにして、グレイコードの最大桁のビット番号を標的にすれば良さそうです。今の場合、制御と標的は1番目と2番目になります。また、制御ユニタリは$V^{\dagger}$に対する制御ユニタリとして、制御ビットはグレイコードの最大桁のビット番号(つまりCNOTの標的と同じ)とすれば良いです。次に、グレイコードを1つ進めて(010)にします。前段と同様にして、変化したビット番号1を制御ビット、最大桁番号2を標的とするCNOTをかけて、その標的を制御にした制御ユニタリをかけます。このときのユニタリは$V$です。つまり、$V$と$V^{\dagger}$は、交互に現れることになります。さらにグレイコードを1つ進めて(110)にします。このとき変化したビット番号は3、最大桁のビット番号も3となり、CNOTが成り立たちません。この場合は、制御ビットの方を1つ減らして2にする規則になっているようです。制御ユニタリ$V^{\dagger}$の制御ビット番号はCNOTの標的とおなじ3です。ということを繰り返していく規則で良さそうです。
いま「良さそうです」と、さも自分が導いたかのような言い方をしましたが、すみません、参考書籍を読んでいるので偉そうに語れるだけです。これをはじめに導いた人は偉いと思います。
n量子ビット(制御:n-1,標的:1)
最後にn量子ビットの場合です。やりたいことを数式で書くと、
\Lambda_{n-1} U \ket{x_1, x_2, x_3,\cdots ,x_n} = \ket{x_1,x_2, \cdots ,x_{n-1}} \otimes U^{x_1 \land x_2 \land \cdots \land x_{n-1}} \ket{x_n} \tag{17}
の右辺を基本量子ゲートで展開することです。先程の式(15)をさらに拡張します(証明は省略します)。
2^{n-2} (x_1 \land x_2 \land \cdots \land x_{n-1}) = - \sum_{r_1,r_2, \cdots ,r_{n-1}=0}^{1} (-1)^{r_1 + r_2 + \cdots + r_{n-1}} (r_1 x_1 + r_2 x_2 + \cdots + r_{n-1} x_{n-1}) \tag{18}
この右辺の和をグレイコードの順番に並べて(正確には逆順に並べて)、式(17)に代入してガチャガチャ計算すると、基本量子回路だけで実行できる式が導けるはずです。量子回路の記載は省略します。代わりに、量子回路を順に構成していくためのルールを示します。
- [STEP.0] (n-1)ビットの制御ビットと1ビットの標的ビットを設定し、(n-1)ビットのグレイコードを0に初期化します。
- [STEP.1] グレイコードを1つ進めます。
- [STEP.2] グレイコードが0のときは[STEP.1]に戻ります。それ以外のときは[STEP.3]に進みます。
- [STEP.3] グレイコードを1つ進めたことで変化したビット番号を制御ビット、グレイコードの1が立っている最上位ビット番号を標的ビットとしたCNOTゲートをかけます。ただし、制御と標的が同じになってしまった場合、制御ビット番号の方を1つ下げます。また、グレイコードが1の場合、何もしません。
- [STEP.4] グレイコードの1が立っている最上位ビット番号を制御ビットにして、全体の標的ビットを標的にする制御ユニタリをかけます。このとき、奇数番目のグレイコードの場合、そのユニタリ演算子を$V$とし、偶数番目の場合、$V^{\dagger}$とします。ここで、$V$は$U=V^{2^{n-2}}$を満たすユニタリです。
- [STEP.5] グレイコードが(n-1)ビットの範囲内にある場合、[STEP.1]に戻ります。それ以外となった場合、終了します。
ちなみに、前々回の記事では、「一般」ではないToffoliゲート(つまり、Multi-Controlled NOTゲート)の話をしましたが、上の$U$を位相シフトゲート$P(\pi)$として、両側からアダマールではさむことで実現していました。
基本量子ゲート数
最後に、このように構成したとき、基本ゲート数がどうなるかを見積もってみます。
2量子ビットの制御ユニタリが$2^{n-1}-1$個、CNOTゲートが$2^{n-1}-2$個必要になります。また、2量子ビットの制御ユニタリは、4個の1量子ビットゲートと2個のCNOTで表現し直せます。総合すると、1量子ビットゲートは$4(2^{n-1}-1)$個、CNOTゲートは$2(2^{n-1}-1)+(2^{n-1}-2)$個必要となります(正確には、グレイコードのつなぎの部分でCNOTをいくつか削除できますが、大勢には影響ありません。詳細は参考文献をご覧ください)。
ということで、$O(2^n)$の基本量子ゲートが必要になります。
おわりに
ようやく、喉に引っかかっていた魚の骨がとれた感じがします(笑)。が、これの理解を進める中で、もっと効率の良い構成方法があるということを知りました（$O(2^n)$では効率悪すぎです）。「はじめに」で述べたように、次回、（その２）として、そのあたりの説明をしてみたいと思います。
以上