量子算術演算覚え書き(加算器編)
量子算術演算はQRAMのエンコーディングや、量子フーリエ変換において冪乗余演算をする際に登場します。
今回は算術演算の中でも特に加算回路について、いくつかの手法を実装例付きでまとめてみました。
AND, OR, XOR
2-qubitでできる2入力の論理演算
AND
これはユニタリではないので、実現できません。
OR
これはユニタリではないので、実現できません。
XOR
制御NOTでOK
3-qubitでできる2入力の論理演算 (補助量子ビット1個)
AND
OR
XOR
1桁同士の加算回路
半加算器
(↑wiki引用)
をまねるだけ。
全加算器
全加算器の真理値表は次のようになります。
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 |
これと睨めっこすると、
なので、次のような量子回路を組むことができます。
実装例
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桁以上同士の加算回路が実現できます。
以下、ビッグエンディアンで整数をエンコードした場合の実装例です。
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を参照。
エンディアンに注意!!
上記論文と、以下の実装は、ビッグエンディアンで実装されています。
qiskitなど、量子ビットのブラケット表記は基本的にリトルエンディアンが主流なので、この表記に合わせると、ripple carry adderの挙動は、次のようになります。
これを実現するには、次の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は次のような操作で、
これを、例えば、
をなるべく効率的に実現できればいいわけです。
もっと具体的には、QFTされた後の重ね合わされたそれぞれの"位相"状態
ここで肝なのが、
この操作を図示したのが、以下の図です。(下図はリトルエンディアンであることに注意!!)
(画像はQuantum arithmetic with the Quantum Fourier Transformより)
ここで、位相回転の操作を以下に表す
この操作は、
具体例で見た方が早いかもしれません。
"11" + "01" = "100"を例に取ると、次のようになります。
QFT Adderの最大の利点は、連続して何回も加算操作をする際に、QFTとIQFTが相殺されて、回路がその分浅くなる点です。
QFT Const Adder
定数
よって、
以下に実装例を示します。
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つの整数
上のRipple Carry Adderと実装を合わせるため、最初に来るのが
つまり、
とします。
実装例は以下のようになります。
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"の実行結果は次のようになります。
終わりに
他にも多種多様な手法が提案されていますが、今回は加算回路のほんの一部の手法を実装付きで紹介しました。
乗算のまとめもやろうと思っていますが、それはまたの機会に投稿します。
ぜひそちらも参考にしていただければです!
Discussion