【数式なしの量子コンピュータ】3回目 簡単に作成できるマルチ制御NOTゲート

連載記事の3回目　簡単に作成できるマルチ制御ゲート
前回と異なり今回は読み切り可能でかつ長くはない投稿。では何故「マルチ制御ゲート」正確には「マルチ制御NOTゲート」を、ここで持ち出したのか？ 「ソリトンセルオートマトン（６回目予定）」と「グローバーアルゴリズム（6量子ビット）の時間発展（７回目予定）」には「マルチ制御NOTゲート」が必要だからである。

Blueqatのユーザーが使えるようにモジュール化してみた。名前はqmcn.py。このモジュールの中身については以下に説明するが、全体はGithubのリポジトリーq-camsで公開している。このモジュールではcccx（３ビット制御）から CCCCCCX（６ビット制御）までが含まれているが、誰か７ビット以上のもっとマルチな制御やNOT以外の制御ゲート化を付け加えてくれたらと思う。量子コストは物凄いことになってしまうが。

3-1. グレイコード

グレイコードとは灰色のコードのことではない。Grayさんが考案した二進表記の方法で通常の二進法と桁上りのルールが異なる。要はカウントアップしていく時、０から１に、あるいは１から０に変化する桁が1か所だけというものだ。なんでこのコードがゲート型量子コンピュータのマルチ制御ゲートと関係するのか？　マルチ制御ゲートを、数式なしに作るときに役立つからだ。具体的なグレイコードは3-2の表3-2に挙げている。

では、どのようにしたらこのグレイコードが生成できるのか。普通の二進数であれば十進数から変換はできるであろう。しかしグレイコードはいきなり十進数から生成するのは難しく、その代わり普通の二進数を介在させると簡単にできる。その方法を言葉で表現すれば、二進数を右にシフトし、シフト前のオリジナルの二進数とシフト後の二進数で排他論理和(異なれば 1、等しければ 0)、つまり制御NOTをとるとグレイコードとなる。

下表を使って具体的な例で見てみよう。十進数の23を二進数にすれば、10111である。これを①とする。この二進数がビットの列だと考えて、中身を右隣りのビットに移す。これを右シフトと言う。表の②の上段の状態である。表の左端のビットは空欄になってしまうので、そこに０を入れる。右端のビットは一個飛び出てしまう。このビットは捨ててしまう。その結果、得られたものが②の下段の01011である。次に①と②の下段の同じビットの位置にある中身で排他論理和をとる。つまり制御NOTを行う。その結果がグレイコードである。

古典コンピュータでは

古典コンピュータにはビットの中身（１あるいは０）を右あるいは左のビットに移すシフトと称するビット演算が準備されている。この表の例の場合、右にずらした時、十進数で言うと２で割った値となっている。表で飛び出した所の値が余りを現すことになる。逆側にシフトさせた場合は２を掛けた値となる。さらにローテートというビット演算があり、これは下表の右に飛び出した部分を捨てるのではなく左端に入れる。セルオートマトンでもこれと同様の処理をすることがあり周期的境界条件と称する。

本論の「マルチ制御ゲート」から横道にそれるが、上述した普通の二進数からグレイコードを生成するアルゴリズムは、非常に単純な量子アルゴリズムで記述できることに気付いた。今、N桁の二進数を量子ビット番号0~N-1にセットする。古典コンピュータのようにビット演算でこの量子ビットを直接シフトできないので、量子ビット番号0~N-1の状態を１個シフトさせたものを量子ビット番号N~2N-1に「コピー（この後説明）」する。シフトさせるのは簡単で量子ビット0番をN番ではなくN+1番に「コピー」すればよい。左端となるN番は何もしなければ0状態である。また、N-1番は捨ててしまうので「コピー」しなくてよい。「コピー」とは、0状態にある量子ビットを標的（後述）としてコピー元を制御ビットとして制御NOTゲートを適用すればよい。排他論理和(異なれば 1、等しければ 0)なので片方が０なら必ず、元の値になる。最後に0~N-1ビットとN~2N-1ビットで制御NOTを行えばグレイコードなる。以下にBlueqatを用いた十進数からのグレイコード生成プログラムのフルコードを記した。とても実用的かつある意味ナンセンスな量子コンピューティングだと思う。

graycode.py

from blueqat import Circuit

dnum=input('input natural number less than 1024 > ')
temp=list(bin(int(dnum)))
del temp[0:2]
temp[0:0]=['0']*(10-len(temp))

c=Circuit(20)

for i in range(10):
    if temp[i]=='1':
        c.x[i]          # initial qubit setting

for i in range(9):
    c.cx[i,i+11]        # copy with shift
for i in range(10):
    c.cx[i,i+10]        # exclusive OR  

wgc=list(c.m[:].run(shots=1))   
xgc=wgc[0]

