量子回路における加算器（2020年 Week1a）

量子回路における加算器（2020年 Week1a）#

はじめに#

本演習では、量子回路を用いて、古典論理回路による加算器と論理的に等価な回路を作成することを目的とします。
本演習を行うにあたり、必要となる前提知識は以下の通りです。可能な限り下記項目の概要を調べ、理解しておくことを推奨します。

演習ではまず最初に量子回路を使った様々な論理ゲート（AND, OR, XORなど）と、ブロッホ球表示について扱います。 その後、古典の加算器と等価な計算を量子回路で実現する方法を演習を通して学ぶことができます。下記の通り、演習を通して量子計算手法の基礎を身に着けることができます。

# 標準のQiskitライブラリーをインポートしてアカウントを構成する
from qiskit import QuantumRegister, ClassicalRegister, QuantumCircuit
from qiskit.quantum_info import Statevector
from qiskit.primitives import StatevectorSampler

量子回路の基礎#

量子回路とは？

量子回路は、量子計算の過程を記述する手法の１つで、基本的な操作を行う量子ゲートを組み合わせて構成されます。本章ではまず、いくつかの主要な量子ゲートをご紹介します。
以下より、さっそく基本的な単一量子ゲートを動かしてみましょう

ブロッホ球とは？

ブロッホ球とは、量子ビットの状態を単位球面上に表す表記法です。量子ビットの任意の純粋状態 \(\ket \psi\) は \(\ket 0\) と \(\ket 0\) の重ね合わせで表現できるため、ブロッホ球上の極座標として表現することができます。
（簡単に数式で説明すると、、、）
\(\ket 0\)と \(\ket 0\) の重ね合わせ状態を式で表すと、このようになります。$\( \ket \psi = \alpha \ket 0 + \beta \ket 1\)\( 重ね合わせ状態のうち、\)\alpha\( は \)\ket 0\( の占める割合、\)\beta\( は \)\ket 0\( の占める割合であり（確率振幅）、以下の式が成り立ちます。\)\( |\alpha|^2 + |\beta|^2 = 1 \)\( 例えば、単純な量子ビット \) \ket 0 \(と、重ね合わせ状態 \) (1 / \sqrt 2)(\ket 0 + \ket 1)$ をブロッホ球で表現すると以下のように表されます。

# 単純な量子ビット|0>のブロッホ球表示
qc = QuantumCircuit(1)

psi = Statevector(qc)
psi.draw("bloch")
_images/6f35591211ce2e61df0c5cb4c8483fe7fc7425da825f48278498c45482eff4ed.png 
# 重ね合わせ状態 1/√2 (|0> + |1>)
qc = QuantumCircuit(1)
qc.h(0)

psi = Statevector(qc)
psi.draw("bloch")
_images/7c94e552a71bb312890ed43d6b09b5cb3a5a33501fb7a60b9d124e7b32f64289.png

Xゲート#

Xゲートはブロッホ球の\(x\)軸周りの\(\pi\)回転です。 すなわち、 \(\ket 0\) にXゲートを適用すると \(\ket 1\) 、 \(\ket 1\) にXゲートを適用すると \(\ket 0\) になるので、古典のNOTゲートのような操作が実現でき、ビット反転とも呼ばれます。

xゲートを代数的に表現すると下記のように表されます。

\(X = \begin{pmatrix} 0 & 1 \\ 1 & 0 \\ \end{pmatrix}\)

# |0> qubitにXゲートをかけてみましょう
qc = QuantumCircuit(1)
qc.x(0)
qc.draw(output='mpl')
_images/32dfdd1ba5612cd5b8ff614a25f64d893f2c9f378e3975a5b82c3dce4edda923.png

ブロッホ球表示で結果を見てみましょう。初期状態\(\ket 0\)がビット反転して、\(\ket 1\)となっていれば成功です！

psi = Statevector(qc)
psi.draw("bloch")
_images/c2e3c3a1703d65b9b49c508ab224ea6f0b84f6b155a97beb5e0c1e513d11f152.png

Hゲート#

