@yuichirominato 2018.11.11更新 74views

量子ゲートで組合せ最適化問題を解くQAOAの実装

Blueqat QUBO イジング 量子ゲート 量子コンピュータ

はじめに

量子ゲートモデルの量子コンピュータは汎用モデルといわれていて、現在の私たちの計算機で行うことがそのままできます。量子効果によって計算速度の上がる問題、上がらない問題がありますが、全ての計算が上がらなくてもどうしても活用しないといけないことはたくさんあります。

ここでは、普通の組合せ最適化問題を、普通は量子イジングマシンや量子アニーリングを使うところ、古典計算機を使わないで済むように量子ゲートモデルで解いてみます。

量子ゲートモデルで組合せ最適化問題を解く

量子ゲートモデルは汎用型計算機です。私たちの使用しているマシンのように様々な計算を演算子と呼ばれる計算要素を使って計算できます。私たちの使っている計算機とは異なるかたちのゲート演算子と呼ばれる操作によって計算ができます。

汎用モデルですので組合せ最適化を解く方法は1つではなく、アルゴリズムによってたくさんあります。こちらのペーパーでは体系的にまとめてあります。

Combinatorial Optimization on Gate Model Quantum Computers: A Survey
Ehsan Zahedinejad · Arman Zaribafiyan
https://arxiv.org/abs/1708.05294

難しくない

量子ゲートの計算は難しく聞こえますが、そうではありません。現在では技術がどんどん進んでソフトウェアやミドルウェアでどんどん難解な部分を補完してきていますので、基礎的なことを知らずに、純粋に回路だけを作るだけで問題が解けます。

準備

まずはMDRのBlueqatを使います。もちろん無料。
pipが入っていれば簡単、

pip install blueqat

その他こちらから入手できます。
https://github.com/mdrft/Blueqat

回路の作り方

簡単な回路の作り方はこちらから。

「量子コンピュータの国産シミュレータblueqatをつかってゲート操作の基本」
http://blog.mdrft.com/post/214

組合せ最適化問題を解くための手法

量子ゲートモデルは最適な回転角の組み合わせというものをQAOAというアルゴリズムでときます。量子断熱計算という計算手法をシミュレートをしますが、難しいことは忘れて大丈夫です。

ときたい問題はハミルトニアン、コスト関数というもので作りますが、こちらは少しコツが必要かもしれません。詳しくは量子イジング、量子アニーリングのドキュメントを参照ください。難しい場合には飛ばしてしまってください。MDRでWildqatと呼ばれるツールを提供して、それも簡単に計算ができるようになってきています。

「量子アニーリング、イジングモデルとフレームワーク」
http://blog.mdrft.com/post/6

ハミルトニアン、コスト関数

組合せ最適化問題を解くには、-1,+1で記述されたコスト関数が必要になります。
ZやYとかのゲート操作と文字で表現されます。Blueqatでは、ZやXなどに係数をつけて計算ができます。
実際に組み合わせ最適化問題を解くにはZゲートの表現だけでいいのですが、例題として少しみてみます。

from blueqat.pauli import *

hamiltonian1 = (1.23 * Z[0] + 4.56 * X[1] * Z[2]) ** 2
hamiltonian2 = (2.46 * Y[0] + 5.55 * Z[1] * X[2] * X[1]) ** 2
hamiltonian = hamiltonian1 + hamiltonian2
print(hamiltonian)

実行すると、

7.5645*I + 5.6088*Z[0]*X[1]*Z[2] + 5.6088*X[1]*Z[2]*Z[0] + 20.793599999999998*X[1]*Z[2]*X[1]*Z[2] + 13.652999999999999*Y[0]*Z[1]*X[2]*X[1] + 13.652999999999999*Z[1]*X[2]*X[1]*Y[0] + 30.8025*Z[1]*X[2]*X[1]*Z[1]*X[2]*X[1]

こんな感じ。また、計算上は不要なゲートもあるので、単純化できます。

hamiltonian = hamiltonian.simplify() # 無駄な演算子を省き、シンプルにする
print(hamiltonian)

かなり簡単になります。

-2.4444000000000017*I - 27.305999999999997j*Y[0]*Y[1]*X[2] + 11.2176*Z[0]*X[1]*Z[2]

