加減算回路の高位合成の試み

目的
----

ちょっとした足し算引き算を行う量子回路を作るのは結構大変です。
Python の構文の範囲内で、それらしく記述をするとそれらしく量子回路を合成できるといいな、と思ったので作ってみます。

```python
class TestProc_ADDSUB(UO_Procedure):
    def __init__(self, i: int, j: int) -> None:
        UO_Procedure.__init__(self, 'Test:ADDSUB')
        #
        #   回路の作成
        #
        # 整数は４量子ビットで表現する。
        Integer.NBITS = 4
        # 加減算に用いる２つの整数を用意する。
        a = Integer(self, i)
        b = Integer(self, j)
        # 途中の計算結果を取り出すための整数を用意する。
        c = Integer(self, 0)
        # 足し算 (b = b + a) を行う。
        b += a
        # 0 に b の XOR を作用させることで足し算の結果を c に取り出しておく。
        # Python に ^= はないようなので << で代用。
        c << b
        # 減算（足し算の逆演算）して b をもとに戻す (b = b - a)。
        b -= a
        # どの量子変数を割り付けたか確認できるように self に記録しておく。
        self.b = b
        self.c = c
# 回路を合成する
i = 3
j = 2
p = TestProc_ADDSUB(i, j)
# 合成した回路を表示する
print('---- circuit ----')
print(str(p))
# シミュレータ実行
print('---- simulator ----')
circuit = p.synthesis(blueqat.Circuit())
print(str(circuit))
result = str(circuit.m[:].run(shots=100))
print('---- result ----')
print(str(result))
print('a=' + str(p.a))
print('b=' + str(p.b))
print('c=' + str(p.c))
print('{0}+{1}-{1}={2}'.format(j, i, p.b.parse(result)))
print('{0}+{1}={2}'.format(j, i, p.c.parse(result)))
```

実行すると以下のように量子回路を合成してシミュレーション結果を表示できるようにします。

```
---- circuit ----
Test:ADDSUB{
 Integer.init{
  X[0],
  X[1]
 },
 Integer.init{
  X[5]
 },
 Integer.add{
  Carry[12,0,4,13]{ ccx[0,4,13], cx[0,4], ccx[12,4,13] },
  Carry[13,1,5,14]{ ccx[1,5,14], cx[1,5], ccx[13,5,14] },
  Carry[14,2,6,15]{ ccx[2,6,15], cx[2,6], ccx[14,6,15] },
  Carry[15,3,7,16]{ ccx[3,7,16], cx[3,7], ccx[15,7,16] },
  CX[3,7],
  Sum[15,3,7]{ cx[3,7], cx[15,7] },
  RCarry[14,2,6,15]{ ccx[14,6,15], cx[2,6], ccx[2,6,15] },
  Sum[14,2,6]{ cx[2,6], cx[14,6] },
  RCarry[13,1,5,14]{ ccx[13,5,14], cx[1,5], ccx[1,5,14] },
  Sum[13,1,5]{ cx[1,5], cx[13,5] },
  RCarry[12,0,4,13]{ ccx[12,4,13], cx[0,4], ccx[0,4,13] },
  Sum[12,0,4]{ cx[0,4], cx[12,4] }
 },
 Integer.xor{
  CX[4,8],
  CX[5,9],
  CX[6,10],
  CX[7,11]
 },
 Integer.sub{
  RSum[12,0,4]{ cx[12,4], cx[0,4] },
  Carry[12,0,4,13]{ ccx[0,4,13], cx[0,4], ccx[12,4,13] },
  RSum[13,1,5]{ cx[13,5], cx[1,5] },
  Carry[13,1,5,14]{ ccx[1,5,14], cx[1,5], ccx[13,5,14] },
  RSum[14,2,6]{ cx[14,6], cx[2,6] },
  Carry[14,2,6,15]{ ccx[2,6,15], cx[2,6], ccx[14,6,15] },
  RSum[15,3,7]{ cx[15,7], cx[3,7] },
  CX[3,7],
  RCarry[15,3,7,17]{ ccx[15,7,17], cx[3,7], ccx[3,7,17] },
  RCarry[14,2,6,15]{ ccx[14,6,15], cx[2,6], ccx[2,6,15] },
  RCarry[13,1,5,14]{ ccx[13,5,14], cx[1,5], ccx[1,5,14] },
  RCarry[12,0,4,13]{ ccx[12,4,13], cx[0,4], ccx[0,4,13] }
 }
}
---- simulator ----
Circuit(18).x[0].x[1].x[5].ccx[0, 4, 13].cx[0, 4].ccx[12, 4, 13].ccx[1, 5, 14].cx[1, 5].ccx[13, 5, 14].ccx[2, 6, 15].cx[2, 6].ccx[14, 6, 15].ccx[3, 7, 16].cx[3, 7].ccx[15, 7, 16].cx[3, 7].cx[3, 7].cx[15, 7].ccx[14, 6, 15].cx[2, 6].ccx[2, 6, 15].cx[2, 6].cx[14, 6].ccx[13, 5, 14].cx[1, 5].ccx[1, 5, 14].cx[1, 5].cx[13, 5].ccx[12, 4, 13].cx[0, 4].ccx[0, 4, 13].cx[0, 4].cx[12, 4].cx[4, 8].cx[5, 9].cx[6, 10].cx[7, 11].cx[12, 4].cx[0, 4].ccx[0, 4, 13].cx[0, 4].ccx[12, 4, 13].cx[13, 5].cx[1, 5].ccx[1, 5, 14].cx[1, 5].ccx[13, 5, 14].cx[14, 6].cx[2, 6].ccx[2, 6, 15].cx[2, 6].ccx[14, 6, 15].cx[15, 7].cx[3, 7].cx[3, 7].ccx[15, 7, 17].cx[3, 7].ccx[3, 7, 17].ccx[14, 6, 15].cx[2, 6].ccx[2, 6, 15].ccx[13, 5, 14].cx[1, 5].ccx[1, 5, 14].ccx[12, 4, 13].cx[0, 4].ccx[0, 4, 13]
---- result ----
Counter({'110001001010000000': 100})
a=Integer[0,1,2,3]
b=Integer[4,5,6,7]
c=Integer[8,9,10,11]
2+3-3=2
2+3=5
```

