$$
\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}}
$$
はじめに
前回の記事（その１）で、グレイコードを用いてn量子ビット(制御:n-1)の一般Toffoliゲートを構成する方法について説明しました。その際、必要となる基本ゲート数が$O(2^n)$となり、あまり効率的ではない方法であるということもわかりました。以下に示す参考書籍には、補助量子ビットが1つ必要になるのですが、基本ゲート数が$O(n)$のオーダーで済む方法も掲載されていました。今回はそれについて勉強してみたいと思います。
参考書籍に従い、以下のように進めていきます。
まず、制御量子ビット数とほぼ同数の補助量子ビットが必要になるToffoliゲートを構成する方法について見ていきます。次に、これを複数組み合わせて、補助量子ビット1つでToffoliゲートを構成する方法を示します。このとき、基本ゲート数が$O(n)$のオーダーで済むということも合わせて示します。最後に、このToffoliゲートを使って、一般Toffoliゲートを構成する方法を示します。
Toffoliゲートの構成(補助量子ビット数：制御量子ビット数とほぼ同数)
$n$量子ビットの状態空間上で$m=[n/2]$個の制御量子ビットをもつToffoliゲート$\Lambda_{[n/2]} X$を考えます。ここで$[a]$はガウス記号を表しています。すなわち、実数$a$に対してそれを超えない整数を$[a]$と表します。
簡単のため、まず、9量子ビット空間上でのToffoliゲート$\Lambda_{4} X$を考え、それを3量子ビットの(普通の)Toffoliゲートで展開できることを示します。
1 --*--
2 --*--
3 --*--
4 --*-- = ???
5 -----
6 -----
7 -----
8 -----
9 --X--
答えを先に言います。
(1)(2)(3)(4)(5)(6)(7)(8)
1 --*-- --------*-----------*-----
2 --*-- --------*-----------*-----
3 --*-- -----*-----*-----*-----*--
4 --*-- = --*-----------*-----------
5 ----- --------------------------
6 ----- --------------------------
7 ----- -----*--X--*-----*--X--*--
8 ----- --*--X-----X--*--X-----X--
9 --X-- --X-----------X-----------
です。ここで、アスタリスクとおなじ列に記載されている量子ゲートは線でつながっているものと思ってください(以下同様)。
何やら難しい配置ですが規則性がありそうです。Xゲートは最初、最大量子ビット番号$n(=9)$に配置され1つずつ量子ビット番号を下げ、$m-1(=3)$個並んだところで、今度は量子ビット番号を上げる方向に転じ、$m-1(=3)$個並んだところ(つまり最大ビット番号)のところで、再び量子ビット番号を下げる方向に$m-1(=3)$個並べ、最後に、量子ビット番号を上げていくのですが、今度は$m-2(=2)$個並べて終了します。制御量子ビットの方は、Xゲートと連動して上下するのですが、Xゲートの量子ビット番号が1番下がったところ、$n-m+2(=7)$番目のときだけ、制御量子ビット番号は(1,2)です。
これで、本当にToffoliゲートが実現できるのかを確認するため、表にしてみました。注目したいのは量子ビット番号が(7,8,9)の値$(x_7,x_8,x_9)$です(それ以外はこの量子回路を通して不変なので)。論理式の分配法則と$x \oplus x = 0$という恒等式に注意しておけば、順に計算できると思います。
| $x_7$ | $x_8$ | $x_9$ | |
|---|---|---|---|
| (1) | $x_7$ | $x_8$ | $x_4 \land x_8 \oplus x_9$ |
| (2) | $x_7$ | $x_3 \land x_7 \oplus x_8$ | $x_4 \land x_8 \oplus x_9$ |
| (3) | $x_1 \land x_2 \oplus x_7$ | $x_3 \land x_7 \oplus x_8$ | $x_4 \land x_8 \oplus x_9$ |
| (4) | $x_1 \land x_2 \oplus x_7$ | $x_3 \land (x_1 \land x_2 \oplus x_7) \oplus (x_3 \land x_7 \oplus x_8)$ $=x_1 \land x_2 \land x_3 \oplus x_8$ |
$x_4 \land x_8 \oplus x_9$ |
| (5) | $x_1 \land x_2 \oplus x_7$ | $x_1 \land x_2 \land x_3 \oplus x_8$ | $x_4 \land (x_1 \land x_2 \land x_3 \oplus x_8) \oplus (x_4 \land x_8 \oplus x_9)$ $=x_1 \land x_2 \land x_3 \land x_4 \oplus x_9$ |
| (6) | $x_1 \land x_2 \oplus x_7$ | $x_3 \land (x_1 \land x_2 \oplus x_7) \oplus (x_1 \land x_2 \land x_3 \oplus x_8)$ $=x_3 \land x_7 \oplus x_8$ |
$x_1 \land x_2 \land x_3 \land x_4 \oplus x_9$ |
| (7) | $x_1 \land x_2 \oplus (x_1 \land x_2 \oplus x_7)$ $=x_7$ |
$x_3 \land x_7 \oplus x_8$ | $x_1 \land x_2 \land x_3 \land x_4 \oplus x_9$ |
| (8) | $x_7$ | $x_3 \land x_7 \oplus (x_3 \land x_7 \oplus x_8)$ $=x_8$ |
$x_1 \land x_2 \land x_3 \land x_4 \oplus x_9$ |
さて、どうでしょうか。9番目の量子ビット番号の値が、
\ket{x_9} \rightarrow \ket{x_1 \land x_2 \land x_3 \land x_4 \oplus x_9}
となり、それ以外の量子ビットは最初どんな値だったとしても元の値に戻ることがわかりました。
では、9以外の$n$量子ビット(制御量子ビット$m=[n/2]$)の場合でも成り立つかを確認してみます。量子回路の第k層、第l番目の量子ビットの出力を$\ket{out_{k,l}}$と書くことにします。第1層から順に、Xゲートの出力を見ていきます。ちょっと長いですが辛抱強く計算していけば確認できるはずです。
\begin{align}
out_{1,n} &= x_{m} \land x_{n-1} \oplus x_{n} \\
out_{2,n-1} &= x_{m-1} \land x_{n-2} \oplus x_{n-1} \\
out_{3,n-2} &= x_{m-2} \land x_{n-3} \oplus x_{n-2} \\
& \cdots \\
out_{m-2,n-m+3} &= x_{3} \land x_{n-m+2} \oplus x_{n-m+3} \\
out_{m-1,n-m+2} &= x_{1} \land x_{2} \oplus x_{n-m+2} \\
out_{m,n-m+3} &= x_{3} \land out_{m-1,n-m+2} \oplus out_{m-2,n-m+3} \\
&= x_{3} \land (x_{1} \land x_{2} \oplus x_{n-m+2}) \land (x_{3} \land x_{n-m+2} \oplus x_{n-m+3}) \\
&= x_{1} \land x_{2} \land x_{3} \oplus x_{n-m+3} \\
out_{m+1,n-m+4} &= x_{4} \land out_{m,n-m+3} \oplus out_{m-3,n-m+4} \\
&= x_{4} \land (x_{1} \land x_{2} \land x_{3} \oplus x_{n-m+3}) \oplus (x_{4} \land x_{n-m+3} \oplus x_{n-m+4}) \\
&= x_{1} \land x_{2} \land x_{3} \land x_{4} \oplus x_{n-m+4} \\
& \cdots \\
out_{2m-3,n} &= x_{1} \land x_{2} \land \cdots \land x_{m} \oplus x_{n}
\end{align}
これで、n番目の量子ビットが正しく出力されることが確認できました(以後、この量子ビットは変化しません)。残りの層は、変化させてしまった補助量子ビットを元に戻す操作になります。
\begin{align}
out_{2m-2,n-1} &= x_{m-1} \land out_{2m-5,n-2} \oplus out_{2m-4,n-1} \\
&= x_{m-1} \land (x_{1} \land \cdots \land x_{m-2} \oplus x_{n-2}) \oplus (x_{1} \land \cdots \land x_{m-1} \oplus x_{n-1}) \\
&= x_{m-1} \land x_{n-2} \oplus x_{n-1} \\
out_{2m-1,n-2} &= x_{m-2} \land out_{2m-6,n-3} \oplus out_{2m-5,n-2} \\
&= x_{m-2} \land (x_{1} \land \cdots \land x_{m-3} \oplus x_{n-3}) \oplus (x_{1} \land \cdots \land x_{m-2} \oplus x_{n-2}) \\
&= x_{m-2} \land x_{n-3} \oplus x_{n-2} \\
& \cdots \\
out_{3m-6,n-m+2} &= x_{3} \land out_{m-1,n-m+2} \oplus out_{m,n-m+3} \\
&= x_{3} (x_{1} \land x_{2} \oplus x_{n-m+2}) \oplus (x_{1} \land x_{2} \land x_{3} \oplus x_{n-m+3}) \\
&= x_{3} \land x_{n-m+2} \oplus x_{n-m+3} \\
out_{3m-5,n-m+2} &= x_{1} \land x_{2} \oplus out_{m-1,n-m+2} \\
&= x_{1} \land x_{2} \oplus (x_{1} \land x_{2} \oplus x_{n-m+2}) \\
&= x_{n-m+2} \\
out_{3m-4,n-m+3} &= x_{3} \land x_{n-m+2} \oplus out_{3m-6,n-m+3} \\
&= x_{3} \land x_{n-m+2} \oplus (x_{3} \land x_{n-m+2} \oplus x_{n-m+3}) \\
&= x_{n-m+3} \\
& \cdots \\
out_{4m-8,n-1} &= x_{m-1} \land x_{n-2} \oplus out_{2m-2,n-1} \\
&= x_{m-1} \land x_{n-2} \oplus (x_{m-1} \land x_{n-2} \oplus x_{n-1}) \\
&= x_{n-1}
\end{align}
というわけで、$n-m+2,n-m+3,\cdots,n-1$番目の量子ビットが元の値$x_{n-m+2},x_{n-m+3},\cdots,x_{n-1}$に戻りました。また、全体で必要になる3量子ビットのTofforiゲートは$4m-8=4(m-2)$個であるということもわかりました。
Toffoliゲートの構成(補助量子ビット数：1)
次に、$n$量子ビットの状態空間上でのToffoliゲート$\Lambda_{n-2} X$を構成することを考えます。これは、いま見てきたToffoliゲート$\Lambda_{[n/2]} X$を4つ、以下のように並べると実現できます。
1 --*-- --*-----*-----
2 --*-- --*-----*-----
3 --*-- --*-----*-----
4 --*-- = --*-----*-----
5 --*-- -----*-----*--
6 --*-- -----*-----*--
7 --*-- -----*-----*--
8 ----- --X--*--X--*--
9 --X-- -----X-----X--
$n=9$の場合を示しましたが、それ以上の$n$の場合も容易にイメージできると思いますが、一応示しておきます。n-1番目が補助量子ビットです。
1 --*-- --*-----*-----
2 --*-- --*-----*-----
3 --*-- --*-----*-----
... ... ... ...
[n/2] --*-- --*-----*-----
[n/2]+1 --*-- = -----*-----*--
... ... ... ...
n-3 --*-- -----*-----*--
n-2 --*-- -----*-----*--
n-1 ----- --X--*--X--*--
n --X-- -----X-----X--
なぜこれがToffoliゲートになっているのかですが、
\begin{align}
out_{1,n-1} &= x_{1} \land \cdots \land x_{[n/2]} \oplus x_{n-1} \\
out_{2,n} &= x_{[n/2]+1} \land \cdots \land x_{n-2} \land out_{1,n-1} \oplus x_{n} \\
&= x_{[n/2]+1} \land \cdots \land x_{n-2} \land (x_{1} \land \cdots \land x_{[n/2]} \oplus x_{n-1}) \oplus x_{n} \\
&= x_{1} \land \cdots \land x_{n-2} \oplus x_{[n/2]+1} \land \cdots \land x_{n-1} \oplus x_{n} \\
out_{3,n-1} &= x_{1} \land \cdots \land x_{[n/2]} \oplus out_{1,n-1} \\
&= x_{n-1} \\
out_{4,n} &= x_{[n/2]+1} \land \cdots \land x_{n-2} \land out_{3,n-1} \oplus out_{2,n} \\
&= x_{[n/2]+1} \land \cdots \land x_{n-1} \oplus (x_{1} \land \cdots \land x_{n-2} \oplus x_{[n/2]+1} \land \cdots \land x_{n-1} \oplus x_{n}) \\
&= x_{1} \land \cdots \land x_{n-2} \oplus x_{n}
\end{align}
のように計算できることからわかります。
ここで、必要になる基本ゲート数を見積もってみます。いまToffoliゲート$\Lambda_{[n/2]} X$を2個、$\Lambda_{n-[n/2]-1} X$を2個使いました。先程、$\Lambda_{m} X$に必要になる3量子ビットのToffoliゲートは4(m-2)ということがわかりましたので、合わせると、$8([n/2]-2)+8(n-[n/2]-3)=8(n-5)$個の3量子ビットToffoliゲートが必要になります。3量子ビットのToffoliゲートは十数個程度の基本ゲートで構成できることがわかってていますので、結局、基本ゲート数は、$O(n)$のオーダーで済むことになります。
一般Toffoliゲートの構成(補助量子ビット数：1)
ここまで来れば、あとは一瞬で終わります。一般Toffoliゲートは、上で作成したToffoliゲートを2つ使って、
1 --*-- --*-----*--
2 --*-- --*-----*--
3 --*-- = --*-----*--
... ... ... ...
n-2 --*-- --*-----*--
n-1:|0> ----- --X--*--X--
n --U-- -----U-----
のように構成すれば良いです(n-1番目が補助量子ビットで$\ket{0}$に初期化しておく前提です)。制御量子ビットがすべて1のときだけXゲートが作動して1となり、その場合Uゲートが作動します。そのあとのToffoliゲートは補助量子ビットを元に戻す操作です。自明ですね。
使用する基本ゲート数は、先程のToffoliゲートの2倍ということなので、$O(n)$のオーダーとなります。
おわりに
補助量子ビットを1つ加えることで、基本ゲート数を$O(2^n)$から$O(n)$のオーダーまで削減することができました。将来、大規模な量子計算が実用化されたときには、この差は圧倒的だと思います。
できれば、補助量子ビットを使わないでもっと効率の良い方法があれば良いと思われるかもしれません。実は、今回の記事では省略してしまいましたが参考書籍には、補助量子ビットなしで$O(n^2)$にできるということも証明されていました。きちんと理解できたら、また紹介したいと思います。
以上