量子ゲートで、非常に基本的なゲートにCNOTゲートがあります。
これは、Controlビットが1のときのみ、Targetビットを反転させる、というものです。

また、少し応用的なゲートにToffoliゲートがあります。
これは、Controlが2つあるCNOTゲートで、Controlビットが両方共1のときのみ、Targetビットを反転させる、というものです。

では、Controlが3つ, 4つ, ... の場合も、こうしたゲートを作ることができるのでしょうか。
このような、Multi-controlled NOTゲートを作っていきます。

基本方針

まず、Multi-controlled Zゲートを作ります。
続いて、Multi-controlled Zゲートの前後をHゲートで挟みます。
そうすると、Multi-controlled NOTゲートができます。

Targetビットに注目しましょう。

もしも、controlビットに0が含まれていた場合、Multi-controlled Zゲートは、Targetビットに何も起こりません。
すると、Targetビットには、Hゲートが2回適用されることになるので、何も起こりません。

もしも、controlビットがすべて1だった場合、Multi-controlled Zゲートによって、TargetビットにZゲートがかけられます。
すると、Targetビットには、 H, Z, H の操作がなされます。

これは、Xゲートを操作するのと等価であることが知られています。

こういったゲート操作がどのような行列になるのかを知るには、Blueqatを使うのが便利です。

from blueqat import Circuit
print(Circuit().h[0].z[0].h[0].run(backend='sympy_unitary'))
# => Matrix([[0, 1], [1, 0]])
print(Circuit().x[0].run(backend='sympy_unitary'))
# => Matrix([[0, 1], [1, 0]]) 上と同じ

Controlled RZゲートを作る

Controlled RZゲートは、Z軸を任意の角度だけ回転させるRZゲートの、controlled版です。
Multi-controlled Zゲートを作るために必要になるので、先に作っておきます。

これはとても簡単で、角度θを回転させるControlled RZは、次のように作ります。ただし、cはcontrolビット、tはtargetビットです。
CXはCNOTと同じ意味です。

rz(θ/2) t
cx c, t
rz(-θ/2) t
cx c, t

cが0のときは、CXゲートは何もしないので、
ターゲットビットは、θ/2回転した後、-θ/2回転し、元に戻ります。
cが1のときは、CXゲートはtをX軸周りに180度回します。
ターゲットビットは、θ/2回転した後、X軸まわりに180度回ります。それから-θ/2回転すると、回転は打ち消し合わず、追加で回ります。それから、X軸まわりに180度回したのを元に戻す操作をします。

イメージしにくいので、次のように、時計を考えます。面倒なので、短針だけ描いています。
(ブロッホ球が分かる人向けの説明: ブロッホ球のXY平面を輪切りにしたと思ってください)
4時間分、回転するには、次のようにします。

Multi-controlled RZゲートを作る

Multi-controlled RZゲートを作って回転角をπにすれば、Mutli-controlled Zゲートになるので、Multi-controlled RZゲートを作っていきます。

Controlled RZゲートを上で作りましたが、その際に行った、「回して、CNOTして、逆方向に回す」という方針はMulti-controlled RZゲートにも使えます。

全てのcontrolビットが1のときだけ、所定の回数を回るようにして、そうでないときは元に戻るようにする、というのが基本方針となります。

Controlが2個だと

回転したい角度をθとして、φ=θ/2とおきます。φが2回で、ちょうどθだけ回ることになります。

controlビットをc0, c1とおきます。また、targetビットをtとおきます。
まず、さっき作ったcrzを使いましょう。

crz(φ) c0, t // (1)

これだと、c1が0のときにも回転してしまうので、次のように対処します。

cx c0, c1
crz(-φ) c1, t // (2)

さらに、

cx c0, c1
crz(φ) c1, t // (3)

とします。

動きがわかりにくいので、表にします。
ただし、c0 c1: tの順で、tには、回転した角度の累計を書いています。

最初	(1)	(2)	(3)
0 0	0 0: 0	0 0: 0	0 0: 0
0 1	0 1: 0	0 1: -φ	0 1: 0
1 0	1 0: φ	1 1: 0	1 0: 0
1 1	1 1: φ	1 0: φ	1 1: 2φ

ちょうど、c0, c1が1のときのみ2φ=θ、回転していることが分かります。

Grayコード

じゃあ、controlが3ビット、4ビット、...だったら、どうするのか。
自分でがんばって探さないといけないのか、規則性にしたがって自動で構成する方法があるのか。
気になると思います。

Grayコードを使うと、自動的にMulti-controlled RZゲートを作ることができます。
これは、nビットの数を、順に1ビットずつ変化させる符号化形式で、例えば、3ビットのGrayコードは次のようになります。

000
001
011
010
110
111
101
100

機械的に構成する

Grayコードを使って、次のような手順で構成します。
また、ターゲットとなるビットをTビットと表します。

controlの数と同じビット数のGrayコードを考える。最初は0とする
Grayコードを1つ進める。このとき「変化したビットが何番目か」、「立っているビットのうち最上位のものは何番目か」「立っているビットが偶数個か奇数個か(Grayコードの性質上、偶数、奇数、偶数、奇数、と繰り返す)」を覚えておく
変化したビットの番号をcontrol、最上位ビットの番号をtargetとして、CNOTゲートをかける。ただし、最上位ビットが変化した場合は、ひとつ下位のビットをcontrolとする。また、初回、0から1に進める場合は、CNOTはかけない
最上位ビットをcontrol、Tビットをtargetにして、crzゲートをかける。ただし、回転角は、立っているビットが奇数個のときはφ、偶数個のときは-φとする
2.に戻る。Grayコードを進めた結果、controlの数を超えたビットが立ったら6.に進む
これにより、controlが全部1のときのみTビットが$2^{n-1}\phi$(ただしnはcontrolの数)回転し、それ以外はTビットが回転しない操作ができた。なので、$\phi = \theta/2^{n-1}$とおくと、θを回転させるmulti controlled RZゲートができた

すみません、なんでこれでできるのかは、まだ理解していません。
(知っている方がいたら、コメントいただけると有り難いです)

とりあえず、4ビットで回路を書いてみます。

た、多分あってるはず……!

Multi-controlled RZゲートからMulti-controlled NOTゲートに

Multi-controlled RZゲートをMulti-controlled Zゲートとして使いたいので、回転角を180度、つまりθ = π (rad)とします。
Multi-controlled Zゲートのtargetビットの前後にHゲートを挿入すると、Multi-controlled NOTゲートができました。

参考文献&謝辞

この記事の大部分は、Qiskit Aquaのソースコードリーティングで得られた知見を元に書いています。
また、ソースコードリーディングは、MDR株式会社でのインターンの一環として、インターン生の助けをたくさん借りて行いました。
IBMの開発者とMDRのインターン生に深く感謝を申し上げます。

Multi-controlled NOTゲートを補助ビットなしに作ってみる