'---- circuit ----' に続けて最初に表示している部分が、合成された量子回路です。
一連の基本演算のどの部分がどのような回路ブロックに対応しているかを { } でくくって表示しています。

'---- simulator ----' に続けて表示しているのが、実際にシミュレータに投入された回路です。circuit として表示したものと全く同じで、ただ回路ブロック別になっていないだけなのが見て取れます。

'---- result ----' に続けて表示しているのがシミュレーション結果です。2 に対する操作 +3 に続けて、+3 の逆操作 -3 を行ったことで操作が打ち消し合って 2 に戻っています。逆操作実施前に XOR (CNOT) で加算結果を別の整数に写してあるので 2+3 の値も取得できています。

概略を図にするとこんな感じです。

![addsub.png](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/412308/b2f7739e-39cb-f1ab-5c38-ae824d3a4a34.png)


構成
----

まず、整数を表現するために必要な、あるいは加減算のワークエリアとして必要な量子ビットを割り付けられる仕組みを用意します。
これをベースとして、量子回路要素を表現するクラスをインスタンス化すると自動的に必要な量子ビットを取得して量子回路を合成できるようにします。
量子回路要素を再帰的に組み合わせ要素に還元していくことで、合成された量子回路を得ます。

量子ビットの割付
--------------

量子ビットは無限にある前提で、0 から順にインデックス位置で表します。
使用中の量子ビットインデックス位置を管理するクラスを作成します。

```python
class QubitAllocator(object):
    u'''量子ビット管理
    '''
    def __init__(self) -> None:
        self.allocated: Set[int] = set()
    def reset(self) -> None:
        u'''割付を初期化する。系全体をリセットする場合に呼び出す。
        '''
        self.allocated = set()
    def allocate1(self) -> int:
        u'''量子ビット一つを割り付け、インデックス位置を返す。
        '''
        if not self.allocated:
            self.allocated.add(0)
            return 0
        for i in range(0, max(self.allocated)):
            if i not in self.allocated:
                self.allocated.add(i)
                return i
        i = max(self.allocated) + 1
        self.allocated.add(i)
        return i
    def deallocate1(self, i: int) -> None:
        u'''量子ビット一つの割り付けを解除し、再割り当て可能にする。
        |0> に初期化された状態で返却されることを期待している。
        '''
        self.allocated.remove(i)
    def allocate(self, n: int) -> List[int]:
        u'''指定された数の量子ビットを割り付け、
        インデックス位置リストを返す。
        '''
        qbits = []
        for i in range(n):
            qbits.append(self.allocate1())
        return qbits
    def deallocate(self, qbits: List[int]) -> None:
        u'''指定された数の量子ビットを割り付け、
        インデックス位置リストを返す。
        '''
        for q in qbits:
            self.deallocate1(q)
```

allocate1 / deallocate1 は一つの $\def\ket#1{\mathinner{\left|{#1}\right\rangle}} \ket{0}$ 量子ビットを取得・返却するためのメソッドです。返却された量子ビットが $\ket{0}$ 状態であることの確認はしません。

系全体の量子ビットの割り当て状況は一意なので、グローバル変数 ALLOCATOR に置いておきます。

```python
ALLOCATOR = QubitAllocator()

def reset_all() -> None:
    ALLOCATOR.reset()
```

ユニタリ操作
------------

ユニタリ操作を以下のようなクラスで扱うことにします。
量子回路は可逆演算なので、回路の逆操作（エルミート共役）を得られるようにします。