Hadamardゲート(アダマールゲート)はブロッホ球の\(x\)軸と\(z\)軸の中間の軸周りの\(\pi\)回転です。 例えば\(|0\rangle\)にHゲートを適用すると、\(\frac{|0\rangle + |1\rangle}{\sqrt{2}}\)のような重ね合わせ状態（測定すると0または1になる確率が等しい状態）を作ることができます。この状態は\(|+\rangle\)とも表記されます。

Hゲートを代数的に表現すると以下のように表されます。

\(H = \frac{1}{\sqrt{2}}\begin{pmatrix} 1 & 1 \\ 1 & -1 \\ \end{pmatrix}\)

# |0> qubitにHゲートをかけてみましょう
qc = QuantumCircuit(1)
qc.h(0)
qc.draw(output='mpl')
_images/73c1df937c5a1ea13dedeb73f4faa3dc8aa190207bd0b8e646d6fefc41fd4f32.png 
psi = Statevector(qc)
psi.draw("bloch")
_images/7c94e552a71bb312890ed43d6b09b5cb3a5a33501fb7a60b9d124e7b32f64289.png

Zゲート#

Zゲートはブロッホ球の\(z\)軸周りの\(\pi\)回転です。位相反転とも呼ばれます。
（重ね合わせ状態は確率振幅の他に、位相を持ちます。ここではブロッホ球の緯線の方向が反転するという理解で十分です）

Zゲートを代数的に表現すると下記のように表されます。

\(Z = \begin{pmatrix} 1 & 0 \\ 0 & -1 \\ \end{pmatrix}\)

qc = QuantumCircuit(1)
qc.h(0)
qc.z(0)
qc.draw(output='mpl')
_images/21c8d3ee6193cfe4a2f7d69124ba638f8e124a163dc7028bcc353018ae741867.png 
psi = Statevector(qc)
psi.draw("bloch")
_images/c0d7e469c2eccd80e4070549cbca343b449818d7aa6d4055de9fa5c48608412e.png

ここまでは単純な単一量子ゲートのXゲート、Hゲート、Zゲートを扱いました。
ここからは、複数の量子ビットを入出力に持つ、CXゲート、CZゲート、CCXゲートについて扱います

CXゲート(CNOTゲート)#

CXゲート（Control-Xゲート）は制御NOTゲート、CNOTとも呼ばれます。CXゲートは、２つの量子ビット(制御量子ビットとターゲット量子ビットと呼びます)を入出力に持ち、制御量子ビットが\(|1\rangle\)のときに、ターゲット量子ビットに対してビット反転(Xゲート)を行います。(Qiskitでは、番号の大きい量子ビットほど高い位のビット数に対応しています。つまり、右から順に番号付けされます。)

CXゲートを代数的に表現すると下記のように表されます。

\(CX = \begin{pmatrix} 1 & 0 & 0 & 0\\ 0 & 1 & 0 & 0\\ 0 & 0 & 0 & 1\\ 0 & 0 & 1 & 0\\ \end{pmatrix}\)

qc = QuantumCircuit(2)
qc.cx(0,1) # cx(control-bit, target-bit) 
qc.draw(output='mpl')
_images/ed75e1e8d9c12eec083f83433a28f15ae3d37888ad868bdde096bf75ea96ac46.png 
psi = Statevector(qc)
psi.draw("bloch")
_images/0e9170053443cacd67320da0ea0c4f0bb9052acab8d0f98d10e814b548a38601.png 
qc = QuantumCircuit(2)
qc.x(0)
qc.cx(0, 1)
qc.draw(output='mpl')
_images/59a6d9153b2d91ca46f06183d2ba17d9acf3923c3379f378792d7961d68315bc.png 
psi = Statevector(qc)
psi.draw("bloch")
_images/140f341102dcf65dee3c305f24cbe76ab41302b78cc268ff5c9ceef6874efd70.png

CZゲート#

CZゲートも、２つの量子ビット(制御量子ビットとターゲット量子ビットと呼びます)を入出力に持ち、制御量子ビットが\(|1\rangle\)のときに、ターゲット量子ビットに対して位相反転(Zゲート)を行います。

CZゲートを代数的に表現すると下記のように表されます。

