Introduction

データポイントの数や次元数の大きいデータを扱うとき、機械学習の学習アルゴリズムの時間計算量を気にしたことがあるかもしれません。量子アルゴリズムには素因数分解や未整序データベース探索といった特定の課題で、時間計算量のオーダーを下げることに成功した例があり、学習アルゴリズムに対しても同様のことができないかというのは興味深い話です。

このノートでは、そのような量子機械学習と呼ばれるトピックから、特にk-means法の量子アルゴリズムを紹介し、その構成要素であるGrover's algorithmとswap testのうち、swap testのqiskitによる実装例を掲げます。

なお、このノートは量子コンピュータ Advent Calendar 2018, 21日目の記事になります。作成者の@gyu-donさんに感謝申し上げます。また頭痛による体調不良のため投稿が遅れたことをお詫び申し上げます。

量子k-means法のアルゴリズム

量子k-means法は次のようなアルゴリズムで計算されます。基本は古典的なk-means法と変わりません。

1. k個のクラスター中心を乱数で生成する。
2. 以下を収束するまで繰り返す。
（a）各データポイントを最も近いクラスター中心に対応するクラスターに割当。
（b）新しいクラスター中心を計算する。

ここで量子アルゴリズムを用いるのは、2（a）のみです。各データポイントと各クラスター中心との距離を求めるoracleを以下で説明するswap testとよばれる量子アルゴリズムで実装します。また、求めた距離を参考に各データポイントに最も近いクラスター中心をGrover's algorithmによって探索します。

1のクラスター中心の乱数生成や2（b）におけるクラスター中心のための平均値の計算は古典的なアルゴリズムを用います。

swap test

swap testとは本来、2つの量子状態|a>, |b>の内積<a|b>の大きさ||<a|b>||²を計算するためのアルゴリズムです。詳細を見てみましょう。

ここで、第1レジスターと第2レジスターでHadamard gateとU3 gateがかかっているのは、初期状態|0>から所望の状態|a>, |b>を構成するためであることには注意しておきます。要するに、swap testで本質的なのは第0レジスターのHadamard gateとcontrolled swap gateのほうです。

以下では、このcircuitにおける観測によって、状態の内積<a|b>の大きさ||<a|b>||²が計算で来ていることを確認します。

qiskitによるswap testの実装

今回は、それぞれの状態を|a> = |0>, |b> = -|1>として内積<a|b>=0を計算できるかやってみましょう。まずは必要なmoduleをimportします。

# 必要なモジュールのインポート
from qiskit import QuantumCircuit, QuantumRegister, ClassicalRegister, execute, Aer
from qiskit.tools.visualization import matplotlib_circuit_drawer as circuit_drawer
from qiskit.tools.visualization import plot_histogram
from IPython.display import Image, display_png

次にswap testのquantum circuitを実装します。

# swap testの実装
def build_swap_test(theta_1, theta_2):    # theta_iで|a>, |b>の量子状態を作る。
    q = QuantumRegister(3)
    c = ClassicalRegister(1)
    qc = QuantumCircuit(q, c)
    qc.h(q[0])
    qc.h(q[1])
    qc.h(q[2])
    qc.u3(theta_1, pi, pi, q[1])
    qc.u3(theta_2, pi, pi, q[2])
    qc.cswap(q[0], q[1], q[2])
    qc.h(q[0])
    qc.measure(q[0], c[0])
    return qc

内積を計算したい状態は|a> = |0>, |b> = -|1>でしたので、U3 gateの定義からtheta_1 = π/2, theta_2 = -π/2を引数に渡してインスタンスを建てればよいことが分かります。

# インスタンスを建てる。
from math import pi
swap_test = build_swap_test(theta_1 = pi/2, theta_2 = -pi/2)

折角なので、swap testのcircuitをみてみましょう。

# 実装したサーキットの可視化
circuit_drawer(swap_test, filename = "swap_test.png")
display_png(Image("swap_test.png"))

次にcircuitをコンパイルして、計算を実行しましょう。

# サーキットのコンパイルおよび計算の実行
job_sim = execute(swap_test, Aer.get_backend("qasm_simulator"))
res = job_sim.result()
print("シミュレーションの実行:", res)
print("結果:", res.get_counts(swap_test))

恐らく、ほぼ同程度だけ状態|0>と|1>が観測されたのではないでしょうか。計算結果を棒グラフでも可視化して確認しておきましょう。

# 計算結果の可視化
plot_histogram(res.get_counts(swap_test))

状態|0>の観測確率P[obs = |0>]は1/2+1/2||<a|b>||²に等しいことを前節で示しました。すなわち、1/2+1/2||<a|b>||² = 1/2が得られたことになりますから、<a|b> = 0を量子計算で確認できたことになります。

swap testを用いた距離計算

実は余弦定理に注意すると、swap testを用いることで2点間の距離を求めることが出来ることを示せます。

時間計算量の視点から

今回、量子機械学習を紹介するモチベーションとして時間計算量を挙げましたが、古典アルゴリズムを用いた2点間の計算は次元Nに対してO(N)：線形にオーダーがかかるのに対し、今回紹介した量子アルゴリズムはO(logN)：対数オーダーです。

おわりに

量子機械学習では他にもサポートベクトルマシンや主成分分析、ニューラルネットワークなどさまざまな手法で盛んに研究が行われてきました。この記事をきっかけに、様々なみなさんに量子機械学習に興味を持っていただければ、私にとってはこの上ない幸せです。

風邪をひいてしまい、書き上げることを第1目標にしてしまったので、ところどころ間違いがあったり文章が分かりづらかったりしていると思います。体調が直ったら一度見直したいです、ごめんなさい。最後に、量子k-means法そのものに近い簡単な実装例を書きたかったというのが心残りでした。時間があるときに加筆修正していければと思います。

参考文献

[ABS] E. Aimeur, G. Brassard and S. Gambs, Machine learning in a quantum world, In Advances in Artificial Intelligence, 431-442, 2016.
[LMR] S. Lloyd, M. Mohseni and P. Rebentrost, Quantum algorithms for supervised and unsupervised machine learning,  arXiv:1307.0411 [quant-ph], 2013.
[SSP] M. Schuld, I. Sinayskiy, F. Petruccione, An Introduction to quantum machine learning, Contemporary Physics, 56:2, 172-185, 2015.