```python
class UnitaryOperation(object):
    u'''ユニタリ操作の抽象クラス
    '''
    def __init__(self) -> None:
        pass
    def reversed(self, proc: 'UO_Procedure') -> 'UnitaryOperation':
        u'''登録されたユニタリ操作を逆順にしたものを返す
        '''
        return proc
    def synthesis(self, bq_circuit : blueqat.Circuit) -> blueqat.Circuit:
        u'''量子回路シミュレータに回路を書き込む
        '''
        return bq_circuit
    def __str__(self) -> str:
        return self.string(0)
    def string(self, depth : int) -> str:
        return ''
```

基本的なパウリゲートは以下のようなクラスで表現することにします。
とりあえず、古典的可逆回路の実現に必要に最低限必要な X ゲート CX ゲートだけ書くとこんな感じです：

```python
class UO_X(UnitaryOperation):
    u'''パウリ X ゲート
    '''
    def __init__(self, proc : UO_Procedure, x : int) -> None:
        UnitaryOperation.__init__(self)
        self.x = x
        proc.append_op(self)
    def reversd(self, proc : UO_Procedure) -> 'UO_X':
        return UO_X(proc, self.x)
    def synthesis(self, bq_circuit : blueqat.Circuit) -> blueqat.Circuit:
        bq_circuit.x[self.x]
        return bq_circuit
    def string(self, depth: int) -> str:
        return 'X[{0}]'.format(self.x)
class UO_CX(UnitaryOperation):
    u'''制御 NOT ゲート
    '''
    def __init__(self, proc: UO_Procedure, c: int, x: int) -> None:
        UnitaryOperation.__init__(self)
        self.c = c
        self.x = x
        proc.append_op(self)
    def reversed(self, proc: UO_Procedure) -> 'UO_CX':
        u'''反転しても同じ
        '''
        return UO_CX(proc, self.c, self.x)
    def synthesis(self, bq_circuit: blueqat.Circuit) -> blueqat.Circuit:
        (c, x) = (self.c, self.x)
        bq_circuit.cx[c, x]
        return bq_circuit
    def string(self, depth: int) -> str:
        return 'CX[{0},{1}]'.format(self.c, self.x)
```

基本的なユニタリ操作を一つの回路としてまとめて扱えるように、また、複数の回路要素をまとめたものを一つの回路としてまとめて扱えるように、一連のユニタリ操作をまとめて扱うクラスを用意します。

```python
class UO_Procedure(UnitaryOperation):
    u'''複数ユニタリ操作を一連のユニタリ操作としてまとめる
    '''
    def __init__(self, title: str,
                 proc: Optional['UO_Procedure'] = None) -> None:
        UnitaryOperation.__init__(self)
        self.title = title
        self.ops : List[UnitaryOperation] = []
        if proc:
            proc.append_op(self)
    def append_op(self, op : UnitaryOperation) -> None:
        u'''ユニタリ操作を登録する
        '''
        self.ops.append(op)
    def reversed(self, r : 'UO_Procedure') -> 'UO_Procedure':
        u'''登録されたユニタリ操作を逆順にしたものを返す
        '''
        rops = []
        for op in reversed(self.ops):
            rops.append(op.reversed(r))
        r.ops = rops
        return r
    def synthesis(self, bq_circuit : blueqat.Circuit) -> blueqat.Circuit:
        u'''量子回路シミュレータに回路を書き込む
        '''
        for op in self.ops:
            op.synthesis(bq_circuit)
        return bq_circuit
    def string(self, depth: int) -> str:
        s = self.title + '{\n'
        s += ',\n'.join(
            [' ' * (depth + 1) + op.string(depth + 1) for op in self.ops])
        s += '\n'
        s += ' ' * depth + '}'
        return s
```

これを使うと、加算器に必要な部品を以下のように書くことができます。

