Quantum Alternating Operator Ansatzを使用したポートフォリオリバランスのレビュー

はじめに

リゲッティ社がオーストラリア・コモンウェルス銀行と行ったポートフォリオリバランスの問題を見てみたいと思います。2020年前半は少し丁寧に論文を見ていきます。

参照

こちらです。

Portfolio rebalancing experiments using the Quantum Alternating Operator Ansatz

Mark Hodson∗, Brendan Ruck∗, Hugh (Hui Chuan) Ong†, David Garvin∗, Stefan Dulman† ∗Rigetti Computing †Commonwealth Bank of Australia

https://arxiv.org/pdf/1911.05296.pdf

内容

離散ポートフォリオ最適化問題を量子ゲート方式のマシンで行います。主にシミュレータを使って評価をし、様々なポートフォリオ最適化に関する要素も取り入れています。また、今回の論文の肝はQuantum Alternating Operator Ansatzというテクニックで、その辺りを中心に見ていきたいと思います。マシンは量子ゲート方式と呼ばれる汎用型マシンですが、エラーがあるので、ちょっと計算を工夫する必要があります。

量子ゲートで組み合わせ最適化問題

上記のポートフォリオ最適化問題は離散最適化、組合せ最適化の部類になります。量子コンピュータでそれを解く際にはイジングに落とし込む必要があります。

イジングモデルに落とし込む際に必要なのはコスト関数と呼ばれるもので、コスト関数を最小にすることを組合せ最適化の解に割り当てます。解くべきコスト関数は、

C(s) = c + \sum_{i=1}^N h_i s_i + \sum_{i=1}^N\sum_{j=i+1}^N J_{ij}s_is_j

となり、cは定数、hはバイアス、Jは相互作用係数です。

QAOA

QAOAはニアタームアルゴリズムと呼ばれ、量子ゲートマシンでエラーがありながらもハイブリッドで計算できる方式でよく使われる組み合わせ最適化問題向けのアルゴリズムです。

元々は時間発展アルゴリズムというものがベースとなっており、それを変分アルゴリズムに改造されています。ここでは、ときたいコスト関数を上記のC、QAOAでよく使われる初期化されたコスト関数をBとして、BをCへと断続的に変化させることで、量子断熱計算と呼ばれる手法で、基底状態＝最小値を探していきます。

量子変分原理では、量子回路中の角度をパラメータとして、

\langle \Psi_1\mid C \mid \Psi_1\rangle

ある量子状態でハミルトニアンを測定したときの期待値を最小にするような量子状態を探していきます。この $\Psi_1$ はQAOAアルゴリズムによって変分計算で網羅的に探していきます。

初期状態のコスト関数にはPauli-Xを基底（ $\sigma^x$ ）とした、

B = \sum_{i=1}^N \sigma_i^x

を利用します。元のコスト関数は同様にPauli-Zを基底( $\sigma^z$ )として、書き換えることができ、

C(s) = c + \sum_{i=1}^N h_i \sigma^z_i + \sum_{i=1}^N\sum_{j=i+1}^N J_{ij}\sigma^z_i \sigma^z_j

こちらを使います。これらのコスト関数は、時間発展を改造したQAOAで量子状態を変化させる形で導入されますが、

\mid \Psi_1 \rangle = \left( \prod_{\alpha=p}^1 U(B,\beta_\alpha)U(C,\gamma_\alpha)\right) \mid \Psi_0 \rangle

のように、繰り返しユニタリ行列をかけることで初期の量子状態を変化させることができます。初期の量子状態は今回は、

\mid \Psi_0 \rangle = \mid + \rangle^{\otimes N}

のように、N量子ビットにアダマールゲートを適用し、|+>状態に持っていくことで準備できます。 $\otimes N$ は単にN量子ビットのテンソル積で構成されているということを示しています。

それぞれのユニタリ行列は、

U(B,\beta_\alpha) = e^{-iB\beta_\alpha}

や

U(C,\gamma_\alpha) = e^{-iC\gamma_\alpha}

のように、時間発展型で記述されます。

