量子算術演算覚え書き(加算器編)

量子算術演算はQRAMのエンコーディングや、量子フーリエ変換において冪乗余演算をする際に登場します。
今回は算術演算の中でも特に加算回路について、いくつかの手法を実装例付きでまとめてみました。

AND, OR, XOR

2-qubitでできる2入力の論理演算

AND

$$|A\rangle|B\rangle \rightarrow |A\rangle|A \cdot B\rangle$$

$$.\ \ \ 00 \ \ 01 \ \ 10 \ \ 11\\ \begin{matrix} 00\\ 01\\ 10\\ 11 \end{matrix} \left( \begin{matrix} 1 & 0 & 0 & 0 \\ 0 & 1 & 0 & 0 \\ 0 & 0 & 1 & 0 \\ 0 & 0 & 1 & 0 \end{matrix} \right)$$

これはユニタリではないので、実現できません。

OR

$$|A\rangle|B\rangle \rightarrow |A\rangle|A + B\rangle$$

$$.\ \ \ 00 \ \ 01 \ \ 10 \ \ 11\\ \begin{matrix} 00\\ 01\\ 10\\ 11 \end{matrix} \left( \begin{matrix} 1 & 0 & 0 & 0 \\ 0 & 1 & 0 & 0 \\ 0 & 0 & 0 & 1 \\ 0 & 0 & 0 & 1 \end{matrix} \right)$$

これはユニタリではないので、実現できません。

XOR

$$|A\rangle|B\rangle \rightarrow |A\rangle|A \oplus B\rangle$$

$$.\ \ \ 00 \ \ 01 \ \ 10 \ \ 11\\ \begin{matrix} 00\\ 01\\ 10\\ 11 \end{matrix} \left( \begin{matrix} 1 & 0 & 0 & 0 \\ 0 & 1 & 0 & 0 \\ 0 & 0 & 0 & 1 \\ 0 & 0 & 1 & 0 \end{matrix} \right)$$

制御NOTでOK

3-qubitでできる2入力の論理演算 (補助量子ビット1個)

AND

$$|A\rangle|B\rangle|0\rangle \rightarrow |A\rangle|B\rangle|A \cdot B\rangle$$

OR

$$|A\rangle|B\rangle|0\rangle \rightarrow |A\rangle|B\rangle|A + B\rangle$$

XOR

$$|A\rangle|B\rangle|0\rangle \rightarrow |A\rangle|B\rangle|A \oplus B\rangle$$

1桁同士の加算回路

半加算器

(↑wiki引用)

をまねるだけ。

$$|A\rangle|B\rangle|0\rangle \rightarrow |S\rangle|B\rangle|C\rangle$$

全加算器

$$|A\rangle|B\rangle|C_{in}\rangle|0\rangle \rightarrow |A\rangle|B\rangle|S\rangle|C\rangle$$

全加算器の真理値表は次のようになります。

$A$	$B$	$C_{in}$	$S$	$C$
0	0	0	0	0
0	0	1	1	0
0	1	0	1	0
0	1	1	0	1
1	0	0	1	0
1	0	1	0	1
1	1	0	0	1
1	1	1	1	1

これと睨めっこすると、
$S = A\oplus B \oplus C_{in}$
$C = (A\cdot B)\oplus (B\cdot C_{in}) \oplus (C_{in}\cdot A)$
なので、次のような量子回路を組むことができます。

実装例

def full_adder(to_gate = True):
    qr_a = QuantumRegister(1, "a")
    qr_b = QuantumRegister(1, "b")
    qr_cin = QuantumRegister(1, "cin")
    qr_zero = QuantumRegister(1, "zero")
    qc = QuantumCircuit(qr_a, qr_b, qr_cin, qr_zero)
    
    qc.ccx(qr_a,qr_b,qr_zero)
    qc.cx(qr_a,qr_b)
    qc.ccx(qr_b,qr_cin,qr_zero)
    qc.cx(qr_b,qr_cin)
    qc.cx(qr_a,qr_b)
    return qc.to_gate(label="full_adder") if to_gate else qc

2桁以上同士の加算回路

全加算器の直列連結

ただ全加算器を直列に繋ぐだけで、2桁以上同士の加算回路が実現できます。

$$|A\rangle|B\rangle|C_{in}\rangle|0\cdots 0\rangle \rightarrow |A\rangle|B\rangle|S_0\rangle|S_1\cdots S_{n}\rangle$$

以下、ビッグエンディアンで整数をエンコードした場合の実装例です。