例題

BlueqatにはVQEというアルゴリズムを使って QAOAを簡単に解く機能がついています。QAOAはZのゲートの組み合わせだけ計算すればいいので、ハミルトニアンは量子ビット同士の結合や、量子ビットにかかるバイアスの係数を考慮して計算式を作ればいいことになります。

また、通常はイジングの-1,+1で計算をしますが、Blueqatでは、0,+1のバイナリで計算をしてくれるQUBOと呼ばれる式変形にも対応しているため、産業界に簡単に対応できます。0と+1で考えてゲート回路に投入できます。

少し長めの式を作って早速それを解いてみます。

from blueqat import vqe
from blueqat.pauli import qubo_bit as q

hamiltonian = -3*q(0)-3*q(1)-3*q(2)-3*q(3)-3*q(4)+2*q(0)*q(1)+2*q(0)*q(2)+2*q(0)*q(3)+2*q(0)*q(4)+2*q(1)*q(2)+2*q(1)*q(3)+2*q(1)*q(4)+2*q(2)*q(3)+2*q(2)*q(4)+2*q(3)*q(4)
step = 2

result = vqe.Vqe(vqe.QaoaAnsatz(hamiltonian, step)).run() # VQEこれだけ
print(result.most_common(12))

量子コンピュータでは、状態関数と呼ばれるベクトルの形で答えが出てしまうので、ここではサンプリング手法で、うえから12個出現確率の高い順番に答えを出しています。

(((0, 0, 0, 1, 1), 0.0669142552997253), ((0, 0, 1, 1, 0), 0.06691425529972529), ((0, 0, 1, 0, 1), 0.06691425529972529), ((1, 1, 0, 0, 0), 0.06691425529972526), ((1, 0, 1, 0, 0), 0.06691425529972526), ((1, 0, 0, 1, 0), 0.06691425529972526), ((1, 0, 0, 0, 1), 0.06691425529972526), ((0, 1, 1, 0, 0), 0.06691425529972524), ((0, 1, 0, 1, 0), 0.06691425529972524), ((0, 1, 0, 0, 1), 0.06691425529972524), ((1, 0, 0, 0, 0), 0.022190614260905954), ((0, 0, 0, 1, 0), 0.022190614260905937))

出てきた答えの後ろは出現確率です。1が2つ選ばれているこたの出現確率が高く、1が1つのものが少し低くなっています。このように、確率で答えを推測するようになっています。

ちなみにこちらの問題はjupyternotebook形式でこちらからも入手できます。自習に役立ててください。
https://github.com/mdrft/Blueqat/blob/master/tutorial_ja/tutorial003_vqe.ipynb

WildqatとBlueqatを使ってもっと簡単に組合せ最適化問題を解いてみる

Wildqatというイジングを作るSDKとBlueqatを組み合わせることでもっと簡単に実行できます。

まずはWildqatを持っていない方は入手

pip install wildqat

そしてあとは繋げるだけ、

import wildqat as wq
from blueqat import vqe

qubo = wq.pauli(wq.sel(4,1))
step = 4
result = vqe.Vqe(vqe.QaoaAnsatz(qubo,step)).run()
print(result.most_common(5))

上記はWildqatの4つから1つ量子ビットを選ぶという関数です。
その関数を自動的にpauliという関数でQUBOにしています。そして、それをそのままBlueqatにいれることで簡単に問題を解くことができます。最後に5つ答えを取り出します。

結果は、

(((1, 0, 0, 0), 0.2226406659245161), ((0, 1, 0, 0), 0.222640665924516), ((0, 0, 1, 0), 0.222640665924516), ((0, 0, 0, 1), 0.22264066592451595), ((0, 0, 0, 0), 0.02866208270294894))

計算精度の調整はstep数で行います。stepというところを増やしたり減らしたりすることで精度と計算速度を調整できます。問題サイズが大きくなるとstep数を増やすことを推奨します。

qubo = wq.pauli(wq.sel(10,3))
step = 4
result = vqe.Vqe(vqe.QaoaAnsatz(qubo,step)).run()
print(result.most_common(5))

jupyternotebook形式はこちらからも入手できます。
https://github.com/mdrft/Wildqat/blob/master/examples_ja/tutorial025_QUBO_to_Pauli.ipynb