コスト関数のCはユニタリ行列ではないですが、エルミート行列であるので、指数の肩に載っていてもユニタリ行列へ変換できます。

これで基本的なアルゴリズムの準備はOKです。ちなみにBのコスト関数はmixing operatorと論文中では表現されており、量子ビットの探索を担当する役割をしています。

もう一つのQAOA、Quantum Alternating Operator Ansatz

上記のQAOAを実施すると確かに頑張れば答えが出るのですが、通常コスト関数に導入される制約条件と呼ばれるものから、実は探索すべき空間を制限できることがわかります。

通常コスト関数は、コストと制約条件からなり、最小化したいコストと並行して満たすべき条件の制約条件を項として持ちます。この制約条件はソフト制約の形でハイパーパラメータを導入しながら解かれますが、結構この制約条件が悪さをします。

C = cost + \lambda * constraint

Quantum Alternating Operator Ansatzでは、この制約条件を量子ゲートの時間発展として考慮し、最初から制約を満たすべき空間を制限して探索してしまおうというものです。そうすることにより、探索する空間を部分空間に制限することで探索を効率化することができます。これは長年量子アニーリングにおいて望まれていた機能そのものです。

XYミキサー、パリティミキサー

今回利用するのはPauli-XYミキサー、もしくはパリティミキサーと名付けられたもので、XXとYYの時間発展で実現できます。

X_0X_1 + Y_0Y_1 = \begin{bmatrix} 0&1\\ 1&0 \end{bmatrix} \otimes \begin{bmatrix} 0&1\\ 1&0 \end{bmatrix} + \begin{bmatrix} 0&-i\\ i&0 \end{bmatrix} \otimes \begin{bmatrix} 0&-i\\ i&0 \end{bmatrix} \\ = \begin{bmatrix} 0&0&0&1\\ 0&0&1&0\\ 0&1&0&0\\ 1&0&0&0 \end{bmatrix} + \begin{bmatrix} 0&0&0&-1\\ 0&0&1&0\\ 0&1&0&0\\ -1&0&0&0 \end{bmatrix} = 2 \begin{bmatrix} 0&0&0&0\\ 0&0&1&0\\ 0&1&0&0\\ 0&0&0&0 \end{bmatrix}

こちらをハミルトニアンとして導入することで、対象の|01>状態と|10>状態を入れ替えることができ、状態ベクトルのone-hot encodingを維持したまま探索できます。

また、肝心のユニタリ変換は、変分パラメータβを含む形で分解され、

U(B,\beta_\alpha) = U(B_{last},\beta_\alpha)U(B_{odd},\beta_\alpha)U(B_{even},\beta_\alpha)

で、

B_{odd} = \sum_{odd}^{N-1} \sigma_a^x \sigma_{a+1}^x + \sigma_a^y\sigma_{a+1}^y

B_{even} = \sum_{even}^N \sigma_a^x \sigma_{a+1}^x + \sigma_a^y\sigma_{a+1}^y

Nがoddの時、\\ B_{last} = \sigma_N^x \sigma_1^x + \sigma_N^y\sigma_1^y\\ \\ Nがevenの時\\ B_{last} = I

となります。

ポートフォリオリバランス

ポートフォリオのリバランスは、トレーダーが機関投資家のポートフォリオの純価値を維持し、機関の助言に基づいて資産構成を調整し、市場の状況の変化に応じてリスクをヘッジする定期的な資産管理プロセスです。リバランスは、資産のロングポジションとショートポジション、およびそれらのデリバティブ（プットオプションとコールオプション）を含む金融商品の組み合わせを使用して実現できます。リバランスの頻度は、市場のボラティリティ、リスクプロファイル、資産の流動性、取引コストなどの多くの要因に依存します。毎日、毎週、または毎月実行されます。関連するリスク計算を含むリバランスの計算負荷は、通常、夜間に実行されるので、将来的な量子コンピューターによってもたらされる大幅なスピードアップにより、金融機関は意思決定をより機敏に行えるようになり、市場の状況の変化により迅速に対応できるようになります。

過去の量子アニーリングの例など