print(dnum,'=> Gray Code =', xgc[10:])from blueqat import Circuit

初めに、コンソールからグレイコードを知りたい自然数（1~1023）を入力する。エラー処理をしていないので左記以外の値を入れた場合、正しい解は得られない。pythonで入力された十進数を10桁の二進数化をし、それをリスト化してdelで'0b'をカットする。10桁に満たない場合、左側に'0'を加えて二進数を完成させる。このリストをもとに量子ビット番号０~９番に「１」、「０」をセットするが、リストの要素で「１」の時はxゲートで反転させて「１」状態する。ここまでは単なるセッティングで、二進数からグレイコードを生成するアルゴリズム部は前述した通りである。重ね合わせを行っていないので、答えは常に一つのみである。単純にプリントすると、オリジナルの二進数とグレイコードの20桁分を出力してしまうのでスライスして量子ビット番号10から19まで、つまりグレイコードのみを出力させている。以下、十進数23を入力した時の結果である。

ところで、制御ゲートの最もシンプルなものが、制御NOTゲートでBlueqatのコードで書けば、cx[control,target]　controlはある量子ビットの番号で制御ビットと称し、targetは別の量子ビットの番号で標的ビットと称する。排他論理和(異なれば 1、等しければ 0)を丁寧に説明すると、制御ビットの状態が「１」のとき、標的ビットの状態は反転する。つまり「１」なら「０」に、「０」なら「１」にと。一方、制御ビットの状態が「０」である場合、標的ビットの状態は変わらない。if文のような制御構造を持たない量子コンピュータのアルゴリズムにおいて、この制御NOTゲートは貴重だ。しかし、残念なことに、制御ビットが自分自身を標的ビットとすることができない。それ故にか、量子コンピュータのアルゴリズムで本当にif文のような構造を作ろうとナンセンスなことをすると勢い、制御ビットの数、つまり標的ビットを反転させる条件を多くしていくことになる。

制御ビットが二つの場合、つまり制御制御NOTは、トフォリさんが発案なので特別にトフォリゲートと称する。トフォリゲートの場合、２つの制御ビットの状態がともに１であれば標的ビットの状態を反転させるが、どちらか一つでも状態が０であると標的ビットは変化しない。尚、トフォリゲートの場合はBlueqatの標準としてccxゲートが準備されている。制御が３つ以上になると制御という文字を連ねるのが面倒なのでマルチ制御などと称している。当然、全制御ビットの状態が１であれば、唯一の標的ビットは反転するが、そうでなければ反転しない。残念ながら制御ビットが３以上のマルチ制御ゲートはBlueqatの標準のゲートとしては準備されていない。しかし幸いマルチ制御NOTゲートは、制御NOTゲートと制御Z軸回転ゲート（位相回転ゲート）及び一対のアダマールゲートから構成できる。何故、これらの簡単なゲートの組み合わせだけで作れるのか、数式なしには説明できない。と言うより投稿者の理解のスコープ外となる。理屈は分からずとも、どの様に構成すればとてもマルチな制御NOTゲートにすることができるのか、具体的な方法論を次に説明する。

3-2. マルチ制御ゲートの作り方