def adder_big_endian(num_digit, to_gate = True):

    qr_cin = QuantumRegister(1)
    qr_a = QuantumRegister(num_digit)
    qr_b = QuantumRegister(num_digit)
    qr_zero = QuantumRegister(num_digit)
    qc = QuantumCircuit(qr_a, qr_b, qr_cin, qr_zero)
    
    qc.append(full_adder(), [qr_a[0], qr_b[0], qr_cin[0], qr_zero[0]])
    for i in range(1, num_digit):
        qc.append(full_adder(), [qr_a[i], qr_b[i], qr_zero[i - 1], qr_zero[i]])
    
    return qc.to_gate(label="adder") if to_gate else qc

これを回路で表示してみると、

ここで、実行例として、"10110" + "01100" = "100010"をやってみます。

qc = QuantumCircuit(5 + 5 + 5 + 1, 6)
qc.x([1, 2, 4])
qc.x([5 + 2, 5 + 3])
qc.append(adder_big_endian(5), range(5 + 5 + 5 + 1))
qc.measure(range(5 + 5, 5 + 5 + 5 + 1), range(6))
plot_histogram(execute(qc, backend=Aer.get_backend("qasm_simulator")).result().get_counts())

qiskitもビッグエンディアンで測定なので、エンディアンが揃って､測定結果がそのまま普通の2進数として読めます。

Ripple Carry Adder

Steven A. Cuccaro, Thomas G. Draper, Samuel A. Kutin, David Petrie Moultonによる、A new quantum ripple-carry addition circuitを参照。

エンディアンに注意!!

上記論文と、以下の実装は、ビッグエンディアンで実装されています。

$a = a_{n-1}a_{n-2}\cdots a_1a_0$ と、$b = b_{n-1}b_{n-2}\cdots b_1b_0$を整数、
$A, B$を量子レジスタとするとき、$a,b$を次のように$A, B$に格納します。

$a_i$を$A_i$、$b_i$を$B_i$に対応させる。

qiskitなど、量子ビットのブラケット表記は基本的にリトルエンディアンが主流なので、この表記に合わせると、ripple carry adderの挙動は、次のようになります。

$$|0\rangle|a\rangle|b\rangle|0\rangle = |0\rangle|A_{0}A_{1}\cdots A_{n-2}A_{n-1}\rangle|B_{0}B_{1}\cdots B_{n-2}B_{n-1}\rangle|C_{in}\rangle \rightarrow |0\rangle|a\rangle|a+b\rangle|Carry\rangle$$

これを実現するには、次のin-place MAJority gate (MAJ)とUnMajority and Add gate(UMA)を使用します。

def MAJ(to_gate= True):
    qc = QuantumCircuit(3)
    qc.cx(2, 1)
    qc.cx(2, 0)
    qc.ccx(0, 1, 2)
    return qc.to_gate(label=" MAJ ") if to_gate else qc

def UMA(to_gate = True):
    qc = QuantumCircuit(3)
    qc.ccx(0, 1, 2)
    qc.cx(2, 0)
    qc.cx(0, 1)
    return qc.to_gate(label=" UMA ") if to_gate else qc

これを量子回路として描画すると、次のようになります。
MAJ

UMA

これらの回路は、次のような効果をもたらします。

(画像はA new quantum ripple-carry addition circuitより)

これを、

こんな感じでつなげていきます。(画像はA new quantum ripple-carry addition circuitより)

また、上の回路はより浅くすることができて、論文内では次のように構成できることが示されています。

(画像はA new quantum ripple-carry addition circuitより)

実装例は以下のようになります。

def ripple_carry_adder_big_endian(num_digit, to_gate = True):
    """
    |0>|A>|B>|Z> -> |0>|A>|A+B>|Carry>
    """
    qr_a = QuantumRegister(num_digit)
    qr_b = QuantumRegister(num_digit)
    qr_c0 = QuantumRegister(1)
    qr_zero = QuantumRegister(1)
    qc = QuantumCircuit(qr_c0, qr_a, qr_b, qr_zero)
    
    qc.append(MAJ(), [qr_c0[0], qr_b[0], qr_a[0]])
    for i in range(num_digit - 1):
        qc.append(MAJ(), [qr_a[i], qr_b[i + 1], qr_a[i + 1]])
    
    qc.cx(qr_a[-1], qr_zero)
    
    for i in range(num_digit - 1)[::-1]:
        qc.append(UMA(), [qr_a[i], qr_b[i + 1], qr_a[i + 1]])
    qc.append(UMA(), [qr_c0[0], qr_b[0], qr_a[0]])
    
    return qc.to_gate(label="ripple_adder") if to_gate else qc

これを図示すると、

このようになります。
実行例として、"10110" + "01100" = "100010"をやってみます。

