概要
この記事では量子コンピュータの概要とPythonを使ったシミュレーションによる実装例を紹介します。
量子アニーリングと量子ゲートの2種類のコンピュータについて書いています。
量子コンピュータを使った演算に関係ない部分の説明はできるだけ省きました。
量子コンピュータを知らない人には見慣れない数式や物理用語が出てきて怖そうなイメージがありますよね。
単純なアルゴリズムで量子コンピュータのプログラムを実装するだけなら実はそれほど難しくありません。
自動車のエンジンの仕組みを知らなくても車を運転することはできます。
すごく単純な例なので実用レベルではありませんが、量子コンピュータのプログラム実装のイメージを掴める手助けになると信じています。
量子コンピュータの種類
量子コンピュータは計算方法の違いで以下の2種類に分類できます。
特化型(量子アニーリングなど)
量子特化型コンピュータは特定の問題を解く専用機です。
例えば量子アニーリングマシンは量子アニーリングを使って「組み合わせ最適化問題」のような問題を解くための専用機です。
汎用型(量子ゲートなど)
量子汎用型コンピュータはあらゆる量子計算を解けるコンピュータです。
例えば量子ゲートマシンは量子回路を使って汎用的に問題を解けるコンピュータです。
量子アニーリングで問題を解く
量子アニーリングで問題を解くのは大まかに以下の手順を実行します。
- 問題をモデル化してコスト関数を作る
- コスト関数からQUBO(行列)を作る
- QUBOを量子アニーリングで計算する
- 測定して結果を取り出す
量子アニーリングで自然数分割問題を解く
量子アニーリングを使って具体的な問題を解いてみましょう。
自然数分割問題
ここでは自然数分割問題を解いてみます。
自然数分割問題はある自然数の集合を2つの集合の値の和が同じになるように分割する問題です。
例えば ${ \left[1,2,5,6\right] }$ を２つに分けてみましょう。
${ 1+2+5+6 = 14 }$ なので合計が半分の7ずつになるように分けられます。
答えは簡単で ${ \left[1,6\right] }$ と ${ \left[2,5\right] }$ に分けられます。
モデル化する
アニーリングのモデル化とは量子ビット ${ q_i=0,1 }$ の多項式だけで問題を表現することです。
具体的には量子ビットの1次または2次の多項式で書きます。
アニーリングにおける量子ビットは測定すると0か1の値に収束するような変数です。
この量子ビットの多項式をコスト関数といいます。
コスト関数を最小化する問題にすることがアニーリングのモデル化です。
自然数分割問題のモデル化
自然数分割問題をモデル化してみましょう。
集合Aの自然数の値 ${ a_i }$ の合計値と集合Bの自然数の値 ${ b_j }$ の合計値が同じであることは式で書くと次のようになります。
a_0 + ... + a_m = b_0 + ... + b_n \\\
\sum_i a_i = \sum_j b_j \\\
\sum_i a_i - \sum_j b_j = 0
i番目の自然数がどちらの集合に所属するかを量子ビット${ q_i }$で表すことにします。
例えば、集合Aに所属するときを「1」、集合Bに所属するときを「0」と決めます。
このとき${ 2q_i-1 }$の値は、集合Aでは「1」、集合Bでは「-1」になります。
自然数の値を${ n_i }$とすると、
${ a_i=n_i(2q_i-1), -b_j=n_j(2q_j-1) }$ と書けます。
\sum_i a_i - \sum_j b_j = \sum_i n_i(2q_i-1)
AとBは任意なので正負を考えないために全体を２乗します。
この式をコスト関数とします。
コスト関数Eを最小(=0)にするのがアニーリングの解法です。
E = \left(\sum_i n_i(2q_i-1)\right)^2
自然数分割問題のQUBOを作る
QUBO(Quadratic Unconstrained Binary Optimization)は量子ビットの2次までの多項式です。
以下のように行列で表現できます。
QUBO = \sum_{i,j} k_{ij}q_iq_j = \begin{pmatrix} q_1 ... q_n \end{pmatrix} \begin{pmatrix} k_{11} ...k_{1n} \\ ... \\ k_{n1}...k_{nn} \end{pmatrix} \begin{pmatrix} q_1 \\ ... \\ q_n \end{pmatrix}
2つの条件を使ってQUBOを簡素化します。
- 単項化
${ q_i = 0,1 }$ なので ${ q_i^2 = 0,1 }$ です。
つまり ${ q_i^2 = q_i }$ となります。 - 係数の一元化
${ q_iq_j = q_jq_i }$ なので ${ k_{ij}q_iq_j + k_{ji}q_jq_i = (k_{ij}+k_{ji})q_iq_j }$ と書けます。${ k_{ji}=0 }$ とすれば係数を1つにまとめられます。
この2つからQUBOは上三角行列になります。
QUBO = \sum_{i} k_{ii}q_i + \sum_{i<j} k_{ij}q_iq_j \\\
= \begin{pmatrix} q_1...q_n \end{pmatrix} \begin{pmatrix} k_{11}...k_{1n} \\ ... \\ 0...k_{nn} \end{pmatrix} \begin{pmatrix} q_1 \\ ... \\ q_n \end{pmatrix}
通常は量子ビットの部分を除いた係数部分の行列だけを入力します。
自然数分割問題のシミュレーション
自然数分割問題をPythonで解いてみましょう。
PyQUBOというライブラリを使います。
# python 3.7
# pyqubo 0.4.0
import pyqubo
def solve(numbers):
# numberの個数分だけ量子ビットを定義する
qubits = pyqubo.Array.create('x', len(numbers), vartype='BINARY')
# コスト関数
H = sum([(2*q - 1)*n for n, q in zip(numbers, qubits)])**2
model = H.compile()
# QUBOの生成
qubo, offset = model.to_qubo()
return pyqubo.solve_qubo(qubo)
def check_solution(solution):
a = [n for i,n in enumerate(numbers) if solution['x[{}]'.format(i)] == 0]
b = [n for i,n in enumerate(numbers) if solution['x[{}]'.format(i)] == 1]
sa = sum(a)
sb = sum(b)
if sa == sb:
return 'Correct answer: {} = {}'.format(sa, sb)
return 'Wrong answer: {} != {}'.format(sa, sb)
numbers = [1,2,5,6]
solution = solve(numbers)
print(solution)
print(check_solution(solution))
実行結果です。
${ \left[1,2,5,6\right] }$ が ${ \left[1,6\right] }$ と ${ \left[2,5\right] }$ に分けられていますね。
([1, 6], [2, 5])
Correct answer: 7 = 7
量子ゲートで問題を解く
量子ゲートで問題を解くには以下の手順を実行します。
- 問題をモデル化する
- モデルからゲート(行列)を構築する
- ゲートを演算する
- 測定して結果を取り出す
量子ゲートで足し算をする
量子ゲートで1ビット同士の足し算をします。
論理回路で半加算器(Half Adder)と呼ばれる回路を量子回路で実現します。
半加算器を論理回路で書くと次のようにかけます。
s は a と b の XOR(排他的論理和) で1桁目の数を表します。
c は a と b の AND(論理積) で2桁目の数を表します。
量子ビット
量子1ビットで100%の確率で「0」が観測される状態と100%の確率で「1」が観測される状態をそれぞれベクトルで表現します。
\lvert0\rangle = \begin{pmatrix} 1 \\ 0 \end{pmatrix}\\\
\lvert1\rangle = \begin{pmatrix} 0 \\ 1 \end{pmatrix}
重ね合わせ状態にある量子1ビットは一般的に次のように表せます。
\lvert\psi\rangle = \begin{pmatrix} \alpha \\ \beta \end{pmatrix} = \alpha \begin{pmatrix} 1 \\ 0 \end{pmatrix} + \beta \begin{pmatrix} 0 \\ 1 \end{pmatrix} = \alpha\lvert0\rangle + \beta\lvert1\rangle
量子2ビットは以下のように書けます。
\lvert00\rangle = \begin{pmatrix} 1 \\ 0 \\ 0 \\ 0 \end{pmatrix} \\\
\lvert01\rangle = \begin{pmatrix} 0 \\ 1 \\ 0 \\ 0 \end{pmatrix} \\\
\lvert10\rangle = \begin{pmatrix} 0 \\ 0 \\ 1 \\ 0 \end{pmatrix} \\\
\lvert11\rangle = \begin{pmatrix} 0 \\ 0 \\ 0 \\ 1 \end{pmatrix}
量子NOTゲート
Xゲートは量子NOTゲートとも呼ばれます。ビットの値を反転させます。
Xゲートは行列で以下のように書けます。
X = \begin{pmatrix} 0 & 1 \\ 1 & 0 \end{pmatrix}
1ビットの値にXゲートを適用するとビットの値が反転していることがわかります。
X\lvert0\rangle = \begin{pmatrix} 0 & 1 \\ 1 & 0 \end{pmatrix} \begin{pmatrix} 1 \\ 0 \end{pmatrix} = \begin{pmatrix} 0 \\ 1 \end{pmatrix} = \lvert1\rangle \\\
X\lvert1\rangle = \begin{pmatrix} 0 & 1 \\ 1 & 0 \end{pmatrix} \begin{pmatrix} 0 \\ 1 \end{pmatrix} = \begin{pmatrix} 1 \\ 0 \end{pmatrix} = \lvert0\rangle
量子XORゲート
CXゲート(またはCNOTゲート)は量子XORゲートとも呼ばれます。
2ビットの量子ゲートでコントロールビットが「1」のときだけターゲットビットの値を反転させます。
CXゲートは行列で以下のように書けます。
CX = \begin{pmatrix} 1 & 0 & 0 & 0 \\ 0 & 1 & 0 & 0 \\ 0 & 0 & 0 & 1 \\ 0 & 0 & 1 & 0 \end{pmatrix}
2ビットの値にCXゲートを適用すると1ビット目の値だけが反転していることがわかります。
CX\lvert00\rangle = \begin{pmatrix} 1 & 0 & 0 & 0 \\ 0 & 1 & 0 & 0 \\ 0 & 0 & 0 & 1 \\ 0 & 0 & 1 & 0 \end{pmatrix}\begin{pmatrix} 1 \\ 0 \\ 0 \\ 0 \end{pmatrix} = \begin{pmatrix} 1 \\ 0 \\ 0 \\ 0 \end{pmatrix} = \lvert00\rangle \\\
CX\lvert01\rangle = \begin{pmatrix} 1 & 0 & 0 & 0 \\ 0 & 1 & 0 & 0 \\ 0 & 0 & 0 & 1 \\ 0 & 0 & 1 & 0 \end{pmatrix}\begin{pmatrix} 0 \\ 1 \\ 0 \\ 0 \end{pmatrix} = \begin{pmatrix} 0 \\ 1 \\ 0 \\ 0 \end{pmatrix} = \lvert01\rangle \\\
CX\lvert10\rangle = \begin{pmatrix} 1 & 0 & 0 & 0 \\ 0 & 1 & 0 & 0 \\ 0 & 0 & 0 & 1 \\ 0 & 0 & 1 & 0 \end{pmatrix}\begin{pmatrix} 0 \\ 0 \\ 1 \\ 0 \end{pmatrix} = \begin{pmatrix} 0 \\ 0 \\ 0 \\ 1 \end{pmatrix} = \lvert11\rangle \\\
CX\lvert11\rangle = \begin{pmatrix} 1 & 0 & 0 & 0 \\ 0 & 1 & 0 & 0 \\ 0 & 0 & 0 & 1 \\ 0 & 0 & 1 & 0 \end{pmatrix}\begin{pmatrix} 0 \\ 0 \\ 0 \\ 1 \end{pmatrix} = \begin{pmatrix} 0 \\ 0 \\ 1 \\ 0 \end{pmatrix} = \lvert10\rangle
量子ANDゲート
CCXゲート(またはトフォリゲート)は量子ANDゲートと言えます。
3ビットの量子ゲートで2つのコントロールビットが「1」のときだけターゲットビットの値を反転させます。
CCXゲートは行列で以下のように書けます。
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}
(各ビットに対するゲート演算結果の行列表示は長いので割愛します。)
CCX\lvert000\rangle = \lvert000\rangle,\quad CCX\lvert001\rangle = \lvert001\rangle \\\
CCX\lvert010\rangle = \lvert010\rangle,\quad CCX\lvert011\rangle = \lvert011\rangle \\\
CCX\lvert100\rangle = \lvert100\rangle,\quad CCX\lvert101\rangle = \lvert101\rangle \\\
CCX\lvert110\rangle = \lvert111\rangle,\quad CCX\lvert111\rangle = \lvert110\rangle
半加算器のゲート
半加算器を論理回路で書くと次のようにかけます。
これはCCXゲートとCXゲートをそれぞれ演算したものです。
CX(0,1)CCX\lvert000\rangle = CX(0,1)\lvert000\rangle = \lvert000\rangle \\\
CX(0,1)CCX\lvert010\rangle = CX(0,1)\lvert010\rangle = \lvert010\rangle \\\
CX(0,1)CCX\lvert100\rangle = CX(0,1)\lvert100\rangle = \lvert110\rangle \\\
CX(0,1)CCX\lvert110\rangle = CX(0,1)\lvert111\rangle = \lvert101\rangle
- 入力: ${ \lvert a b 0 \rangle }$
- 出力: ${ \lvert a s c \rangle }$
半加算器の論理表と同じになっていることがわかります。
| a | b | c | s |
|---|---|---|---|
| 0 | 0 | 0 | 0 |
| 0 | 1 | 0 | 1 |
| 1 | 0 | 0 | 1 |
| 1 | 1 | 1 | 0 |
半加算器のシミュレーション
半加算器をPythonのシミュレーションで実現してみましょう。
Qiskitというライブラリを使います。
量子ビットにはデフォルトで「0」が入ります。
今回は足し算を実現するために入力値に合わせてXゲートを半加算器の前において「1」 に変化させています。
## python 3.7
## qiskit 0.12
from qiskit import QuantumCircuit, QuantumRegister, ClassicalRegister
from qiskit import execute, Aer
## HalfAdder
def classical_half_adder(a, b):
# AND
c = a & b
# XOR
s = a ^ b
print('{0} + {1} = {2}{3}'.format(a,b,c,s))
def get_result(qc, shots=1):
simulator = Aer.get_backend('qasm_simulator')
return execute(qc, simulator, shots=shots).result().get_counts(qc)
def quantum_half_adder(a, b):
# 量子3ビットを定義する
q = QuantumRegister(3)
# 古典3ビットを定義する
c = ClassicalRegister(3)
# 量子回路を定義する
qc = QuantumCircuit(q,c)
if a == 1:
# 0ビット目を「1」にする
qc.x(0)
if b == 1:
# 1ビット目を「1」にする
qc.x(1)
# CCXゲート
qc.ccx(0,1,2)
# CXゲート
qc.cx(0,1)
# 量子ビットを測定する
qc.measure(q,c)
r = list(get_result(qc).keys())[0]
print('{0} + {1} = {2}{3}'.format(a,b,r[0],r[1]))
def main_half_adder():
print('Classical Half Adder')
classical_half_adder(0, 0)
classical_half_adder(0, 1)
classical_half_adder(1, 0)
classical_half_adder(1, 1)
print('Quantum Half Adder')
quantum_half_adder(0, 0)
quantum_half_adder(0, 1)
quantum_half_adder(1, 0)
quantum_half_adder(1, 1)
main_half_adder()
実行結果を表示します。
Classical Half Adder
0 + 0 = 00
0 + 1 = 01
1 + 0 = 01
1 + 1 = 10
Quantum Half Adder
0 + 0 = 00
0 + 1 = 01
1 + 0 = 01
1 + 1 = 10
古典論理回路による結果と量子回路による結果を比較しています。
2つの結果が同じになっていることがわかります。
まとめ
- 量子コンピュータ(アニーリングとゲート)の演算は行列計算
- 量子ビットはベクトルで表現できる
- 量子アニーリングはQUBO(行列)を作って問題を解く
- 量子ゲートはゲート(行列)を組み合わせて問題を解く
補足
- 量子アニーリングで問題を解くにはQUBOを作った後にグラフ構築などの作業が必要な環境もあります(例えばD-Wave)。
- 量子ゲートで半加算器を実装するのは古典コンピュータでやるべきことなので現実的に意味はありません。量子ゲート向けのアルゴリズムは概念を理解するのがちょっと難しいので単純な例として使っています。