\(CZ = \begin{pmatrix} 1 & 0 & 0 & 0\\ 0 & 1 & 0 & 0\\ 0 & 0 & 1 & 0\\ 0 & 0 & 0 & -1\\ \end{pmatrix}\)

qc = QuantumCircuit(2)
qc.h(1)
qc.cz(0, 1)
qc.draw(output='mpl')
_images/e374ffa3d7264ff775b778ad3210c4a5597e1c2296b670eb6af96cea52355d20.png 
psi = Statevector(qc)
psi.draw("bloch")
_images/a47686cfe59a114d1916a4cea5a326c906df2c5f69305372b180581dc6c4bf81.png 
qc = QuantumCircuit(2)
qc.x(0)
qc.h(1)
qc.cz(0, 1)
qc.draw(output='mpl')
_images/fc7ebac14ec254ce7b89141a2257cf15a639205741f66c1be007f67b07e77e1e.png 
psi = Statevector(qc)
psi.draw("bloch")
_images/041ba820643a381f9edeab85c2e490ed139519e1b6c451b3ebae58ef7084c7de.png

CZゲートはCXゲートとHゲートからも作ることができます。

qc = QuantumCircuit(2)

qc.h(1)
qc.cx(0, 1)
qc.h(1)
qc.draw(output='mpl')
_images/5da9578f8ee02e6199dc46207063d5a09dd4ea9026c09e80b6e8f7f3a1f9b570.png

CCXゲート(Toffoliゲート)#

CCXゲートは、3つの量子ビット(2つの制御量子ビットと1つのターゲット量子ビット)を入出力に持ち、制御量子ビットが2つとも\(|1\rangle\) のときに、ターゲット量子ビットに対してビット反転(Xゲート)を行います。(Qiskitでは、右から順に番号付けされることに注意してください。)

Toffoliゲートを代数的に表現すると下記のように表されます。

\(CCX = \begin{pmatrix} 1 & 0 & 0 & 0 & 0 & 0 & 0 & 0\\ 0 & 1 & 0 & 0 & 0 & 0 & 0 & 0\\ 0 & 0 & 1 & 0 & 0 & 0 & 0 & 0\\ 0 & 0 & 0 & 1 & 0 & 0 & 0 & 0\\ 0 & 0 & 0 & 0 & 1 & 0 & 0 & 0\\ 0 & 0 & 0 & 0 & 0 & 1 & 0 & 0\\ 0 & 0 & 0 & 0 & 0 & 0 & 0 & 1\\ 0 & 0 & 0 & 0 & 0 & 0 & 1 & 0\\ \end{pmatrix}\)

qc = QuantumCircuit(3)
qc.ccx(0, 1, 2)
qc.draw(output='mpl')
_images/b95ba7d58468c0a4b4abb7545f59331bffeea43c7de828eea33d14eeaa2dbf40.png 
psi = Statevector(qc)
psi.draw("bloch")
_images/aa8809c472a7132e1bfb27d7722570e4fb28b99c23327fe616ae71091e28a4d7.png 
qc = QuantumCircuit(3)
qc.x(0)
qc.ccx(0, 1, 2)
qc.draw(output='mpl')
_images/89d993960f82437bf1b8bb19670a05e094d60c8c8978cfaaa8d3bde89e2db6fe.png 
psi = Statevector(qc)
psi.draw("bloch")
_images/9f5db614b2d80ee75857642659bac79cbb26805cc22822765d9204c6a21c824d.png 
qc = QuantumCircuit(3)
qc.x(0)
qc.x(1)
qc.ccx(0, 1, 2)
qc.draw(output='mpl')
_images/c2c855dfbbf3ad11c41be070fc207d7fa5cbbcc5abb568b2f42153d71c8f268e.png 
psi = Statevector(qc)
psi.draw("bloch")
_images/29ce7742cd8f04f7219a4ac5151b0937cfef4dce16a36fec00e25d9f5b6db123.png

古典の論理ゲートを量子ゲートで再現する#

ここまで、基本的な量子ゲートを学びました。 次は、古典の論理ゲート

  1. NOTゲート

  2. ANDゲート

  3. NANDゲート

  4. ORゲート

  5. XORゲート

  6. NORゲート

