東芝SBMの量子アニーリング？でポートフォリオ最適化メモ

f:id:dw_dw_dt:20210417013820j:plain

※今回の記事は専門じゃないことを記載しているので、間違いがあるかもですが、その際はコメントいただけると幸いです。

さて、今更感がありますが、東芝のシミュレーテッド分岐マシン(以下SBM)なるソルバーを使ってみました。

www.global.toshiba

このSBMというのは量子コンピュータ（イジング方式）が得意な計算を

普通のコンピュータでできるようにしてみたアルゴリズムのことだそうです。

イジング方式は組み合わせ最適化問題が得意（超早い）ということで

実用性はいったん置いておいて、とりあえずポートフォリオ最適化を

整数計画にアレンジした際のやり方をメモしました。

ノリ的にはalpacaさんがarXivにあげている以下の論文と似ているかと思います。

https://arxiv.org/pdf/2009.08412.pdf

なお、SBMは以下のAWS marketplacesにて販売されています(FPGAではなくGPU版)。

aws.amazon.com

量子アニーリング

余裕で専門外なのでざっくりとした話しかできないのですが

そもそも量子コンピュータというのは2種類に分類できるもので

ゲート方式

イジング方式

という2種類があるみたいです。

で、ゲート方式というのは汎用的なマシンのことで

イジング方式は組み合わせ最適化に特化した量子コンピュータのようです。

IBM-Qやgoogleマシンがゲート方式で、D-WAVEがイジング方式みたいです。

で、そのイジング方式は、量子アニーリングという手法で

量子焼きなまし法 - Wikipedia

組み合わせ最適化を解くのですが、それを普通のPCで解けるようにしたのが

今回触ってみる東芝様のSBMというものになります。

ちなみに量子コンピュータそのものについては、

東大が公開している以下のmaterialが役に立ちそうです。

utokyo-icepp.github.io

問題設定

あまり筋が良いとは思えませんが、

いわゆるポートフォリオ最適化に対してSBMを適用してみたいと思います。

通常のポートフォリオ最適化は

$w \in \mathbb{R}$ を最適ウェイトとして $max_{w} \mu^{T} w - \lambda w^{T} \Sigma w$

みたいなものを解くわけですが、

SBMで解くためには、以下の形（イジング問題）に変換する必要があります。

$x$ を成分が $0$ または $1$ からなるベクトルとして $min_{x} x^{T}Z x$

この $Z$ をSBMのインスタンスに投げることで、答えのresponseが返ってくるイメージです。

問題の変形

さて、上で見た通り通常のポートフォリオ最適化から

SBMで受け取れるように変形する必要があります。

その際、ウェイト $w$ を求める問題から数量 $x$ を求める問題に変わってしまいますが

それは特に問題ないかなと思います。

2進展開

たとえば、12という数字は、以下のように2進展開できます。

$12 = 0 * 2^{0} + 0 * 2^{1} + 1 * 2^{2} + 1 * 2^{3}$

このテクニックを使うことで、

12という数字は $(0,0,1,1)$ という01ベクトルと対応付けることができそうです。

すると、例えば期待リターンが3の証券を12個保有した際の

期待リターンは以下のようにあらわすことができます。

$3 * (1, 2, 4, 8) (0, 0, 1, 1)^{T} = 36$

さらに、複数証券のときは、 $d = (1,2,4,8)$ として

期待リターンが3の証券を12個、3.5の証券を10個保有した際は

$(3, 3.5)C(0,0,1,1,0,1,0,1)^{T}=71$

ただし $C$ は対角成分に $d$ が並んでいる2*8行列

のようにあらわすことができそうです。

このように考えることで、

$\mu^{T} C x$

という形で、証券を $x$ だけ保有した際の期待リターンが求まる。

ただし、これではまだ二次形式になっていないのでSBMには投げれない。

そこで、01ベクトルはその成分を2乗しても変わらないことを利用して

$\mu^{T} C x = x^{T} diag(\mu) \otimes diag(d) x$

とすることで、はれて二次形式となる。

そして、リスクについては

$x^{T}C^{T} \Sigma C x$

とすれば、 $x$ だけ保有した際のリスクになるので

$x^{T} (C^{T} \Sigma C - diag(\mu) \otimes diag(d)) x$

を最小化することで、いわゆるポートフォリオ最適化と類似の問題に帰着する。

コード

最小化するべき二次形式の真ん中の行列をまずは計算する。

サンプルとして以下のようなものを想定する。

import numpy as np


Z = np.zeros((2,2))
Z[0][0] = 10
Z[0][1] = 3
Z[1][0] = 4
Z[1][1] = 7

次にこれを所定の形式で吐き出す。

from scipy.io import mmwrite
from scipy.sparse import csr_matrix


mmwrite('Z.mtx', csr_matrix(Z), field='real', symmetry='symmetric')

最後にこれをSBMのインスタンスに投げつけて、

レスポンスを読み取る

from urllib import request


res = request.urlopen(
    request.Request(url='***', data=open('Z.mtx', 'rb'), headers={'Content-Type': 'application/octet-stream'}
)
result = json.load(res.read())

となります。

とはいえ

まぁポートフォリオ最適化だと

整数計画に精緻化するメリットが希薄なのと、

変数の数が2進展開で爆増してしまって

結局スピード面の優位性がそがれるので、

あまり良い事例ではないように感じられます。

東芝社の論文内で述べられている為替の三角裁定や

ダルマキャピタルとの共同研究の株 stat arbのほうが筋が良さそうですね。

ではまた！

今回の関連図書

リンク

そこそこわかりやすく記載されていた気がします。