```python
class UO_Carry(UnitaryOperation):
    u'''キャリー伝搬付き加算
    '''
    def __init__(self, proc: UO_Procedure,
                 a: int, b: int, c: int, d: int,
                 is_reversed: bool=False) -> None:
        UnitaryOperation.__init__(self)
        self.a = a
        self.b = b
        self.c = c
        self.d = d
        proc.append_op(self)
        self.is_reversed = is_reversed
    def reversed(self, proc: UO_Procedure) -> 'UO_Carry':
        u'''逆演算
        '''
        (a, b, c, d) = (self.a, self.b, self.c, self.d)
        return UO_Carry(proc, a, b, c, d, not self.is_reversed)
    def synthesis(self, bq_circuit: blueqat.Circuit) -> blueqat.Circuit:
        u'''量子計算シミュレータに回路を書き込む。
        '''
        (a, b, c, d) = (self.a, self.b, self.c, self.d)
        if not self.is_reversed:
            bq_circuit.ccx[b, c, d].cx[b, c].ccx[a, c, d]
        else:
            bq_circuit.ccx[a, c, d].cx[b, c].ccx[b, c, d]
        return bq_circuit
    def string(self, depth: int) -> str:
        return (
            'Carry[{0},{1},{2},{3}]{{ ccx[{1},{2},{3}], cx[{1},{2}], ccx[{0},{2},{3}] }}'.format(self.a, self.b, self.c, self.d)
            if not self.is_reversed else
            'RCarry[{0},{1},{2},{3}]{{ ccx[{0},{2},{3}], cx[{1},{2}], ccx[{1},{2},{3}] }}'.format(self.a, self.b, self.c, self.d))
class UO_Sum(UnitaryOperation):
    def __init__(self, proc: UO_Procedure,
                 a: int, b: int, c: int,
                 is_reversed: bool = False) -> None:
        UnitaryOperation.__init__(self)
        self.a = a
        self.b = b
        self.c = c
        proc.append_op(self)
        self.is_reversed = is_reversed
    def reversed(self, proc: UO_Procedure) -> 'UO_Sum':
        u'''逆演算
        '''
        (a, b, c) = (self.a, self.b, self.c)
        return UO_Sum(proc, a, b, c, not self.is_reversed)
    def synthesis(self, bq_circuit: blueqat.Circuit) -> blueqat.Circuit:
        u'''量子計算シミュレータに回路を書き込む。
        '''
        (a, b, c) = (self.a, self.b, self.c)
        if not self.is_reversed:
            bq_circuit.cx[b, c].cx[a, c]
        else:
            bq_circuit.cx[a, c].cx[b, c]
        return bq_circuit
    def string(self, depth: int) -> str:
        return (
            'Sum[{0},{1},{2}]{{ cx[{1},{2}], cx[{0},{2}] }}'.format(self.a, self.b, self.c)
            if not self.is_reversed else
            'RSum[{0},{1},{2}]{{ cx[{0},{2}], cx[{1},{2}] }}'.format(self.a, self.b, self.c))
```

ここまでできれば、あとは UO_Carry, UO_Sum を組み合わせて加算器を作ることができます。
加算器を合成するオペレータ +=、加算器の逆演算を合成するオペレータ -= などを持つ整数クラス Integer を以下のように書きました:

```python
class Integer(object):
    NBITS = 4
    def __init__(self, proc: UO_Procedure, n: int) -> None:
        nbits = Integer.NBITS
        self.proc = proc
        self.qbits = ALLOCATOR.allocate(nbits)
        # 補助ビットは必要になるまで確保を遅延する
        self.cs : Optional[List[int]] = None
        # キャリービットも必要になるまで確保を遅延する
        self.carry : Optional[int] = None
        if n != 0:
            # 初期値を与える
            p = UO_Procedure('Integer.init')
            for i in range(0, nbits):
                if n & (1 << i) == 0:
                    continue
                UO_X(p, self.qbits[i])
            self.proc.append_op(p)
    def _deallocate(self) -> None:
        u'''補助ビットは加算・減算が終わったら即座に返却する
        （補助ビットは加減算が終わった時点で |0> になっている）。
        '''
        if self.cs:
            ALLOCATOR.deallocate(self.cs)
            self.cs = None
    def _cs(self, i: int) -> int:
        u'''補助ビット・キャリービットの獲得
        '''
        if i >= len(self.qbits):
            return self._carry()
        if not self.cs:
            self.cs = ALLOCATOR.allocate(len(self.qbits))
        return self.cs[i]
    def _carry(self) -> int:
        u'''キャリービットの獲得
        '''
        if self.carry is None:
            self.carry = ALLOCATOR.allocate1()
        return self.carry
    def __iadd__(self, other: 'Integer') -> 'Integer':
        u'''引数に与えられた Integer を加算する。
        '''
        self.proc.append_op(self._synthesis_iadd(other))
        self._deallocate()
        return self
    def __isub__(self, other: 'Integer') -> 'Integer':
        u'''引数に与えられた Integer で減算する。加算の逆操作を行う。
        '''
        p = UO_Procedure('Integer.sub')
        self.proc.append_op(self._synthesis_iadd(other).reversed(p))
        self._deallocate()
        return self
    def _synthesis_iadd(self, other: 'Integer') -> UO_Procedure:
        u'''加算回路を合成する。
        '''
        if len(other.qbits) != len(self.qbits):
            raise RuntimeError('invalid Integer bit width')
        p = UO_Procedure('Integer.add')
        for i in range(len(self.qbits)):
            a = other.qbits[i]
            b = self.qbits[i]
            c = self._cs(i)
            c2 = self._cs(i + 1)
            UO_Carry(p, c, a, b, c2)
        UO_CX(p, other.qbits[-1], self.qbits[-1])
        for i in range(len(self.qbits) - 1, 0, -1):
            a = other.qbits[i]
            b = self.qbits[i]
            c = self._cs(i)
            a1 = other.qbits[i - 1]
            b1 = self.qbits[i - 1]
            c1 = self._cs(i - 1)
            UO_Sum(p, c, a, b)
            UO_Carry(p, c1, a1, b1, c, is_reversed=True)
        UO_Sum(p, self._cs(0), other.qbits[0], self.qbits[0])
        return p
    def __lshift__(self, orig: 'Integer') -> 'Integer':
        u'''引数に与えられた Integer との XOR をとる。
        '''
        if len(orig.qbits) != len(self.qbits):
            raise RuntimeError('invalid Integer bit width')
        p = UO_Procedure('Integer.xor') 
        for c, x in zip(orig.qbits, self.qbits):
            UO_CX(p, c, x)
        # orig にキャリービットがあれば、キャリービットも XOR をとる
        if orig.carry is not None:
            UO_CX(p, orig.carry, self._carry())
        self.proc.append_op(p)
        return self
    def parse(self, s: str) -> int:
        u'''blueqat の結果出力を元に、当該量子ビット群が表す整数値を返す。
        '''
        i = s.find("'")
        s = s[i + 1:]
        n = 0
        for i in range(0, len(self.qbits)):
            if s[self.qbits[i]] == '1':
                n += (1 << i)
        if self.carry is not None and s[self.carry] == '1':
            n += (1 << len(self.qbits))
        return n
    def __str__(self) -> str:
        args = ','.join([str(q) for q in self.qbits])
        if self.carry is not None:
            args += ',' + str(self.carry)
        return 'Integer[{0}]'.format(args)
```