を量子ゲートで作成してみましょう。

この章では、真理値表と量子回路による表現を示します。なお、量子レジスタをq、古典レジスタをcとし、測定結果を作成する論理ゲートの出力とします。

NOTゲート#

先述の通り、XゲートをNOTゲートとみなすことができます。 真理値表は以下のようになります。

入力

出力

0

1

1

0

 
qc = QuantumCircuit(1, 1)
qc.x(0)
qc.measure(0, 0)    # 測定した結果を古典ビットにマップする
qc.draw(output='mpl')
_images/4ad927104e239c6a0621be8605e9f63ddac939af4e184ab4c86f7e2523cdd20d.png

ANDゲート#

ANDゲートの真理値表は以下のようなものです。

入力A

入力B

出力

0

0

0

0

1

0

1

0

0

1

1

1

CCXゲートを用いると、制御量子ビット2つに対するANDゲートの結果をターゲット量子ビットに得られます。

ex.

q0, q1を制御量子ビットとした場合、q0とq1に対するAND演算の結果がq2に格納されます。

qc = QuantumCircuit(3, 1)
qc.ccx(0, 1, 2)
qc.measure(2, 0)    # 測定した結果を古典ビットにマップする
qc.draw(output='mpl')
_images/b5d3a5dd2a62c5a953709b73a57b28e07b5723533d561e1abe0653fa2fc97841.png

NANDゲート#

NANDゲートはANDゲートにNOTゲートを適用したものと捉えることができます。 よって、先ほどのANDゲートのq2ビットにNOTゲートを作用させます。

入力A

入力B

出力

0

0

1

0

1

1

1

0

1

1

1

0

 
qc = QuantumCircuit(3, 1)
qc.ccx(0, 1, 2)
qc.x(2)
qc.measure(2, 0)
qc.draw(output='mpl')
_images/cd1cb51a5da12872330a59cf0710f7226d2da29d5f8688f1d861d377b45ab6d1.png

ORゲート#

ORゲートは2入力の一方が1であれば1出力が1となる、下記の論理表のような入出力を持つ論理ゲートです。
量子回路を用いる場合、ANDゲートと同じようにq0ビット、q1ビットを2入力、q2ビットを1出力とし、CXゲートとCCXゲートを用いることでORゲートを再現することができます。

入力A

入力B

出力

0

0

0

0

1

1

1

0

1

1

1

1

 
qc = QuantumCircuit(3, 1)
qc.cx(1, 2)
qc.cx(0, 2)
qc.ccx(0, 1, 2)
qc.measure(2, 0)
qc.draw(output='mpl')
_images/e109ec40a43aeed54a8c18b59e150e1399725369d9c8159ce67168245d9d891c.png

XORゲート#

XORゲートは2入力が一致しない場合に1を出力する論理ゲートです。
量子回路を用いる場合、CXゲートを用いることでXORゲートを再現できます。

入力A

入力B

出力

0

0

0

0

1

1

1

0

1

1

1

0

 
qc = QuantumCircuit(3, 1)
qc.cx(1, 2)
qc.cx(0, 2)
qc.measure(2, 0)
qc.draw(output='mpl')
_images/e9a86d82c9368392bc1c490d9a13f579c2593695712c2b5317ce18cb2ad7eeec.png

NORゲート#

NORゲートはORゲートの出力にNOTゲートを作用させることで実現できます。

入力A

入力B

出力

0

0

1

0

1

0

1

0

0

1

1

0

 
qc = QuantumCircuit(3, 1)
qc.cx(1, 2)
qc.cx(0, 2)
qc.ccx(0, 1, 2)
qc.x(2)
qc.measure(2, 0)
qc.draw(output='mpl')
_images/fa4baf6f501834d2f79e31f84980c928195399f490f73971d818ae20b4516db2.png

ここまでの章で、

  1. 量子回路の基礎

  2. 量子回路を用いた古典論理ゲートの再現

を学んできました。これで量子回路を用いた加算器を作ることができます。

加算器を量子ゲートで再現する#

加算器は足し算を行う論理回路です。 今回は最もシンプルな加算器である半加算器と全加算器を用いた加算器に関して考えます。

