Zenn
🌐

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

2021/10/01に公開
量子コンピュータ
#
量子計算
qiskit
#
量子算術演算
#
量子回路
tech

量子算術演算は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

xor2

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

AND

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

and3

OR

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

or3

XOR

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

xor3

1桁同士の加算回路

半加算器

wikipediaより
(↑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)
なので、次のような量子回路を組むことができます。

full_adder

実装例

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

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

ここで、実行例として、"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())

adder_big_endian_hist
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
MAJ
UMA
UMA
これらの回路は、次のような効果をもたらします。

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

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

また、上の回路はより浅くすることができて、論文内では次のように構成できることが示されています。
qc_ripple_shallow
(画像は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

これを図示すると、
qc_ripple
このようになります。
実行例として、"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())

ripple_hist

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の時でも、分母と打ち消しあって、一つ上の桁に自動的にキャリーがされるという点です。

この操作を図示したのが、以下の図です。(下図はリトルエンディアンであることに注意！！)
qft_const_adder
(画像は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())

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

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をマイナスにすれば大丈夫です。
また、量子回路を表示してみると、次のようになります。
qc_qft_adder

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

終わりに

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

Discussion