理論面

A Quantum Approximate Optimization Algorithmという組合せ最適化問題を解くためのアルゴリズムが汎用量子コンピュータゲートモデル向けに提案されています。出典は、

「A Quantum Approximate Optimization Algorithm」
Edward Farhi, Jeffrey Goldstone, Sam Gutmann
(Submitted on 14 Nov 2014)
https://arxiv.org/abs/1411.4028

概要は、
「組み合わせ最適化問題の近似解を生成する量子アルゴリズムを紹介する。アルゴリズムは正の整数pに依存し、pが増加すると近似の質が向上する。アルゴリズムを実装する量子回路はユニタリゲートから成り、その局所性がせいぜい目的関数の局所性となり、最適性が求められます。回路の深さは、制約条件の数のp倍(最悪でも)線形で増加します。 pが固定されている場合、つまり入力サイズに依存しない場合、アルゴリズムは効率的な古典的な前処理を利用します。pが入力サイズに依存するならば、別の戦略が提案されます。通常のグラフ上でMaxCutに適用されたアルゴリズムを研究し、固定pの2正則および3正則グラフでその性能を分析する。p=1の場合、3正則グラフでは、量子アルゴリズムは常に、最適カットのサイズの少なくとも0.6924倍のカットを検出します。」

ということで、ユニタリゲートからなり、組み合わせ問題を解き、精度がpに依存するアルゴリズムです。

実例

実例として実機でQAOAを実行した事例があります。

“Unsupervised Machine Learning on a Hybrid Quantum Computer”

J. S. Otterbach, R. Manenti, N. Alidoust, A. Bestwick, M. Block, B. Bloom, S. Caldwell, N. Didier, E.Schuyler Fried, S. Hong, P. Karalekas, C. B. Osborn, A. Papageorge, E. C. Peterson, G. Prawiroatmodjo,N. Rubin, Colm A. Ryan, D. Scarabelli, M. Scheer, E. A. Sete, P. Sivarajah, Robert S. Smith, A. Staley,N. Tezak, W. J. Zeng, A. Hudson, Blake R. Johnson, M. Reagor, M. P. da Silva, and C. Rigetti

Rigetti Computing, Inc., Berkeley, CA
(Dated: December 18, 2017)

https://arxiv.org/pdf/1712.05771.pdf

こちらはRigetti Computingという企業が、19量子ビットの実機を利用してQAOAでmaxcutを実行したというものです。スキームは量子古典ハイブリッド計算で、量子断熱計算という計算を量子シミュレーションし、その基底状態は量子コンピュータと古典計算機を交互に使用し、量子変分法と呼ばれる手法で基底状態(組合せ最適化問題としての解)に近づいていきます。

下記は論文中からのスキーム図で、文章中にあるベイズ最適化は量子計算に代入する2つのパラメータを最適化していて、QAOAをハイブリッドシステムで回す際に、VQEを使用しているのでパラメータ$\beta$と$\gamma$を決定する必要がありますが、量子化学計算の際にはUCC理論に基づいて波動関数をパラメータ化してましたが、QAOAの場合には、UCCに当たるものがないので代替としてベイズ最適化を行っています。

QAOA概要

QAOAはイジングモデルと呼ばれる物理モデルのハミルトニアン(コスト関数)の基底状態を求めるためのアルゴリズムで、量子ゲートモデルの量子コンピュータで計算できるように設計されています。

計算方法

計算方法は横磁場イジングモデルの量子アニーリングに似ていて、最初に基底状態が明確な状態からスタートし、時間展開でだんだん目的のハミルトニアンに近づけていきます。

その際に、初期状態の「リファレンスハミルトニアン」から最終目標の求めたい「コストハミルトニアン」へ段階的に移行するためのステップ数というものがあります。一般的にステップ数を増やすほどに精度が上がります。

ハミルトニアン

全体のハミルトニアンは$\tau$を導入し、初期のハミルトニアンから最終のハミルトニアンに段階的に移行します。

$
\hat{H_\tau} = \tau \hat{H}_{ref} + (1-\tau)\hat{H}_{MAXCUT}
$

リファレンスハミルトニアン

リファレンスハミルトニアンは基底状態の自明な状態からスタートします。