マルコウィッツモデルポートフォリオの離散ポートフォリオ最適化は、整数を使用して記述した場合、NP完全であることが証明されています。量子コンピューティングの離散ポートフォリオ最適化への適用性は、量子アニーリングや特殊なゲートモデルアルゴリズムを使用して実証されましたが、QAOAを使用してまだ評価されていません。

量子アニーリングもQuantum Alternating Operator Ansatzのような制約条件をハード制約に落とし込むような概念が提案されてはいますが、実現していません。アニーリングモデルの実機ではペナルティ関数をソフト制約に落とし込む必要があり、Quantum Alternating Operator Ansatzのようなハード制約が実現できていないのが大きな違いです。

ゲートマシンを使って、ソフト制約をハード制約に書き換え（シミュレータ）

ゲートモデル量子コンピューターのシミュレーターでQAOAを使用して実装された、複数期間ポートフォリオリバランスシナリオの制約下での離散ポートフォリオ最適化とパフォーマンスの実験的評価です。ソフト制約定式化を設計および実装し、Quantum Alternating Operator Ansatzに基づいてハード制約定式化と比較しています。

モデル化に先駆けて

ポートフォリオ最適化をモデル化するにあたって、いくつかポイントがあります。

１つ目は離散化されたロットでの取引で、資産は正の整数量でのみ取引ができますが、連続量の値を離散量で近似する際に見積もりが甘くなることがあるようです。

2つ目は、不確実性のモデリングにあります。マルコウィッツモデルポートフォリオ共分散行列の不確実性を完全に扱うには、半正定値プログラミングが必要です。近似は、独自の市場分散に基づいて各資産のポートフォリオ位置空間を離散化されますが、基本的にはイジングモデルでは不確実性を不等式で表現したり、解くのは苦手なので、別の形でモデル化をしておく必要があります。

3つ目は、投資の制約を表すことです。この場合、ポートフォリオの合計値は、リバランスプロセス全体でほぼ維持する必要があります。これは、最適化プロセスの絶対位置ではなく、以前の相対位置を考慮するためにリバランスシナリオで修正された、標準的なマルコウィッツモデルの離散ポートフォリオ最適化問題に共通です。

4つ目は、取引コストのモデリングにあります。これは、資産で取引が発生した場合にのみ発生します。この非線形関数には、離散的な論理関数で自然に表現できる段階的なコスト変化が含まれます。リバランスのシナリオでは、取引規模に関係なく取引コストは固定されていると仮定します。

最後に、通常保有できる資産の最大数、最小配分サイズ、マルチクラスポートフォリオの取引資産クラスの制約など、制約があります。この論文では、最初の2つの特性に基づいて離散ロットサイズを選択できると想定し、取引コストと投資の制約を含む制約の下で離散ポートフォリオの最適化を実行しています。

定式化

定式化をみてみます。今回実現したいのはどの資産を保有するかをコスト関数を通じて表現をします。zという保有に対して、最小化する関数は、 $C_{RR}$ はリターンとリスクの関数、 $C_{TC}$ は取引コストです。

z = argmin_z C_{RR}(z) + C_{TC}(z)

リスク　マイナス　リターンで損失に対する期待値がもとまり、それに固定の取引コストを足し合わせた関数を最小化します。

zは $\\{-1,0,+1\\}^N$ となる値で、ロング(+1)、ショート(-1)、保有なし(0)を割り当てます。 $C_{RR}(z)$ は正規化された（損失）-（収益）の関数 $C_{TC}(z)$ は固定の取引コストです。

Nは選択肢として与えられた資産の数で、今回の制約として、

\sum_{i=1}^Nz_i = D

があります。Dは今回の離散化された資産のロットの合計値です。

risk-return関数の定式化

メインのコスト関数でrisk-returnでの損失の期待値は、マルコウィッツモデルを使って、

C_{RR}(z) = \lambda\sum_{i=1}^N\sum_{j=1}^N\sigma_{ij}z_iz_j - (1-\lambda)\sum_{i=1}^N\mu_iz_i

$\lambda$ はリスクを取り入れるパラメータで、0から1の値を取り、 $\lambda = 1$ はローリスク、 $\lambda = 0$ はハイリターン構成になります。 $\sigma$ は正規化されたリスクの共分散行列、 $\mu$ は平均リターンのベクトルになります。