qc = QuantumCircuit(5 + 5 + 1 + 1, 6)
qc.x([1 + 1, 1 + 2, 1 + 4])
qc.x([1 + 5 + 2, 1 + 5 + 3])
qc.append(ripple_carry_adder_big_endian(5), range(5 + 5 + 1 + 1))
qc.measure(range(5 + 1, 5 + 5 + 1 + 1), range(6))
plot_histogram(execute(qc, backend=Aer.get_backend("qasm_simulator")).result().get_counts())

QFT Adder

Lidia Ruiz-Perez and Juan Carlos Garcia-Escartin　のQuantum arithmetic with the Quantum Fourier Transformを参照しています。

エンディアンに注意!!

上記の論文はリトルエンディアンで解説されていますが、以下の実装と説明はビッグエンディアンで説明しています。

QFT Adderは、まず全体にQFTを掛け､算術演算を位相で行ってから、IQFTで戻すというアイデアです。
オリジナルのアイデアはDraperのAddition on a Quantum Computerによります。
算術演算の本処理を位相操作で行う利点として、これがローカルなゲートの浅い回路で実現できる点が挙げられます。

具体的に見てみます。

QFTは次のような操作で、$n$-qubitで表された整数$a$について、キャリーも考慮して、$N = 2^{n + 1}$ とすると、以下の式のように、qubitにエンコードされた整数$a$を位相の部分にエンコードすることができます。

$$\begin{aligned} |\phi(A)\rangle &=Q F T|a\rangle \\ &=\frac{1}{\sqrt{N}} \sum_{k=0}^{N-1} e^{i \frac{2 \pi A k}{N}}|k\rangle \\ &= \frac{1}{\sqrt{N}} \sum_{k=0}^{N-1} e^{i \frac{2 \pi \left( \sum_{i = 0}^{n} A_i 2^{i} \right) k}{2^{n+1}}}|k\rangle \\ &= \frac{1}{\sqrt{N}} \sum_{k=0}^{N-1} \prod_{i=0}^{n} e^{i \frac{2 \pi \left( A_i 2^{i} \right) k}{2^{n + 1}}}|k\rangle \end{aligned}$$

これを、例えば、$a + b$を行いたい時には、

$$|\phi(A + B)\rangle=\frac{1}{\sqrt{N}} \sum_{k=0}^{N-1} e^{i \frac{2 \pi (A + B) k}{N}}|k\rangle \left(=Q F T|a\rangle\right)$$

をなるべく効率的に実現できればいいわけです。

もっと具体的には、QFTされた後の重ね合わされたそれぞれの"位相"状態$|k\rangle$において、$b$の$s$番目のqubitに対して、$a, b$の$j$番目のqubitに関する加算操作を作用させるには、次式のように、$b_j$が1の時のみ、$s$番目のqubitに対して次の操作を行います。

$$e^{2 \pi i \frac{\left(a_{j}+b_{j}\right) 2^{n-j} k_{s} 2^{n+1-s}}{2^{n+1}}}=e^{2 \pi i \frac{\left(a_{j}+b_{j}\right) k_{s}}{2^{j+s-n}}}$$

ここで肝なのが、$a_j + b_j$が2の時でも、分母と打ち消しあって、一つ上の桁に自動的にキャリーがされるという点です。

この操作を図示したのが、以下の図です。(下図はリトルエンディアンであることに注意！！)

(画像はQuantum arithmetic with the Quantum Fourier Transformより)
ここで、位相回転の操作を以下に表す$R_{l}$とします。

$$R_{l}=\left[\begin{array}{cc} 1 & 0 \\ 0 & e^{\frac{2 \pi i}{2^{l}}} \end{array}\right]$$

この操作は、

$$R_l |0\rangle = |0\rangle$$

$$R_l |1\rangle = e^{\frac{2 \pi i}{2^{l}}}|1\rangle$$

具体例で見た方が早いかもしれません。
"11" + "01" = "100"を例に取ると、次のようになります。

$$\begin{aligned} |\phi(A)\rangle &= \frac{1}{\sqrt{8}} \sum_{k=0}^{7} e^{2 \pi i k } e^{0.011_2} |k\rangle \\ |\phi(B)\rangle &= \frac{1}{\sqrt{8}} \sum_{k=0}^{7} e^{2 \pi i k } e^{0.001_2} |k\rangle \end{aligned}$$

$$\begin{aligned} |\phi(A + B)\rangle &= (I\otimes I\otimes R_1)|\phi(A)\rangle \\ &= \frac{1}{\sqrt{8}} \sum_{k=0}^{7} e^{2 \pi i k } e^{0.011_2 + 0.001_2} |k\rangle\\ &= \frac{1}{\sqrt{8}} \sum_{k=0}^{7} e^{2 \pi i k } e^{0.100_2} |k\rangle \end{aligned}$$