アダマールゲート
--------------

量子計算といえば重ね合わせです。アダマールゲートを追加すると、試行毎に異なる値を得ることができます。

```
---- circuit ----
Test:ADDH{
 Integer.hadamard{
  H[0],
  H[1],
  H[2],
  H[3]
 },
 Integer.hadamard{
  H[4],
  H[5],
  H[6],
  H[7]
 },
 Integer.xor{
  CX[4,8],
  CX[5,9],
  CX[6,10],
  CX[7,11]
 },
 Integer.add{
  Carry[12,0,4,13]{ ccx[0,4,13], cx[0,4], ccx[12,4,13] },
  Carry[13,1,5,14]{ ccx[1,5,14], cx[1,5], ccx[13,5,14] },
  Carry[14,2,6,15]{ ccx[2,6,15], cx[2,6], ccx[14,6,15] },
  Carry[15,3,7,16]{ ccx[3,7,16], cx[3,7], ccx[15,7,16] },
  CX[3,7],
  Sum[15,3,7]{ cx[3,7], cx[15,7] },
  Carry[14,2,6,15]{ ccx[2,6,15], cx[2,6], ccx[14,6,15] },
  Sum[14,2,6]{ cx[2,6], cx[14,6] },
  Carry[13,1,5,14]{ ccx[1,5,14], cx[1,5], ccx[13,5,14] },
  Sum[13,1,5]{ cx[1,5], cx[13,5] },
  Carry[12,0,4,13]{ ccx[0,4,13], cx[0,4], ccx[12,4,13] },
  Sum[12,0,4]{ cx[0,4], cx[12,4] }
 }
}
---- simulator ----
Circuit(17).h[0].h[1].h[2].h[3].h[4].h[5].h[6].h[7].cx[4, 8].cx[5, 9].cx[6, 10].cx[7, 11].ccx[0, 4, 13].cx[0, 4].ccx[12, 4, 13].ccx[1, 5, 14].cx[1, 5].ccx[13, 5, 14].ccx[2, 6, 15].cx[2, 6].ccx[14, 6, 15].ccx[3, 7, 16].cx[3, 7].ccx[15, 7, 16].cx[3, 7].cx[3, 7].cx[15, 7].ccx[2, 6, 15].cx[2, 6].ccx[14, 6, 15].cx[2, 6].cx[14, 6].ccx[1, 5, 14].cx[1, 5].ccx[13, 5, 14].cx[1, 5].cx[13, 5].ccx[0, 4, 13].cx[0, 4].ccx[12, 4, 13].cx[0, 4].cx[12, 4]
---- result ----
13+9=22
9+6=15
8+7=15
14+14=28
1+4=5
1+11=12
10+15=25
13+10=23
11+9=20
13+2=15
```

コード全体は以下のようになります。