取引コストの定式化

取引コストは、

C_{TC}(z) = \sum_{i=1}^N(1-\delta(z_i-y_i))T

で、 $y$ は $\\{-1,0,+1\\}^N$ をとる、前回のポジション、 $\delta(z)$ はディラックのデルタ関数で、z=0の時に1で、それ以外は0、 Tは取引が発生した時に発生する正規化された取引コストです。

risk-return関数の実装

定式化の次は実装です。 $z_i$ は２量子ビットのスピンを使って表現されます。ロング・ショートをとるか取らないかを、量子ビットを使って、表現し下記のようになります。（すみません、、、数式打つのが大変なので以下は引用とさせてください。）

z_i = x_i^+ - x_i^- \\ x_i^+ はロングポジションをとるかどうか \\ x_i^- はショートポジションをとるかどうか

スピンをつかって、下記のように書き換えられました。イジングの+1,-1でかけます。

z_i = \frac{s^+_i - s^-_i}{2}, (s^-_i,s_i^+)\in \{-1,+1\}

そして、保有や取引コストとの対応表は下記の通りです。

引用：https://arxiv.org/pdf/1911.05296.pdf

先ほどの関数をスピンで書き換えると、

C_{RR}(s) = \lambda \sum_{i=1}^N \sum_{j=1}^N \frac{\sigma_{ij}}{4}(s^+_is^+_j - s^+_is^-_j - s_i^-s_j^+ + s^-_is^-_j) - (1-\lambda)\sum_{i=1}^N\frac{\mu_i}{2}(s^+_i - s_i^-)

比較的わかりやすい形となりました。

取引コストの実装

上記の表に準じて、スピンでの場合わけをすると、

if y_i = -1\\ C_{TC}(s) = \frac{1}{4}T(3 + s^+_i - s^-_i + s^+_is^-_i)

if y_i = 0\\ C_{TC}(s) = \frac{1}{4}T(3 + s^+_i + s^-_i - s^+_is^-_i)

if y_i = +1\\ C_{TC}(s) = \frac{1}{4}T(3 - s^+_i + s^-_i + s^+_is^-_i)

場合わけは使えないので、スピンで表現すると、

C_{TC}(s) = \frac{1}{4}T(3+(1-y^2_i-y_i)s_i^+) + (1-y^2_i+y_i)s_i^- + (2y^2_i-1)s_i^+s_i^-

なかなかいい感じです。

投資の制約条件の実装（ソフト制約編）

さて、ここからが本番です。QAOAでのソフト制約の作り方は、

P_{INV}(Z) = A(\sum_{i=1}^N z_i - D)^2

このように、調整パラメータAを使いながら、(zの合計)-(D)の２乗を最小にするというよくあるパターンを採用します。スピンで書いて、展開して、

P_{INV}(s) = \frac{A}{4} \sum_{i=1}^N \sum_{j=1}^N (s^+_is^+_j - s^+_is^-_j - s_i^-s_j^+ + s^-_is^-_j) - AD\sum_{i=1}^N(s^+_i - s_i^-) + AD^2

が得られます。よくある形です。

投資の制約条件の実装（ハード制約編）

上記の制約をハード実装します。Quantum Alternating Operator Ansatzに基づいて上記のソフト制約条件をハード制約するのが今回の論文の一番の目的です。

式の投資制約は、ロングの決定変数とショートの決定変数に独立して作用するパリティミキサーのペアを使用して実現できます。ロングポジションとショートポジションの間のエンタングルメントを使用して、実行可能な結果のセットを正しいネットパリティに制約します。

また、資産の数Nと指定されたロットDから、Kの値で指定される離散のパリティバンドKが下記のように決まります。

K = N - D + 1

設計目標は、これらのパリティバンドでの部分集合で、ロングミキサーとショートミキサーが量子状態を交換できるようにすることです。これは、ロットDの最小ロングポジションを確立する計算基底状態を準備し、量子もつれが残りの資産全体で必要なパリティ関係を保証するようなベル状態をつかって実現されます。なので、ベル状態をつかって初期状態は下記のようになります。