$
\hat{H}_{ref} = \sum_{i=0}^{N-1}\sigma_i^X
$

初期の状態は|+>のテンソル積で表現できます。

$
\mid \Psi_{ref}\rangle = \mid+\rangle_{N-1}\otimes \mid+\rangle_{N-2}\otimes … \otimes \mid+\rangle_0
$

実際に回路上で実現するには、下記のように全ての量子ビットを0に初期化した上でアダマール変換をかけて重ね合わせ状態を作って準備します。


H 0
H 1
...
H N-1

コストハミルトニアン

コストハミルトニアンは今回求めたい答えのコスト関数を記述します。こちらは問題ごとにハミルトニアンが異なります。

$
\hat{H}_{COST}
$

QAOAの実行

QAOAでは、リファレンスハミルトニアンからコストハミルトニアンに段階的に移行する過程でシミュレーションを行います。ステップ数を決めて、それに対して$\tau$を変化させながらシミュレーションを行います。

$
\hat{H_\tau} = \tau \hat{H}_{ref} + (1-\tau)\hat{H}_{MAXCUT}
$

こちらに対して、たとえばステップ数2のシミュレーションでは、

$
U = U(\hat{H}_{\alpha_1})U(\hat{H}_{\alpha_0})
$

このように連続的にユニタリーオペレーターを作用させます。

それぞれのユニタリーオペレーター

それぞれの各段階的なユニタリーオペレーターは、上記ハミルトニアンから鈴木トロッター展開を経て、ハミルトニアンの和から連続したユニタリーオペレーターに分解されます。

$
U(\hat{H}_{s_i}) = U(\tau \hat{H}_{ref} + (1-\tau)\hat{H}_{MAXCUT}) = U(\hat{H}_{ref},\beta_i)U(\hat{H}_{MAXCUT},\gamma_i)
$

となり、それぞれ、

$
U(\hat{H}_{ref},\beta_i) = e^{-i\hat{H}_{ref}\beta_i}
$

$
U(\hat{H}_{MAXCUT},\gamma_i) = e^{-i\hat{H}_{MAXCUT}\gamma_i}
$

です。

まとめると

上記をまとめると、ユニタリーオペレーターの連続発展と、鈴木トロッター展開による各ユニタリーオペレーターの分解によって、全体は綺麗にユニタリーオペレーターの連続発展に書き直されますので、初期の基底状態からユニタリーオペレーターを連続的に作用させることで最終の状態をえます。

$
\mid \beta,\gamma \rangle = e^{-i\hat{H}_{ref}\beta_1}e^{-i\hat{H}_{MAXCUT\gamma_1}}e^{-i\hat{H}_{ref}\beta_0}e^{-i\hat{H}_{MAXCUT\gamma_0}}\mid + \rangle_{N-1,…,0}
$

つまり

パラメータを変えながら、2つのコスト関数に対応する操作を交互に実行すると答えが出ます。

シミュレーションを行うアルゴリズム

上記の連続したユニタリーオペレーターを計算するには、問題によっては精度を出すためには長い回路が必要です。現在はNISQと呼ばれるエラーありの中規模回路ですので、従来の期待されていたアルゴリズムの代替としてVQEなどの量子変分法を利用したアルゴリズムも利用されますので、そちらを利用して解くことが多いようです。

あわせて読みたい

SERVICE

汎用量子コンピュータ向けアプリケーション開発SDK

詳しく見る Githubで入手する(無料)

汎用量子コンピュータ向け高速シミュレータ

詳しく見る

量子コンピュータ向けクラウドサービス(準備中)

詳しく見る

イジングマシン向けアプリケーション開発SDK

詳しく見る Githubで入手する(無料)

COMMUNITY

量子コンピュータのことを学びたい、仕事としたいなどの情報交換の場を設け、コミュニティの形成を進めています。オフラインの勉強会と、オンラインのチャットコミュニティの2種類あります。オフラインのConnpassは1400名、オンラインのSlackは880名を超える参加があります。どちらも無料ですのでお気軽にご参加ください。

CONNPASS SLACK

CONTACT

弊社あての連絡はinfo@mdrft.comより用件を明記の上、メールで連絡を頂けますと幸いです。

ブログトップに戻る

Recent Posts