from qiskit import QuantumRegister, ClassicalRegister, QuantumCircuit
from qiskit.quantum_info import Statevector
from qiskit.primitives import StatevectorSampler
from qiskit.circuit.equivalence_library import SessionEquivalenceLibrary as sel
from qiskit.transpiler.passes import BasisTranslator

半加算器#

半加算器は2つのビット列の同じ桁の値同士を加算し、その桁の加算後の値と上位桁への繰り上がりの有無を表す「桁上げ出力、キャリー(Carry out)」の2つを出力するような論理回路です。桁上げ出力は、繰り上がりがあれば1、なければ0となります。
この半加算器を用いて、後述の全加算器を作成します。

半加算器は以下の様な2入力2出力の真理値表の論理回路で表すことができます。 2入力A, Bはそれぞれ2つのビット列の同じ桁同士、出力Sはその桁の出力、桁上げ出力Cは繰り上がりの値です。

入力A

入力B

出力S

桁上げ出力C

0

0

0

0

0

1

1

0

1

0

1

0

1

1

0

1

この真理値表を見ると、桁上げ出力Cは入力Aと入力Bに対してANDを適用したものであること、出力Sは入力Aと入力Bに対してXORを適用したものであることがわかります。 ANDとXORに関してはすでに作成済みなので、以下のように組み合わせて半加算器の量子回路が作成してみましょう。

qc = QuantumCircuit(4, 2)

#XOR
qc.cx(1, 2)
qc.cx(0, 2)
qc.barrier()

#AND
qc.ccx(0, 1, 3)
qc.barrier()

#Sum
qc.measure(2, 0)
#Carry out
qc.measure(3, 1)
qc.draw(output='mpl')
_images/8e81c93ae7677b7fdb8c3f70a42d90804a78c6ff1555dff203a6cb0ffa8bf4e4.png 
def get_counts(qc: QuantumCircuit):
    sampler = StatevectorSampler()
    job = sampler.run([qc])
    result = job.result()
    count = result[0].data.c.get_counts()
    return count

get_counts(qc)

{'00': 1024}

Unrollerを用いた量子コストの導出#

全加算器を作成する前に、量子回路の性能についてここで学んでおきましょう。 プログラム(量子回路)を評価する手法はいくつか存在します。 代表的なものとしては、

  1. 量子ビット数

  2. 深さ

  3. 実行速度

  4. 命令数

があります。
これらはどれも量子計算の結果やスループットなどに影響する重要な尺度ですが、今回のQuantum Challengeでは特に4の命令数を指標として、以下のようにプログラムを評価します。また、この指標を今回のQuantum Challengeではコストと呼称します。

コスト \(=\) 単一量子ビットゲートの数 \(+\) CXゲートの数 \(\times 10\)

なぜこのように単一量子ビットゲートとCXゲートによってコストを計算するのかというと、任意の量子回路は単一量子ビットゲート(1量子ビットに対する命令)と2量子ビットゲートに対する命令に分解できるためです。
（※現在のノイズの多い中規模量子デバイス（NISQ）では、CXゲートのエラー率は一般に単一量子ビットゲートの10倍です。よって、コストでは、CXゲートの重みづけを単一量子ビットゲートの10倍としています。）

また、unrollerと呼ばれるプログラムを用いることで、皆さんのお手元でもこのコストを導出することができます。
例えば、以下のような量子回路があったとします。

qc = QuantumCircuit(4, 1)
qc.ccx(0, 1, 2)
qc.cx(3, 1)
qc.h(3)
qc.ccx(3, 2, 1)
qc.measure(3, 0)
qc.draw(output='mpl')
_images/c7c1d39b39b5859ab406e2275575d2cc376633d5d2dcc3c9281cb5e2e2adc20e.png 
# qiskitのメソッドcount_ops()でゲートの数をカウントすることができます
qc.count_ops()

OrderedDict([('ccx', 2), ('cx', 1), ('h', 1), ('measure', 1)])

この量子回路にはHゲート、CXゲート、CCXゲートが入っています。qiskit.transpilerを使ってPassManagerをインポートすることで、以下のようにUnrollerによって指定されたゲートに分解できます。この場合では、u3ゲートとcxゲートに分解します。