\mid \psi_0 \rangle = (\mid 01 \rangle)^{\otimes D} \otimes (\frac{1}{\sqrt{2}}\mid 00 \rangle + \frac{1}{\sqrt{2}}\mid 11 \rangle)^{\otimes (N-D)}

パリティバンド全体で均一な解の確率は提供されない代わりに、可能性のある解の母集団に基づいて、二項分布が作成されます。

引用：https://arxiv.org/pdf/1911.05296.pdf

初期状態とアルゴリズム構成を図1に示します。

引用：https://arxiv.org/pdf/1911.05296.pdf

同じ問題サイズの場合、初期パリティバンドの確率分布を表3に示します。

引用：https://arxiv.org/pdf/1911.05296.pdf

ソフト制約でのQAOAの実行

ソフト制約では制約項を含む３つの項で計算が実行されます。

C_{soft}(s) = C_{RR}(s) + C_{TC}(s) + P_{INV}(s)

ハード制約でのQAOA+Quantum Alternating Operator Ansatz

こちらは最後の１つがハード制約で実装されているので、解くべきなのは２つだけです。

C_{hard}(s) = C_{RR}(s) + C_{TC}(s)

実験データ

この実験の入力データは、2017年のオーストラリアASX.20市場の株価の日次リターンです。データは20株と252取引日を対象としました。

引用：https://arxiv.org/pdf/1911.05296.pdf

N = 8株のデータ（AMP、ANZ、BHP、BXB、CBA、CSL、IAG、MQG）が実験で使用するために選択されました。 1日の平均収益率（µi）を表IVに示します。資産リターンの共分散（σij）は図2にあります。慣例により、共分散σii=σ2 i（σiは標準偏差（S.D.））です。

引用：https://arxiv.org/pdf/1911.05296.pdf

制約項の調整パラメータ

調整パラメータを正しく設定しないと、満たすべき制約が正しく設定されません（ソフト制約において）。

A > max[C(s)] - min[C(s)]

基準として、上記のように調整パラメータのサイズの目安が与えられます。

解空間の調査

最初に大体どれくらいの解があり、どれくらいが制約を満たして実行可能かをみてみます。

まず、ブルートフォース法を使用してソリューション空間を評価します。 N = 8のストックを考えると、コスト関数のエンコードには16のスピン変数が必要であり、 $2^{16} = 65536$ の解状態の組み合わせ空間を提示します。これらのうち、D=4で実行可能なのは1820（2.78％）のみであり、式の投資制約によって決定されます。

ファイナンスでは、一般的な式から期待リターンとリスクの累積値に対して実行可能なポートフォリオソリューションをプロットします。これを図3に示します。λが変化すると、最適な離散ソリューションポイントが変わり、利用可能なポートフォリオソリューションの離散効率が作成されます。

引用：https://arxiv.org/pdf/1911.05296.pdf

実行

QAOAをパラメータを決めて実行してみます。A = 0.03として。リスクリターンコントロールパラメーターはλ= 0.9、取引コストT = 0に設定されています。図４の結果が得られました（ソフト制約）。

引用：https://arxiv.org/pdf/1911.05296.pdf

課題

QAOAを実行したのにもかかわらず、探索する角度パラメータの値が小さいため探索がうまく行われていないということが考察されたため、パラメータを改善する必要がありました。

入力データを日次収益ではなく年次収益にスケーリングすることにより、この問題に対処します。年間収益は、平均µiと共分散σijの両方に250を掛けることにより、日次収益から計算されます。ペナルティスケーリング係数は、A = 0.75として再計算されます。実験を再度実行すると、図6の結果が得られます。データの周期構造から明らかなように、初期混合が改善されていることが観察されます。

引用：https://arxiv.org/pdf/1911.05296.pdf

評価

QAOA実験のすべての統計は、ランダムにシードされた20回のシミュレーション実行で計算されます。

結果、図7ではQAOAは33-66%の結果で実行可能な（制約条件を満たす）解を返した一方で、Quantum Alternating Operator Ansatzは100%の確率で解を返しています。