下表3-2(プログラムの下の表）の左側から３列目が左隣の自然数（１０進数）のグレイコードである。この表の目的は、上述した通りマルチ制御NOTゲートのコードの構成要素である制御NOTゲートと制御Z軸回転ゲートの制御ビットと標的ビットの番号を指し示すことにある。では何故、そんなことを指し示す必要があるのか？例えば、あるマルチ制御NOTゲートの制御ビット数がｎ個だった場合、ちなみに標的ビットは常に１個だけだが、制御ビットが１個のシンプルな制御NOTゲートcxと制御Z軸回転ゲートcrzをそれぞれ $2^n-2$ 個分と $2^n-1$ 個分ものコードを連ねる必要がある。しかも $2^n-2$ 個の制御ビットのビット番号はルールがあるようなないような数列をなしている。そのルールを現しているのがグレイコードを基に作成したこの表となる。では、作り方は。例としていきなり、制御が６個のマルチ制御NOTゲートの作り方である。

まず最初に、マルチ制御NOTゲートの標的ビット（以降ta）にアダマールゲートをかける。つまりh[ta]である。表ではta=6を想定している。次に制御Z軸回転ゲートを記述をするが、まず、回転角を計算してなくてはいけない。幸い、全記述で同じ回転角なので、これをangとすれば、$$ang=2\pi/2^n=\pi/2^{(n-1)}$$で与えられる。今回はn=6なので$ang=\pi/32$である。この時の制御ビットは表の1行目の⑤、標的ビットは⑥に記載した番号である。コードではcrz(ang)[0,6]　 次に、制御NOTゲートだが、制御ビットは表の２行目の③を、また標的ビットは同行の④の番号を記述すればよい。さらに次は再び制御Z軸回転ゲートがくる。制御ビットと標的ビットの番号は、それぞれ表の２行目の⑤と⑥である。ここで注意しなければならないのは回転角の符号で、ここではマイナスである。二つのゲートを続けてコードで書くと　cx[0,1].crz(-ang)[1,6]　となる。この記述を表の63行目まで繰り替えすが、回転角の符号は偶数行の時はマイナスで奇数行の時はプラスとする。そして最後に、もう一度、h[ta]を記述すれば完成となる。

実際のモジュール内の関数を下に示そう。マルチ制御NOTゲートの制御ビットを0~5番とし表2-3では現していたが、この関数では、記述者が自由に割り当てることのできる量子ビットの番号であるので、関数上の変数として、c0~c5としている。このモジュールはGithubのリポジトリーq-cams内qmcnであり、以下その中の関数ccccccxである。関数cccx~cccccxも同様にして記述されている。このコードでは一行に表2-3の２行分づつを記述している。このように記述するとわかるのだが、ビットの番号が頻繁に変化しているのは先頭の制御NOTゲートの制御ビットだけとなり、見通しが良い。尚、関数の先頭の引き数cは、blueqatの量子回路オブジェクトであり、この関数を呼び出すときに必ず必要となる。また、この関数には戻り値はないが、標的ビットの量子ビットの状態は、全制御ビットの状態が１であれば反転するし、制御ビット内一つでも０状態があれば変化しない。この関数を使うためには、プログラムと同じフォルダにqmcn.pyを保存しておき、import qmcn as qなどとしてインポートしておく必要がある。関数の呼び出しはq.ccccccx(c,8,9,10,11,12,13,20)などと記述すれば良い。

qmcn.py

def ccccccx(c,c0,c1,c2,c3,c4,c5,ta):

    ang=np.pi/32

    c.h[ta]                             #Hadamard                                   
    c.crz(ang)[c0,ta]                       #Gray code 1
    c.cx[c0,c1].crz(-ang)[c1,ta].cx[c0,c1].crz(ang)[c1,ta]      #Gray code 11 & 1
    c.cx[c1,c2].crz(-ang)[c2,ta].cx[c0,c2].crz(ang)[c2,ta]      #Gray code 110 & 111
    c.cx[c1,c2].crz(-ang)[c2,ta].cx[c0,c2].crz(ang)[c2,ta]      #Gray code 101 & 100
    c.cx[c2,c3].crz(-ang)[c3,ta].cx[c0,c3].crz(ang)[c3,ta]      #Gray code 1100 & 1101
    c.cx[c1,c3].crz(-ang)[c3,ta].cx[c0,c3].crz(ang)[c3,ta]      #Gray code 1111 & 1110
    c.cx[c2,c3].crz(-ang)[c3,ta].cx[c0,c3].crz(ang)[c3,ta]      #Gray code 1010 & 1011
    c.cx[c1,c3].crz(-ang)[c3,ta].cx[c0,c3].crz(ang)[c3,ta]      #Gray code 1000 & 1000
    c.cx[c3,c4].crz(-ang)[c4,ta].cx[c0,c4].crz(ang)[c4,ta]      #Gray code 11000 & 11001
    c.cx[c1,c4].crz(-ang)[c4,ta].cx[c0,c4].crz(ang)[c4,ta]      #Gray code 11011 & 11010
    c.cx[c2,c4].crz(-ang)[c4,ta].cx[c0,c4].crz(ang)[c4,ta]      #Gray code 11110 & 11111
    c.cx[c1,c4].crz(-ang)[c4,ta].cx[c0,c4].crz(ang)[c4,ta]      #Gray code 11101 & 11100
    c.cx[c3,c4].crz(-ang)[c4,ta].cx[c0,c4].crz(ang)[c4,ta]      #Gray code 10101 & 10111
    c.cx[c1,c4].crz(-ang)[c4,ta].cx[c0,c4].crz(ang)[c4,ta]      #Gray code 10110 & 10010
    c.cx[c2,c4].crz(-ang)[c4,ta].cx[c0,c4].crz(ang)[c4,ta]      #Gray code 10010 & 10011
    c.cx[c1,c4].crz(-ang)[c4,ta].cx[c0,c4].crz(ang)[c4,ta]      #Gray code 10001 & 10000
    c.cx[c4,c5].crz(-ang)[c5,ta].cx[c0,c5].crz(ang)[c5,ta]      #Gray Code 110000 & 110001
    c.cx[c1,c5].crz(-ang)[c5,ta].cx[c0,c5].crz(ang)[c5,ta]      #Gray Code 110011 & 110010
    c.cx[c2,c5].crz(-ang)[c5,ta].cx[c0,c5].crz(ang)[c5,ta]      #Gray Code 110110 & 110111
    c.cx[c1,c5].crz(-ang)[c5,ta].cx[c0,c5].crz(ang)[c5,ta]      #Gray Code 110101 & 110100
    c.cx[c3,c5].crz(-ang)[c5,ta].cx[c0,c5].crz(ang)[c5,ta]      #Gray Code 111100 & 111101
    c.cx[c1,c5].crz(-ang)[c5,ta].cx[c0,c5].crz(ang)[c5,ta]      #Gray Code 111111 & 111110
    c.cx[c2,c5].crz(-ang)[c5,ta].cx[c0,c5].crz(ang)[c5,ta]      #Gray Code 111010 & 111011
    c.cx[c1,c5].crz(-ang)[c5,ta].cx[c0,c5].crz(ang)[c5,ta]      #Gray Code 111001 & 111000
    c.cx[c4,c5].crz(-ang)[c5,ta].cx[c0,c5].crz(ang)[c5,ta]      #Gray Code 101000 & 101001
    c.cx[c1,c5].crz(-ang)[c5,ta].cx[c0,c5].crz(ang)[c5,ta]      #Gray Code 101011 & 101010
    c.cx[c2,c5].crz(-ang)[c5,ta].cx[c0,c5].crz(ang)[c5,ta]      #Gray Code 101110 & 101111
    c.cx[c1,c5].crz(-ang)[c5,ta].cx[c0,c5].crz(ang)[c5,ta]      #Gray Code 101101 & 101100
    c.cx[c3,c5].crz(-ang)[c5,ta].cx[c0,c5].crz(ang)[c5,ta]      #Gray Code 100100 & 100101
    c.cx[c1,c5].crz(-ang)[c5,ta].cx[c0,c5].crz(ang)[c5,ta]      #Gray Code 100111 & 100110
    c.cx[c2,c5].crz(-ang)[c5,ta].cx[c0,c5].crz(ang)[c5,ta]      #Gray Code 100010 & 100011
    c.cx[c1,c5].crz(-ang)[c5,ta].cx[c0,c5].crz(ang)[c5,ta]      #Gray Code 100001 & 100000
    c.h[ta]                             #Hadamard

    return

表3-2

これで、この表を用いてのマルチ制御NOTゲートの作り方は分かったとして、ではこの表の③、④、⑤、⑥は何処から出てきた値であるのかと言うことになる。表の全桁数①は言うまでもなくグレイコードの桁数である。その横の上下差分の絶対値の、「上下」とは表の行の上下で、差分とは一つ上の行のグレーコードの差分であり、例えば、自然数で２０の行のグレイコードは11110、この一行上、つまり自然数で１９の行のグレーコードは11010、この差の絶対値は $|11110-11010|=100$ である。その横列は差分の桁数②である。前例の差分が１００の場合、３桁なので３である。この数値は要するに上のグレイコードの何桁目が変化したのかの数値である。この全桁数①と差分の桁数②から、制御NOTゲートと制御Z軸回転ゲートの制御ビットと標的ビットとの番号が計算される。計算は以下のとおりである。

• 制御NOTゲート(cx)の制御ビット ③=②－１
• 制御NOTゲート(cx)の標的ビット ④=①－１
• 制御Z軸回転ゲート(crz)の制御ビット　⑤=①－１=④
• 制御Z軸回転ゲート(crz)の制御ビット　⑥=ta
• $2^i$行の制御NOTゲート(cx)の制御ビット ③=②－2　（iは自然数）

上の最後の $2^i$ 行、つまりグレイコードの全桁数が変わる行は例外で制御NOTゲート(cx)の制御ビットの数値から２マイナスする。以上のようにして表3-2は作られている。

3-3. サマリー

サマリーと言うより補足
表3-2を使って作り方を説明したが、核心部分は、$2^n-2$ 個の制御NOTゲートの制御ビット番号（表3-2の③）である。③はグレイコードから導いたが、この数列はもっと単純に以下の方法からも作り出せる。ただ、これはグレイコードに元々内在している性質とも言える。下の表は、表3-2の③の列を行方向に転置して表3-2で例外で示した黄色でマークしたところで切り行を下にずらして作成したものである。大体眺めていれば、フラクタル(入れ子構造）性と対照性を有していることが分かるであろう。例えば３の行は、中央の３を中心にした対称を成しており、その３の左右は、丸っきり２の行そのものである。だとすれば、この表にはない５行目もグレイコードを使用せずに簡単につくることができる。さらに、制御NOTゲート及び制御Z軸回転ゲートのそれぞれ標的ビットと制御ビットは一番左の黄色のマーキングの数値のプラス１である。

表3-3

と言うことでマルチ制御NOTゲートは莫大なゲートを費やすが簡単に作れることが分かる。次回からいよいよセルオートマトンの投稿をする予定である。