new_circuit = BasisTranslator(sel, ['u3', 'cx'])(qc)
new_circuit.draw(output='mpl')
_images/e11441e767d4978791d5d5f233b415c2eabe940cf8d9d5644afc172d4700db41.png 
new_circuit.count_ops()

OrderedDict([('u3', 19), ('cx', 13), ('measure', 1)])

よって、この回路のコストは\(19+13\times10=149\)ということになります。 このように、以下の手順によって量子回路の性能を評価してみましょう。

  1. 任意の量子回路をUnrollerで単一量子ビットゲートとCXゲートに分割する

  2. 上述のコスト計算方法によってコストを計算する

※単一量子ビットゲートやCXゲート以外のゲートが、Unrollerによってどのように分解されるかは簡単に確認できるので、興味がある人は自分で調べてみましょう。以下ではサンプルとして、CCXゲートをu3ゲートとCXゲートに分解しています。

q = QuantumRegister(3, 'q0')
c = ClassicalRegister(1, 'c0')
qc = QuantumCircuit(q, c)
qc.ccx(q[0], q[1], q[2])
qc.draw(output='mpl')
_images/f0b8bcea2e19e3e3d181e8fda33049db309f3d27019cb75eb9003b2c26e7e138.png 
new_circuit = BasisTranslator(sel, ['u3', 'cx'])(qc)
new_circuit.draw(output='mpl')
_images/e58ca32a0d4c4b91b17274955ce4cbb3d61b77537ad38a198964dce590d54e64.png 
new_circuit.count_ops()

OrderedDict([('u3', 9), ('cx', 6)])

上記の回路のコストは\(9+6\times10=69\)ということになります。

全加算器#

Exercise: 全加算器の量子回路の構築

さて、いよいよ最終演習です。
ここでは全加算器を量子回路で作成します。
全加算器は、下の位からの桁上げを含む加算器です。前章の半加算器を用いて作成します。
最終的に全加算器を量子回路で表現して、

\(A=1\), \(B=0\), \(X=1\)

の時の結果
すなわち \(\ket{11} + \ket{01}\) の2桁目を計算したときの結果を出力してみましょう。
結果が、出力0、桁上げ出力1となれば正解です。

真理値表は以下のようになります。

入力A

入力B

桁上げ入力X

出力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

なお、以下の条件とするように全加算器を作成してください

  • 量子レジスタを\(q\), 古典レジスタ\(c\)とする

  • 入力A, B, 桁上げ入力Xをそれぞれ\(q[0]\), \(q[1]\), \(q[2]\)に与えられるようにする

  • 測定結果の\(c[0]\)に出力S、\(c[1]\)に桁上げ出力Cが出力されるようにする

Hide code cell content 
# 各レジスター、量子回路を宣言
qc = QuantumCircuit(8, 2)

# 入力データを入れます
qc.x(0)
qc.x(2)

# 量子回路を作成
def OR(a,b,c):
  qc.cx(b, c)
  qc.cx(a, c)
  qc.ccx(a, b, c)

def hadder(a,b,s,c):
  #XOR
  qc.cx(b, s)
  qc.cx(a, s)
  #AND
  qc.ccx(a, b, c)

hadder(0,1,4,3)
qc.barrier()
hadder(4,2,6,5)
qc.barrier()
OR(3,5,7)
qc.barrier()

#観測
qc.measure(6, 0)
qc.measure(7, 1)

qc.draw(output='mpl')
_images/92b98eaeb12474afb22076646f465b876a2176aa4a5f25a510a18a953c3bbd1c.png 
get_counts(qc)

{'10': 1024}

Unrollerでコストも計算してください

new_circuit = BasisTranslator(sel, ['u3', 'cx'])(qc)
new_circuit.draw(output='mpl')
_images/233a393e349a23c1f4e50e9ab9c1ae8fe56c6b70e1937c2b458df39435c81163.png 
new_circuit.count_ops()

OrderedDict([('u3', 29), ('cx', 24), ('barrier', 3), ('measure', 2)])

Unrollerを用いて計算したこの回路のコストは、29 + 24 × 10 = 279 となります。

目次