引用：https://arxiv.org/pdf/1911.05296.pdf

実行可能解の領域に制限されたコスト関数の累積確率を図8に示します。Quantum Alternating Operator Ansatzは、実行可能解のランダム選択に関して優れたパフォーマンスを示し、元のQAOAアルゴリズムとのパフォーマンスの違いは大きく、QAOAを使用した制約付き問題の解決におけるハード制約設計の重要性を強調しています。

引用：https://arxiv.org/pdf/1911.05296.pdf

複数期間のリバランスシナリオにQAOAアルゴリズムを使用するように実験を拡大します。このシナリオでは、2017年の最初の6か月ごとに個別に計算された平均年間収益率を考慮し、1か月に1回ポートフォリオのバランスを調整します。取引コストはT = 0.015に含まれています。これは、利用可能な株式の年間収益率と同程度です。年間収益率の月次統計により、短期間で発生する最小値と最大値の極端さが大きいため、式25に従うAにはA = 2.5を設定します。

トレーダーとアナリストが関心を持っている指標を計算します。これには、取引の総数、取引コストに対して調整されたポートフォリオのリターン、期間中の平均リスクが含まれます。２つの定式化の両方を使用してテストし、ブルートフォース法によって決定された最適な軌道と比較します。このシナリオでは複数期間の市場予測が利用できないため、最適化は各タイムステップで独立して実行されることに注意してください。つまり、最適な軌道はブルートフォース法によって発見されたものとは限りません。

図9は、リバランスの6か月間に実行された取引の総数を示しています。初期保有ゼロから、目標のD = 4に到達する取引の最大数は8取引です。ロング6とショート2の割合です。残りの5か月間、取引の最大数は4で、ロングポジションとショートポジションの変化を相殺します。これにより、6か月間の取引数の上限が28になります。

引用：https://arxiv.org/pdf/1911.05296.pdf

リスクを最小限に抑えるためにλが増加すると、リスクを軽減するために必要な負の相関を持つ株式のペアがあまり多くないという図2と一致して、取引活動が減少します。元のQAOAから得られた1つの悪い結果を除いて、質的には両方のQAOAは、最適に近い性能を発揮することがみれます。

その他もいくつか計算結果がありましたが、詳しい内容は元の論文を見てみてください。

考察

今回はシミュレータで２種類のアルゴリズムが実行されました。結果として、なかなか良い結果が得られましたが、実機を使っていないので、

（i）ハードウェアリソース分析による回路の深さ。（ii）シミュレートされたパフォーマンス分析によるノイズの影響。（iii）現在の世代のNISQハードウェアでの検証。

これらは実用的なアプリケーションの実現に向けて実機を使った考察を進める必要がありそうです。

XYミキサーの実用問題での具体的な使い方を見てみました。初期条件を満たす初期量子状態を準備し、問題に応じたハード制約をパリティミキサーの形で実装しています。考え方としては大変面白いので、ぜひ頑張ってマスターしたいところです。

Quantum Alternating Operator Ansatzを使用したポートフォリオリバランスのレビュー

Yuichiro Minato

はじめに.css-1yssqf7{opacity:0.6;border:0;border-color:inherit;border-style:solid;border-bottom-width:1px;width:100%;margin-top:var(--chakra-space-2);}

参照

内容

量子ゲートで組み合わせ最適化問題

QAOA

もう一つのQAOA、Quantum Alternating Operator Ansatz

XYミキサー、パリティミキサー

ポートフォリオリバランス

過去の量子アニーリングの例など

ゲートマシンを使って、ソフト制約をハード制約に書き換え（シミュレータ）

モデル化に先駆けて

定式化

risk-return関数の定式化

取引コストの定式化

risk-return関数の実装

取引コストの実装

投資の制約条件の実装（ソフト制約編）

投資の制約条件の実装（ハード制約編）

ソフト制約でのQAOAの実行

ハード制約でのQAOA+Quantum Alternating Operator Ansatz

実験データ

制約項の調整パラメータ

解空間の調査

実行

課題

評価

考察

はじめに