```python
import blueqat

from typing import List, Optional, Set

# ----------------------------------------------------------------------
class QubitAllocator(object):
    u'''量子ビット管理
    '''
    def __init__(self) -> None:
        self.allocated: Set[int] = set()
    def reset(self) -> None:
        u'''割付を初期化する。系全体をリセットする場合に呼び出す。
        '''
        self.allocated = set()
    def allocate1(self) -> int:
        u'''量子ビット一つを割り付け、インデックス位置を返す。
        '''
        if not self.allocated:
            self.allocated.add(0)
            return 0
        for i in range(0, max(self.allocated)):
            if i not in self.allocated:
                self.allocated.add(i)
                return i
        i = max(self.allocated) + 1
        self.allocated.add(i)
        return i
    def deallocate1(self, i: int) -> None:
        u'''量子ビット一つの割り付けを解除し、再割り当て可能にする。
        |0> に初期化された状態で返却されることを期待している。
        '''
        self.allocated.remove(i)
    def allocate(self, n: int) -> List[int]:
        u'''指定された数の量子ビットを割り付け、
        インデックス位置リストを返す。
        '''
        qbits = []
        for i in range(n):
            qbits.append(self.allocate1())
        return qbits
    def deallocate(self, qbits: List[int]) -> None:
        u'''指定された数の量子ビットを割り付け、
        インデックス位置リストを返す。
        '''
        for q in qbits:
            self.deallocate1(q)

ALLOCATOR = QubitAllocator()

def reset_all() -> None:
    ALLOCATOR.reset()
# ----------------------------------------------------------------------
class UnitaryOperation(object):
    u'''ユニタリ操作
    '''
    def __init__(self) -> None:
        pass
    def reversed(self, proc: 'UO_Procedure') -> 'UnitaryOperation':
        u'''登録されたユニタリ操作を逆順にしたものを返す
        '''
        return proc
    def synthesis(self, bq_circuit : blueqat.Circuit) -> blueqat.Circuit:
        u'''量子回路シミュレータに回路を書き込む
        '''
        return bq_circuit
    def __str__(self) -> str:
        return self.string(0)
    def string(self, depth : int) -> str:
        return ''
class UO_Procedure(UnitaryOperation):
    u'''複数ユニタリ操作を一連のユニタリ操作としてまとめる
    '''
    def __init__(self, title: str,
                 proc: Optional['UO_Procedure'] = None) -> None:
        UnitaryOperation.__init__(self)
        self.title = title
        self.ops : List[UnitaryOperation] = []
        if proc:
            proc.append_op(self)
    def append_op(self, op : UnitaryOperation) -> None:
        u'''ユニタリ操作を登録する
        '''
        self.ops.append(op)
    def reversed(self, r : 'UO_Procedure') -> 'UO_Procedure':
        u'''登録されたユニタリ操作を逆順にしたものを返す
        '''
        rops = []
        for op in reversed(self.ops):
            rops.append(op.reversed(r))
        r.ops = rops
        return r
    def synthesis(self, bq_circuit : blueqat.Circuit) -> blueqat.Circuit:
        u'''量子回路シミュレータに回路を書き込む
        '''
        for op in self.ops:
            op.synthesis(bq_circuit)
        return bq_circuit
    def string(self, depth: int) -> str:
        s = self.title + '{\n'
        s += ',\n'.join(
            [' ' * (depth + 1) + op.string(depth + 1) for op in self.ops])
        s += '\n'
        s += ' ' * depth + '}'
        return s
class UO_H(UnitaryOperation):
    u'''アダマール演算
    '''
    def __init__(self, proc : UO_Procedure, x : int) -> None:
        UnitaryOperation.__init__(self)
        self.x = x
        proc.append_op(self)
    def reversed(self, proc : UO_Procedure) -> 'UO_X':
        return UO_H(proc, self.x)
    def synthesis(self, bq_circuit : blueqat.Circuit) -> blueqat.Circuit:
        bq_circuit.h[self.x]
        return bq_circuit
    def string(self, depth: int) -> str:
        return 'H[{0}]'.format(self.x)
class UO_X(UnitaryOperation):
    u'''パウリ X ゲート
    '''
    def __init__(self, proc : UO_Procedure, x : int) -> None:
        UnitaryOperation.__init__(self)
        self.x = x
        proc.append_op(self)
    def reversd(self, proc : UO_Procedure) -> 'UO_X':
        return UO_X(proc, self.x)
    def synthesis(self, bq_circuit : blueqat.Circuit) -> blueqat.Circuit:
        bq_circuit.x[self.x]
        return bq_circuit
    def string(self, depth: int) -> str:
        return 'X[{0}]'.format(self.x)
class UO_CX(UnitaryOperation):
    u'''制御 NOT ゲート
    '''
    def __init__(self, proc: UO_Procedure, c: int, x: int) -> None:
        UnitaryOperation.__init__(self)
        self.c = c
        self.x = x
        proc.append_op(self)
    def reversed(self, proc: UO_Procedure) -> 'UO_CX':
        u'''反転しても同じ
        '''
        return UO_CX(proc, self.c, self.x)
    def synthesis(self, bq_circuit: blueqat.Circuit) -> blueqat.Circuit:
        (c, x) = (self.c, self.x)
        bq_circuit.cx[c, x]
        return bq_circuit
    def string(self, depth: int) -> str:
        return 'CX[{0},{1}]'.format(self.c, self.x)
class UO_Carry(UnitaryOperation):
    u'''キャリー伝搬付き加算
    '''
    def __init__(self, proc: UO_Procedure,
                 a: int, b: int, c: int, d: int,
                 is_reversed: bool=False) -> None:
        UnitaryOperation.__init__(self)
        self.a = a
        self.b = b
        self.c = c
        self.d = d
        proc.append_op(self)
        self.is_reversed = is_reversed
    def reversed(self, proc: UO_Procedure) -> 'UO_Carry':
        u'''逆演算
        '''
        (a, b, c, d) = (self.a, self.b, self.c, self.d)
        return UO_Carry(proc, a, b, c, d, not self.is_reversed)
    def synthesis(self, bq_circuit: blueqat.Circuit) -> blueqat.Circuit:
        u'''量子計算シミュレータに回路を書き込む。
        '''
        (a, b, c, d) = (self.a, self.b, self.c, self.d)
        if not self.is_reversed:
            bq_circuit.ccx[b, c, d].cx[b, c].ccx[a, c, d]
        else:
            bq_circuit.ccx[a, c, d].cx[b, c].ccx[b, c, d]
        return bq_circuit
    def string(self, depth: int) -> str:
        return (
            'Carry[{0},{1},{2},{3}]{{ ccx[{1},{2},{3}], cx[{1},{2}], ccx[{0},{2},{3}] }}'.format(self.a, self.b, self.c, self.d)
            if not self.is_reversed else
            'RCarry[{0},{1},{2},{3}]{{ ccx[{0},{2},{3}], cx[{1},{2}], ccx[{1},{2},{3}] }}'.format(self.a, self.b, self.c, self.d))
class UO_Sum(UnitaryOperation):
    def __init__(self, proc: UO_Procedure,
                 a: int, b: int, c: int,
                 is_reversed: bool = False) -> None:
        UnitaryOperation.__init__(self)
        self.a = a
        self.b = b
        self.c = c
        proc.append_op(self)
        self.is_reversed = is_reversed
    def reversed(self, proc: UO_Procedure) -> 'UO_Sum':
        u'''逆演算
        '''
        (a, b, c) = (self.a, self.b, self.c)
        return UO_Sum(proc, a, b, c, not self.is_reversed)
    def synthesis(self, bq_circuit: blueqat.Circuit) -> blueqat.Circuit:
        (a, b, c) = (self.a, self.b, self.c)
        if not self.is_reversed:
            bq_circuit.cx[b, c].cx[a, c]
        else:
            bq_circuit.cx[a, c].cx[b, c]
        return bq_circuit
    def string(self, depth: int) -> str:
        return (
            'Sum[{0},{1},{2}]{{ cx[{1},{2}], cx[{0},{2}] }}'.format(self.a, self.b, self.c)
            if not self.is_reversed else
            'RSum[{0},{1},{2}]{{ cx[{0},{2}], cx[{1},{2}] }}'.format(self.a, self.b, self.c))

    
class Integer(object):
    NBITS = 4
    def __init__(self, proc: UO_Procedure, n: int) -> None:
        nbits = Integer.NBITS
        self.proc = proc
        self.qbits = ALLOCATOR.allocate(nbits)
        # 補助ビットは必要になるまで確保を遅延する
        self.cs : Optional[List[int]] = None
        # キャリービットも必要になるまで確保を遅延する
        self.carry : Optional[int] = None
        if n != 0:
            # 初期値を与える
            p = UO_Procedure('Integer.init')
            for i in range(0, nbits):
                if n & (1 << i) == 0:
                    continue
                UO_X(p, self.qbits[i])
            self.proc.append_op(p)
    def _deallocate(self) -> None:
        u'''補助ビットは加算・減算が終わったら即座に返却する
        （補助ビットは加減算が終わった時点で |0> になっている）。
        '''
        if self.cs:
            ALLOCATOR.deallocate(self.cs)
            self.cs = None
    def _cs(self, i: int) -> int:
        u'''補助ビット・キャリービットの獲得
        '''
        if i >= len(self.qbits):
            return self._carry()
        if not self.cs:
            self.cs = ALLOCATOR.allocate(len(self.qbits))
        return self.cs[i]
    def _carry(self) -> int:
        u'''キャリービットの獲得
        '''
        if self.carry is None:
            self.carry = ALLOCATOR.allocate1()
        return self.carry
    def __iadd__(self, other: 'Integer') -> 'Integer':
        u'''引数に与えられた Integer を加算する。
        '''
        self.proc.append_op(self._synthesis_iadd(other))
        self._deallocate()
        return self
    def __isub__(self, other: 'Integer') -> 'Integer':
        u'''引数に与えられた Integer で減算する。加算の逆操作を行う。
        '''
        p = UO_Procedure('Integer.sub')
        self.proc.append_op(self._synthesis_iadd(other).reversed(p))
        self._deallocate()
        return self
    def _synthesis_iadd(self, other: 'Integer') -> UO_Procedure:
        u'''加算回路を合成する。
        '''
        if len(other.qbits) != len(self.qbits):
            raise RuntimeError('invalid Integer bit width')
        p = UO_Procedure('Integer.add')
        for i in range(len(self.qbits)):
            a = other.qbits[i]
            b = self.qbits[i]
            c = self._cs(i)
            c2 = self._cs(i + 1)
            UO_Carry(p, c, a, b, c2)
        UO_CX(p, other.qbits[-1], self.qbits[-1])
        for i in range(len(self.qbits) - 1, 0, -1):
            a = other.qbits[i]
            b = self.qbits[i]
            c = self._cs(i)
            a1 = other.qbits[i - 1]
            b1 = self.qbits[i - 1]
            c1 = self._cs(i - 1)
            UO_Sum(p, c, a, b)
            UO_Carry(p, c1, a1, b1, c, is_reversed=True)
        UO_Sum(p, self._cs(0), other.qbits[0], self.qbits[0])
        return p
    def __lshift__(self, orig: 'Integer') -> 'Integer':
        u'''引数に与えられた Integer との XOR をとる。
        '''
        if len(orig.qbits) != len(self.qbits):
            raise RuntimeError('invalid Integer bit width')
        p = UO_Procedure('Integer.xor') 
        for c, x in zip(orig.qbits, self.qbits):
            UO_CX(p, c, x)
        # orig にキャリービットがあれば、キャリービットも XOR をとる
        if orig.carry is not None:
            UO_CX(p, orig.carry, self._carry())
        self.proc.append_op(p)
        return self
    def hadamard(self) -> 'Integer':
        p = UO_Procedure('Integer.hadamard') 
        for i in range(0, len(self.qbits)):
            UO_H(p, self.qbits[i])
        self.proc.append_op(p)
    def parse(self, s: str) -> int:
        u'''blueqat の結果出力を元に、当該量子ビット群が表す整数値を返す。
        '''
        i = s.find("'")
        s = s[i + 1:]
        n = 0
        for i in range(0, len(self.qbits)):
            if s[self.qbits[i]] == '1':
                n += (1 << i)
        if self.carry is not None and s[self.carry] == '1':
            n += (1 << len(self.qbits))
        return n
    def __str__(self) -> str:
        args = ','.join([str(q) for q in self.qbits])
        if self.carry is not None:
            args += ',' + str(self.carry)
        return 'Integer[{0}]'.format(args)
# ----------------------------------------------------------------------
class TestProc_ADDSUB(UO_Procedure):
    def __init__(self, i: int, j: int) -> None:
        UO_Procedure.__init__(self, 'Test:ADDSUB')
        #
        #   回路の作成
        #
        # 整数は４量子ビットで表現する。
        Integer.NBITS = 4
        # 加減算に用いる２つの整数を用意する。
        a = Integer(self, i)
        b = Integer(self, j)
        # 途中の計算結果を取り出すための整数を用意する。
        c = Integer(self, 0)
        # 足し算 (b = b + a) を行う。
        b += a
        # 0 に b の XOR を作用させることで足し算の結果を c に取り出しておく。
        # Python に ^= はないようなので << で代用。
        c << b
        # 減算（足し算の逆演算）して b をもとに戻す (b = b - a)。
        b -= a
        # どの量子変数を割り付けたか確認できるように self に記録しておく。
        self.b = b
        self.c = c
class TestProc_ADDH(UO_Procedure):
    def __init__(self) -> None:
        UO_Procedure.__init__(self, 'Test:ADDH')
        #
        #   回路の作成
        #
        # 整数は４量子ビットで表現する。
        Integer.NBITS = 4
        # 加算に用いる２つの整数を用意する。
        a = Integer(self, 0)
        b = Integer(self, 0)
        # b の加算前の値を待避するための変数
        b0 = Integer(self, 0)
        a.hadamard()
        b.hadamard()
        b0 << b
        # 足し算 (b = b + a) を行う。
        b += a
        # どの量子変数を割り付けたか確認できるように self に記録しておく。
        self.a = a
        self.b = b
        self.b0 = b0

# 回路を合成する
p = TestProc_ADDH()
# 合成した回路を表示する
print('---- circuit ----')
print(str(p))
# シミュレータ実行
print('---- simulator ----')
circuit = p.synthesis(blueqat.Circuit())
print(str(circuit))
print('---- result ----')
for _ in range(10):
    result = str(circuit.m[:].run(shots=1))
    print('{0}+{1}={2}'.format(
        p.a.parse(result),
        p.b0.parse(result),
        p.b.parse(result)))
```