QFT　Adderの最大の利点は、連続して何回も加算操作をする際に、QFTとIQFTが相殺されて、回路がその分浅くなる点です。

QFT Const Adder

定数$C$を加算するときは、controlの部分を古典で行うことができます。
よって、$A \rightarrow A + C$をしたいときは、$A$に該当する量子レジスタのみ用意すれば十分です。

$$|A\rangle|0\rangle \rightarrow |A + C\rangle|Carry\rangle$$

以下に実装例を示します。

def qft_const_adder_big_endian(num_digit: int, const: int, to_gate=True) -> Union[Gate, QuantumCircuit]:
    
    sub, const = (True, - const) if const < 0 else (False, const)
    sign = "-" if sub else "+"
    const = const % (2 ** num_digit)
    
    qc = QuantumCircuit(num_digit + 1)
    
    qc.append( QFT(num_digit + 1, approximation_degree=0, do_swaps=False, inverse=False, name='QFT').to_gate(), range(0, num_digit + 1) )
    for i in range(0, num_digit): # qubits to be applied
        for j in range(0, num_digit - i): # 
            if const >> (num_digit - 1 - (i + j)) & 1:
                if sub:
                    qc.p(-pi / (2 ** j), num_digit - 1 - i)
                else:
                    qc.p(pi / (2 ** j), num_digit - 1 - i)
    for j in range(0, num_digit):
        if const >> (num_digit - 1 - j) & 1:
            if sub:
                qc.p(-pi / (2 ** (j + 1)), num_digit)
            else:
                qc.p(pi / (2 ** (j + 1)), num_digit)
    qc.append( QFT(num_digit + 1, approximation_degree=0, do_swaps=False, inverse=True, name='IQFT').to_gate(), range(0, num_digit + 1) )
    
    return qc.to_gate(label=" [" + sign + str(const) + "] ") if to_gate else qc

例によって、"10110" + "01100" = "100010"を実行してみると、

qc = QuantumCircuit(6, 6)
qc.x([1, 2, 4])
qc.append(qft_const_adder_big_endian(5, int("01100", 2)), range(6))
qc.measure(range(0, 6), range(6))
plot_histogram(execute(qc, backend=Aer.get_backend("qasm_simulator")).result().get_counts())

次のような結果になります。

QFT Arithmetic Adder

異なる量子レジスタにエンコードされた2つの整数$A, B$に対して、$A \rightarrow A + B$をやろうとしてる回路で、これもLidia Ruiz-Perez and Juan Carlos Garcia-Escartin　のQuantum arithmetic with the Quantum Fourier Transformを参照しています。

上のRipple Carry Adderと実装を合わせるため、最初に来るのが$A$, 後に来るのが$B$、最終結果は$B\rightarrow A + B$とします。
つまり、

$$|A\rangle|B\rangle|0\rangle \rightarrow |A\rangle|A + B\rangle|Carry\rangle$$

とします。

実装例は以下のようになります。

def qft_adder_big_endian(num_digit: int, to_gate=True) -> Union[Gate, QuantumCircuit]:
    
    qc = QuantumCircuit(2 * num_digit + 1)
    
    qc.append( QFT(num_digit + 1, approximation_degree=0, do_swaps=False, inverse=False, name='QFT').to_gate(), range(num_digit, 2 * num_digit + 1) )
    for i in range(0, num_digit):
        for j in range(0, num_digit - i):
            qc.append(PhaseGate(pi / (2 ** (num_digit - 1 - i - j) )).control(), [j, 2 * num_digit - 1 - i])
    for j in range(0, num_digit):
        qc.append(PhaseGate(pi / (2 ** (num_digit - j))).control(), [j, 2 * num_digit])
    qc.append( QFT(num_digit + 1, approximation_degree=0, do_swaps=False, inverse=True, name='IQFT').to_gate(), range(num_digit, 2 * num_digit + 1) )
    
    return qc.to_gate(label=" [ qft_adder ] ") if to_gate else qc

加算の場合のみ示していますが､ 減算の場合はphase rotationをマイナスにすれば大丈夫です。
また、量子回路を表示してみると、次のようになります。

そして、"10110" + "01100" = "100010"の実行結果は次のようになります。

終わりに

他にも多種多様な手法が提案されていますが、今回は加算回路のほんの一部の手法を実装付きで紹介しました。
乗算のまとめもやろうと思っていますが、それはまたの機会に投稿します。
ぜひそちらも参考にしていただければです！